Abstract
In (A. Subramanian, An Explanation of Splaying, Proceedings of the 14th Foundations of Software Technology and Theoretical Computer Science, LNCS Springer Verlag 880 354–365), D. Sleator suggested the following heuristic for self adjusting binary search trees: Every time an access is made, restructure the entire path from the root of the search tree to the accessed node into a balanced binary search tree on those nodes, and place all other subtrees rooted at the children of the nodes in the access path in their proper positions. We show that the method has an O(log n log log n/ log log log n) amortized complexity.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
B. Allen and I. Munro, Self-organizing Search Trees, Journal of the ACM 25 (1978) 526–535.
J. R. Bitner, Heuristics that dynamically organize data structures, SIAM Journal of Computing 8 (1979) 82–110.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, The MIT Press, Cambridge, Massachusetts (1990).
M. L. Fredman, R. Sedgewick, D. D. Sleator and R. E. Tarjan, The Pairing Heap: A New Form of Self-Adjusting Heap, Algorithmica 1 (1986) 111–129.
D. E. Knuth, The Art of Computer Programming, Vol 3: Sorting and Searching, Addison-Wesley, Reading, Massachusettes (1973).
D. D. Sleator, R. E. Tarjan, and Thurston, Rotation distance, triangulations and hyperbolic geometry, Proceedings of the 18th ACM Symposium on Theory of Computing (1986) 122–135.
D. D. Sleator and R. E. Tarjan, Self-adjusting Binary Search Trees, Journal of the ACM 32 (1985) 652–686.
A. Subramanian, An Explanation of Splaying, Proceedings of the 14th Foundations of Software Technology and Theoretical Computer Science, LNCS Springer Verlag 880 354–365.
R. E. Tarjan, Amortized Computational Complexity, SIAM Journal of Algebraic and Discrete Mathematics, 6 (2) (1985) 306–318.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Balasubramanian, R., Raman, V. (1995). Path balance heuristic for self-adjusting binary search trees. In: Thiagarajan, P.S. (eds) Foundations of Software Technology and Theoretical Computer Science. FSTTCS 1995. Lecture Notes in Computer Science, vol 1026. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60692-0_59
Download citation
DOI: https://doi.org/10.1007/3-540-60692-0_59
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60692-5
Online ISBN: 978-3-540-49263-4
eBook Packages: Springer Book Archive