Abstract
In 1985, Sleator and Tarjan introduced the splay tree, a self-adjusting binary search tree algorithm. Splay trees were conjectured to perform within a constant factor as any offline rotation-based search tree algorithm on every sufficiently long sequence—any binary search tree algorithm that has this property is said to be dynamically optimal. However, currently neither splay trees nor any other tree algorithm is known to be dynamically optimal. Here we survey the progress that has been made in the almost thirty years since the conjecture was first formulated, and present a binary search tree algorithm that is dynamically optimal if any binary search tree algorithm is dynamically optimal.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing 8(1), 121–164 (2012)
Allenand, B., Ian Munro, J.: Self-organizing binary search trees. J. ACM 25(4), 526–535 (1978)
Badoiu, M., Cole, R., Demaine, E.D., Iacono, J.: A unified access bound on comparison-based dynamic dictionaries. Theor. Comput. Sci. 382(2), 86–96 (2007)
Bose, P., Collette, S., Fagerberg, R., Langerman, S.: De-amortizing binary search trees. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 121–132. Springer, Heidelberg (2012)
Blum, A., Chawla, S., Kalai, A.: Static optimality and dynamic search-optimality in lists and trees. Algorithmica 36(3), 249–260 (2003)
Bose, P., Douïeb, K., Iacono, J., Langerman, S.: The power and limitations of static binary search trees with lazy finger. CoRR, abs/1304.6897 (2013)
Cole, R., Mishra, B., Schmidt, J.P., Siegel, A.: On the dynamic finger conjecture for splay trees. part i: Splay sorting log n-block sequences. SIAM J. Comput. 30(1), 1–43 (2000)
Cole, R.: On the dynamic finger conjecture for splay trees. part ii: The proof. SIAM J. Comput. 30(1), 44–85 (2000)
Derryberry, J.: Adaptive Binary Search Trees. PhD thesis, CMU (2009)
Demaine, E.D., Harmon, D., Iacono, J., Kane, D.M., Patrascu, M.: The geometry of binary search trees. In: Mathieu, C. (ed.) SODA, pp. 496–505. SIAM (2009)
Demaine, E.D., Harmon, D., Iacono, J., Patrascu, M.: Dynamic optimality - almost. SIAM J. Comput. 37(1), 240–251 (2007)
Demaine, E.D., Iacono, J., Langerman, S., Özkan, Ö.: Combining binary search trees. CoRR, abs/1304.7604 (2013)
Derryberry, J.C., Sleator, D.D.: Skip-splay: Toward achieving the unified bound in the bst model. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 194–205. Springer, Heidelberg (2009)
Fox, K.: Upper bounds for maximally greedy binary search trees. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 411–422. Springer, Heidelberg (2011)
Harmon, D.: New Bounds on Optimal Binary Search Trees. PhD thesis, MIT (2006)
Lucas, J.M.: Canonical forms for competitive binary search tree algorithms. Technical Report DCS-TR-250, Rutgers University (1988)
Sleator, D.: Achieving the unified bound in the bst model. In: 5th Bertinoro Workshop on Algorithms and Data Structures. Talk (2011)
Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202–208 (1985)
Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652–686 (1985)
Subramanian, A.: An explanation of splaying. J. Algorithms 20(3), 512–525 (1996)
Wilber, R.E.: Lower bounds for accessing binary search trees with rotations. SIAM J. Comput. 18(1), 56–67 (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Iacono, J. (2013). In Pursuit of the Dynamic Optimality Conjecture. In: Brodnik, A., López-Ortiz, A., Raman, V., Viola, A. (eds) Space-Efficient Data Structures, Streams, and Algorithms. Lecture Notes in Computer Science, vol 8066. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40273-9_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-40273-9_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40272-2
Online ISBN: 978-3-642-40273-9
eBook Packages: Computer ScienceComputer Science (R0)