Self-adjusting binary search trees: What makes them tick?

Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

6 Citations (Scopus)

Abstract

Splay trees (Sleator and Tarjan [11]) satisfy the so-called access lemma. Many of the nice properties of splay trees follow from it. What makes self-adjusting binary search trees (BSTs) satisfy the access lemma? After each access, self-adjusting BSTs replace the search path by a tree on the same set of nodes (the after-tree). We identify two simple combinatorial properties of the search path and the after-tree that imply the access lemma. Our main result (i) implies the access lemma for all minimally self-adjusting BST algorithms for which it was known to hold: splay trees and their generalization to the class of local algorithms (Subramanian [12], Georgakopoulos and Mc- Clurkin [7]), as well as Greedy BST, introduced by Demaine et al. [5] and shown to satisfy the access lemma by Fox [6], (ii) implies that BST algorithms based on “strict” depth-halving satisfy the access lemma, addressing an open question that was raised several times since 1985, and (iii) yields an extremely short proof for the O(log n log log n) amortized access cost for the path-balance heuristic (proposed by Sleator), matching the best known bound (Balasubramanian and Raman [2]) to a lower-order factor. One of our combinatorial properties is locality. We show that any BST-algorithm that satisfies the access lemma via the sum-of-log (SOL) potential is necessarily local. The other property states that the sum of the number of leaves of the aftertree plus the number of side alternations in the search path must be at least a constant fraction of the length of the search path. We show that a weak form of this property is necessary for sequential access to be linear.

Original languageEnglish
Title of host publicationAlgorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings
PublisherSpringer Verlag
Pages300-312
Number of pages13
Volume9294
ISBN (Print)9783662483497
DOIs
Publication statusPublished - 2015
MoE publication typeA4 Article in a conference publication
EventEuropean Symposium on Algorithms - Patras, Greece
Duration: 14 Sep 201516 Sep 2015
Conference number: 23

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9294
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

ConferenceEuropean Symposium on Algorithms
Abbreviated titleESA
CountryGreece
CityPatras
Period14/09/201516/09/2015

Fingerprint Dive into the research topics of 'Self-adjusting binary search trees: What makes them tick?'. Together they form a unique fingerprint.

Cite this