Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Self-Adjusting Binary Search Trees: What Makes Them Tick?
Vise andre og tillknytning
2015 (engelsk)Inngår i: ALGORITHMS - ESA 2015, Springer Verlag , 2015, s. 300-312Konferansepaper, Publicerat paper (Fagfellevurdert)
Resurstyp
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.

sted, utgiver, år, opplag, sider
Springer Verlag , 2015. s. 300-312
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9294
HSV kategori
Identifikatorer
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 (tryckt)OAI: oai:DiVA.org:kth-180171DiVA, id: diva2:893124
Konferanse
23rd Annual European Symposium on Algorithms (ESA) as part of ALGO Conference, SEP 14-16, 2015, Patras, GREECE
Merknad

QC 20160112

Tilgjengelig fra: 2016-01-12 Laget: 2016-01-07 Sist oppdatert: 2018-01-10bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Personposter BETA

Saranurak, Thatchaphol

Søk i DiVA

Av forfatter/redaktør
Saranurak, Thatchaphol
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 413 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf