Finger search tree
Nowadays, Finger search tree is a topic that has gained great relevance in modern society. As time progresses, many people are interested in this topic and want to delve deeper into it. And it is no wonder, since Finger search tree arouses the curiosity and interest of a wide spectrum of people, from experts in the field to those who simply seek information. That is why in this article we are going to delve into the exciting world of Finger search tree, exploring its various facets and analyzing its impact today. Without a doubt, this article will serve as a starting point for those who want to learn more about Finger search tree and delve into its fascinating universe.
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 least common ancestor,[4][5] also called the turning node,[3] 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,[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
- ^ Guibas, L.J. (1977). "A new representation for linear lists". Proceedings of the ninth annual ACM symposium on Theory of computing - STOC '77. pp. 49–60. CiteSeerX 10.1.1.527.7294. doi:10.1145/800105.803395. S2CID 2414154.
- ^ Huddleston; Mehlhorn, Kurt (1982). "A New Data Structure for Representing Sorted Lists". Acta Informatica. 17 (2): 157–184. doi:10.1007/BF00288968. S2CID 10397918.
- ^ a b Tsakalidis, Athanasios K. (1985). "AVL-Trees for Localized Search". Information and Control. 67 (1–3): 173–194. doi:10.1016/S0019-9958(85)80034-6.
- ^ a b Brodal, Gerth Stølting (2005). "11. Finger Search" (PDF). In Mehta, Dinesh P.; Sahni, Sartaj (eds.). Handbook of Data Structures and Applications. Chapman & Hall / CRC Press. ISBN 978-1584884354. Retrieved 1 January 2013.
- ^ a b Seidel, R.; Aragon, C.R. (1996). "Randomized search trees". Algorithmica. 16 (4–5): 464–497. CiteSeerX 10.1.1.122.6185. doi:10.1007/BF01940876. S2CID 9370259.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |