The power and limitations of static binary search trees with lazy finger

Presenjit Bose; Karim Douïeb; John Iacono; Stefan Langerman

doi:10.1007/978-3-319-13075-0_15

The power and limitations of static binary search trees with lazy finger

Presenjit Bose, Karim Douïeb, John Iacono, Stefan Langerman

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

A static binary search tree where every search starts from where the previous one ends (lazy finger) is considered. Such a search method is more powerful than that of the classic optimal static trees, where every search starts from the root (root finger), and less powerful than when rotations are allowed—where finding the best rotation based tree is the topic of the dynamic optimality conjecture of Sleator and Tarjan. The runtime of the classic root-finger tree can be expressed in terms of the entropy of the distribution of the searches, but we show that this is not the case for the optimal lazy finger tree. A non-entropy based asymptotically-tight expression for the runtime of the optimal lazy finger trees is derived, and a dynamic programming-based method is presented to compute the optimal tree.

Original language	English (US)
Title of host publication	Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings
Editors	Hee-Kap Ahn, Chan-Su Shin
Publisher	Springer Verlag
Pages	181-192
Number of pages	12
ISBN (Electronic)	9783319130743
DOIs	https://doi.org/10.1007/978-3-319-13075-0_15
State	Published - 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8889
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-13075-0_15

Cite this

Bose, P., Douïeb, K., Iacono, J., & Langerman, S. (2014). The power and limitations of static binary search trees with lazy finger. In H.-K. Ahn, & C.-S. Shin (Eds.), Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings (pp. 181-192). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8889). Springer Verlag. https://doi.org/10.1007/978-3-319-13075-0_15

The power and limitations of static binary search trees with lazy finger. / Bose, Presenjit; Douïeb, Karim; Iacono, John et al.
Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings. ed. / Hee-Kap Ahn; Chan-Su Shin. Springer Verlag, 2014. p. 181-192 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8889).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Bose, P, Douïeb, K, Iacono, J & Langerman, S 2014, The power and limitations of static binary search trees with lazy finger. in H-K Ahn & C-S Shin (eds), Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8889, Springer Verlag, pp. 181-192. https://doi.org/10.1007/978-3-319-13075-0_15

Bose P, Douïeb K, Iacono J, Langerman S. The power and limitations of static binary search trees with lazy finger. In Ahn HK, Shin CS, editors, Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings. Springer Verlag. 2014. p. 181-192. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-13075-0_15

Bose, Presenjit ; Douïeb, Karim ; Iacono, John et al. / The power and limitations of static binary search trees with lazy finger. Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings. editor / Hee-Kap Ahn ; Chan-Su Shin. Springer Verlag, 2014. pp. 181-192 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{f9ee7a92a3a344fd877fc7a0d7e1c2ca,

title = "The power and limitations of static binary search trees with lazy finger",

abstract = "A static binary search tree where every search starts from where the previous one ends (lazy finger) is considered. Such a search method is more powerful than that of the classic optimal static trees, where every search starts from the root (root finger), and less powerful than when rotations are allowed—where finding the best rotation based tree is the topic of the dynamic optimality conjecture of Sleator and Tarjan. The runtime of the classic root-finger tree can be expressed in terms of the entropy of the distribution of the searches, but we show that this is not the case for the optimal lazy finger tree. A non-entropy based asymptotically-tight expression for the runtime of the optimal lazy finger trees is derived, and a dynamic programming-based method is presented to compute the optimal tree.",

author = "Presenjit Bose and Karim Dou{\"i}eb and John Iacono and Stefan Langerman",

note = "Funding Information: Research for P. Bose supported in part by NSERC. Funding Information: Research partially completed at NYU School of Engineering with support from NSF grant CCF-1319648. Research partially completed at Universit{\'e} Libre de Bruxelles with support from FNRS. Research partially completed at and supported by MADALGO, a center of the Danish National Research Foundation. Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2014.",

year = "2014",

doi = "10.1007/978-3-319-13075-0_15",

language = "English (US)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "181--192",

editor = "Hee-Kap Ahn and Chan-Su Shin",

booktitle = "Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings",

}

TY - CHAP

T1 - The power and limitations of static binary search trees with lazy finger

AU - Bose, Presenjit

AU - Douïeb, Karim

AU - Iacono, John

AU - Langerman, Stefan

N1 - Funding Information: Research for P. Bose supported in part by NSERC. Funding Information: Research partially completed at NYU School of Engineering with support from NSF grant CCF-1319648. Research partially completed at Université Libre de Bruxelles with support from FNRS. Research partially completed at and supported by MADALGO, a center of the Danish National Research Foundation. Publisher Copyright: © Springer International Publishing Switzerland 2014.

PY - 2014

Y1 - 2014

N2 - A static binary search tree where every search starts from where the previous one ends (lazy finger) is considered. Such a search method is more powerful than that of the classic optimal static trees, where every search starts from the root (root finger), and less powerful than when rotations are allowed—where finding the best rotation based tree is the topic of the dynamic optimality conjecture of Sleator and Tarjan. The runtime of the classic root-finger tree can be expressed in terms of the entropy of the distribution of the searches, but we show that this is not the case for the optimal lazy finger tree. A non-entropy based asymptotically-tight expression for the runtime of the optimal lazy finger trees is derived, and a dynamic programming-based method is presented to compute the optimal tree.

AB - A static binary search tree where every search starts from where the previous one ends (lazy finger) is considered. Such a search method is more powerful than that of the classic optimal static trees, where every search starts from the root (root finger), and less powerful than when rotations are allowed—where finding the best rotation based tree is the topic of the dynamic optimality conjecture of Sleator and Tarjan. The runtime of the classic root-finger tree can be expressed in terms of the entropy of the distribution of the searches, but we show that this is not the case for the optimal lazy finger tree. A non-entropy based asymptotically-tight expression for the runtime of the optimal lazy finger trees is derived, and a dynamic programming-based method is presented to compute the optimal tree.

UR - http://www.scopus.com/inward/record.url?scp=84921802410&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84921802410&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-13075-0_15

DO - 10.1007/978-3-319-13075-0_15

M3 - Chapter

AN - SCOPUS:84921802410

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 181

EP - 192

BT - Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings

A2 - Ahn, Hee-Kap

A2 - Shin, Chan-Su

PB - Springer Verlag

ER -

The power and limitations of static binary search trees with lazy finger

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this