Handbook of Data Structures and Applications, 2nd Edition

12

Finger Search Trees*

Gerth Stølting Brodal

University of Aarhus

12.1Finger Searching

12.2Dynamic Finger Search Trees

12.3Level Linked (2,4)-Trees

12.4Randomized Finger Search Trees

Treaps•Skip Lists

12.5Applications

Optimal Merging and Set Operations•Arbitrary Merging Order•List Splitting•Adaptive Merging and Sorting

Acknowledgments

References

12.1Finger Searching

One of the most studied problems in computer science is the problem of maintaining a sorted sequence of elements to facilitate efficient searches. The prominent solution to the problem is to organize the sorted sequence as a balanced search tree, enabling insertions, deletions and searches in logarithmic time. Many different search trees have been developed and studied intensively ...