Finger search tree
In computer science, finger search trees are a type of binary search tree that keeps pointers to interior nodes, called fingers. The fingers speed up searches, insertions, and deletions for elements close to the fingers, giving amortized [Big Big O notation|O notation|O] lookups, and amortized O insertions and deletions. It should not be confused with a finger tree nor a splay tree, although both can be used to implement finger search trees.
Guibas et al.
introduced finger search trees, by building upon B-trees. The original version supports finger searches in O time, where d is the number of elements between the finger and the search target. Updates take O time, when only O moveable fingers are maintained. Moving a finger p positions requires O time. Huddleston and Mehlhorn refined this idea as level-linked B-trees.
Tsakalidis proposed a version based on AVL trees that facilitates searching from the ends of the tree; it can be used to implement a data structure with multiple fingers by using multiple of such trees.
To perform a finger search on a binary tree, the ideal way is to start from the finger, and search upwards to the root, until we reach the least common ancestor, also called the turning node, of x and y, and then go downwards to find the element we're looking for. Determining if a node is the ancestor of another is non-trivial.
Treaps, a randomized tree structure proposed by Seidel and Aragon, has the property that the expected path length of two elements of distance d is O. For finger searching, they proposed adding pointers to determine the least common ancestor quickly, or in every node maintain the minimum and maximum values of its subtree.
A book chapter has been written that covers finger search trees in depth. In which, Brodal suggested an algorithm to perform finger search on treaps in O time, without needing any extra bookkeeping information; this algorithm accomplishes this by concurrently searching downward from the last candidate LCA.