finger search tree
{{Short description|Type of binary search tree}}
{{about|search trees that allow searching from interior nodes|the purely functional data structure|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.
|doi=10.1145/800105.803395|citeseerx=10.1.1.527.7294|s2cid=2414154}}
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.{{cite journal |last1= Huddleston |first2= Kurt |last2= Mehlhorn |year=1982 |title= A New Data Structure for Representing Sorted Lists|journal= Acta Informatica |volume= 17 |issue=2 |pages= 157–184 |doi=10.1007/BF00288968 |s2cid= 10397918 }}
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.{{cite journal |first= Athanasios K.
|last= Tsakalidis |date= 1985 |title=AVL-Trees for Localized Search |journal=Information and Control |volume=67 |issue= 1–3|pages=173–194 |doi=10.1016/S0019-9958(85)80034-6 |doi-access=free }}
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.
File:Performing finger searches on treaps.svg
Treaps, a randomized tree structure proposed by Seidel and Aragon,{{cite journal |last1= Seidel |first1=R.| author-link=Raimund Seidel |last2=Aragon |first2=C.R. |author-link2= Cecilia R. Aragon |date= 1996 |title= Randomized search trees |journal= Algorithmica |volume= 16|issue= 4–5 |pages=464–497 |doi=10.1007/BF01940876 |citeseerx=10.1.1.122.6185|s2cid=9370259}} 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.
{{cite book
| last = Brodal
| first = Gerth Stølting
| year = 2005
| chapter = 11. Finger Search
| chapter-url = http://www.cs.au.dk/~gerth/papers/finger05.pdf
| editor1-last = Mehta
| editor1-first = Dinesh P.
| editor2-last = Sahni
| editor2-first = Sartaj
| editor2-link = Sartaj Sahni
| title = Handbook of Data Structures and Applications
| publisher = Chapman & Hall / CRC Press
| isbn = 978-1584884354
| access-date = 1 January 2013
}} 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.