Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Finger_search_tree> ?p ?o }
Showing triples 1 to 42 of
42
with 100 triples per page.
- Finger_search_tree abstract "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.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.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 turning node or the least common ancestor 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(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. 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.".
- Finger_search_tree thumbnail Performing_finger_searches_on_treaps.svg?width=300.
- Finger_search_tree wikiPageID "38136820".
- Finger_search_tree wikiPageLength "4350".
- Finger_search_tree wikiPageOutDegree "12".
- Finger_search_tree wikiPageRevisionID "612278231".
- Finger_search_tree wikiPageWikiLink AVL_tree.
- Finger_search_tree wikiPageWikiLink Athanasios_Tsakalidis.
- Finger_search_tree wikiPageWikiLink B-tree.
- Finger_search_tree wikiPageWikiLink Big_O_notation.
- Finger_search_tree wikiPageWikiLink Binary_search_tree.
- Finger_search_tree wikiPageWikiLink Category:Search_algorithms.
- Finger_search_tree wikiPageWikiLink Category:Trees_(data_structures).
- Finger_search_tree wikiPageWikiLink Finger_search.
- Finger_search_tree wikiPageWikiLink Finger_tree.
- Finger_search_tree wikiPageWikiLink Splay_tree.
- Finger_search_tree wikiPageWikiLink Treap.
- Finger_search_tree wikiPageWikiLink File:Performing_finger_searches_on_treaps.svg.
- Finger_search_tree wikiPageWikiLinkText "Finger search tree".
- Finger_search_tree wikiPageWikiLinkText "finger search tree".
- Finger_search_tree hasPhotoCollection Finger_search_tree.
- Finger_search_tree wikiPageUsesTemplate Template:About.
- Finger_search_tree wikiPageUsesTemplate Template:CS-Trees.
- Finger_search_tree wikiPageUsesTemplate Template:Datastructure-stub.
- Finger_search_tree wikiPageUsesTemplate Template:Reflist.
- Finger_search_tree subject Category:Search_algorithms.
- Finger_search_tree subject Category:Trees_(data_structures).
- Finger_search_tree hypernym Tree.
- Finger_search_tree type Article.
- Finger_search_tree type Plant.
- Finger_search_tree type Article.
- Finger_search_tree type Structure.
- Finger_search_tree type Technique.
- Finger_search_tree comment "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.introduced finger search trees, by building upon B-trees.".
- Finger_search_tree label "Finger search tree".
- Finger_search_tree sameAs درخت_جستجو_بندانگشتی.
- Finger_search_tree sameAs m.0pd99nb.
- Finger_search_tree sameAs Q5450242.
- Finger_search_tree sameAs Q5450242.
- Finger_search_tree wasDerivedFrom Finger_search_tree?oldid=612278231.
- Finger_search_tree depiction Performing_finger_searches_on_treaps.svg.
- Finger_search_tree isPrimaryTopicOf Finger_search_tree.