Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published paper (Refereed)
Resource type
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: 000366210300028Scopus ID: 2-s2.0-84945581492ISBN: 978-3-662-48350-3; 978-3-662-48349-7 (print)OAI: 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

Altmetric score

Total: 406 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf