O'Reilly logo

Handbook of Data Structures and Applications, 2nd Edition by Sartaj Sahni, Dinesh P. Mehta

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

TreapsSkip Lists

12.5Applications

Optimal Merging and Set OperationsArbitrary Merging OrderList SplittingAdaptive 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required