Self-adjusting binary trees
Daniel D. Sleator, Robert Endre Tarjan · 1983
We use the idea of self-adjusting trees to create new, simple data structures for priority queues (which we call heaps) and search trees. Unlike other efficient implementations of these data structures, self-adjusting trees have no balance condition. Instead, whenever the tree is accessed, certain adjustments take place. (In the case of heaps, the adjustment is a sequence of exchanges of children, in the case of search trees the adjustment is a sequence of rotations.) Self-adjusting trees are efficient in an amortized sense: any particular operation may be slow but any sequence of operations must be fast.
Cited by 109 works. doi:10.1145/800061.808752 Open-access PDF
Authors
References
- The Art of Computer Programming
- The Design and Analysis of Computer Algorithms
- The Art of Computer Programming: Volume 3: Sorting and Searching
- A Discipline of Programming
- The Art of Computer Programming
- The Art of Computer Programming. Volume 1: Fundamental Algorithms.
- Data Structures and Network Algorithms
- AN ALGORITHM FOR THE ORGANIZATION OF INFORMATION
- A data structure for dynamic trees
- On self-organizing sequential search heuristics