Randomized search trees
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 540-545
- https://doi.org/10.1109/sfcs.1989.63531
Abstract
A randomized strategy for maintaining balance in dynamically changing search trees that has optimal expected behavior is presented. In particular, in the expected case an update takes logarithmic time and requires fewer than two rotations. Moreover, the update time remains logarithmic, even if the cost of a rotation is taken to be proportional to the size of the rotated subtree. The approach generalizes naturally to weighted trees, where the expected time bounds for accesses and updates again match the worst case time bounds of the best deterministic methods. The balancing strategy and algorithms are exceedingly simple and should be fast in practice.Keywords
This publication has 8 references indexed in Scilit:
- A fast planar partition algorithm. IPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Biased Search TreesSIAM Journal on Computing, 1985
- Self-adjusting binary search treesJournal of the ACM, 1985
- Priority Search TreesSIAM Journal on Computing, 1985
- A unifying look at data structuresCommunications of the ACM, 1980
- A dichromatic framework for balanced treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- Binary Search Trees of Bounded BalanceSIAM Journal on Computing, 1973
- Organization and maintenance of large ordered indexesActa Informatica, 1972