Randomized search trees
C. Aragon, Raimund Seidel · Annual Symposium on Foundations of Computer Science · 1989
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.>
Cited by 153 works. doi:10.1109/sfcs.1989.63531
Authors
References
- Organization and maintenance of large ordered indexes
- Self-adjusting binary search trees
- AN ALGORITHM FOR THE ORGANIZATION OF INFORMATION
- Skip lists: a probabilistic alternative to balanced trees
- A dichromatic framework for balanced trees
- Binary Search Trees of Bounded Balance
- Priority Search Trees
- Fast Multiple-Precision Evaluation of Elementary Functions
- A unifying look at data structures
- Multi-dimensional searching and computational geometry