Self-Adjusting Binary Search Trees: What Makes Them Tick?
2015 (English)In: ALGORITHMS - ESA 2015, Springer Verlag , 2015, 300-312 p.Conference paper (Refereed)Text
Splay trees (Sleator and Tarjan ) 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 , Georgakopoulos and McClurkin ), as well as Greedy BST, introduced by Demaine et al.  and shown to satisfy the access lemma by Fox , (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 ) 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 after-tree 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.
Place, publisher, year, edition, pages
Springer Verlag , 2015. 300-312 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 9294
IdentifiersURN: urn:nbn:se:kth:diva-180171DOI: 10.1007/978-3-662-48350-3_26ISI: 000366210300028ScopusID: 2-s2.0-84945581492ISBN: 978-3-662-48350-3; 978-3-662-48349-7OAI: oai:DiVA.org:kth-180171DiVA: diva2:893124
23rd Annual European Symposium on Algorithms (ESA) as part of ALGO Conference, SEP 14-16, 2015, Patras, GREECE
QC 201601122016-01-122016-01-072016-01-12Bibliographically approved