Change search
ReferencesLink to record
Permanent link

Direct link
Self-Adjusting Binary Search Trees: What Makes Them Tick?
Show others and affiliations
2015 (English)In: ALGORITHMS - ESA 2015, Springer Verlag , 2015, 300-312 p.Conference paper (Refereed)Text
Abstract [en]

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 McClurkin [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 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.
Series
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 9294
National Category
Computer Science
Identifiers
URN: 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
Conference
23rd Annual European Symposium on Algorithms (ESA) as part of ALGO Conference, SEP 14-16, 2015, Patras, GREECE
Note

QC 20160112

Available from: 2016-01-12 Created: 2016-01-07 Last updated: 2016-01-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Saranurak, Thatchaphol
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 398 hits
ReferencesLink to record
Permanent link

Direct link