Finger search tree

This article is about search trees that allow searching from interior nodes. For the purely functional data structure, see finger 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 O(log n) lookups, and amortized O(1) 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.[1] introduced finger search trees, by building upon B-trees. The original version supports finger searches in O(log d) time, where d is the number of elements between the finger and the search target. Updates take O(1) time, when only O(1) moveable fingers are maintained. Moving a finger p positions requires O(log p) time. Huddleston and Mehlhorn refined this idea as level-linked B-trees.[2]

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.[3]

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 turning node[3] or the least common ancestor[4][5] 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.

An example of performing finger search on a treap.

Treaps, a randomized tree structure proposed by Seidel and Aragon,[5] has the property that the expected path length of two elements of distance d is O(log d). For finger searching, they proposed adding pointers to determine the least common ancestor(LCA) 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.[4] In which, Brodal suggested an algorithm to perform finger search on treaps in O(log d) time, without needing any extra bookkeeping information; this algorithm accomplishes this by concurrently searching downward from the last candidate LCA.

See also

References

  1. ↑ Guibas, L.J. (1977), "A new representation for linear lists", Proceedings of the ninth annual ACM symposium on Theory of computing: 49–60
  2. ↑ Huddleston; Mehlhorn, Kurt (1982). "A New Data Structure for Representing Sorted Lists". Acta Informatica 17 (2): 157–184. doi:10.1007/BF00288968.
  3. ↑ 3.0 3.1 Tsakalidis, Athanasios K. (1985). "AVL-Trees for Localized Search". Information and Control 67: 173–194. doi:10.1016/S0019-9958(85)80034-6.
  4. ↑ 4.0 4.1 Brodal, Gerth Stølting (2005). "11. Finger Search" (PDF). In Mehta, Dinesh P.; Sahni, Sartaj. Handbook of Data Structures and Applications. Chapman & Hall / CRC Press. ISBN 1584884355. Retrieved 1 January 2013.
  5. ↑ 5.0 5.1 Seidel, R.; Aragon, C.R. (1996). "Randomized search trees". Algorithmica 16 (4-5): 464–497. doi:10.1007/BF01940876.