Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Order_statistic_tree> ?p ?o. }
Showing items 1 to 15 of
15
with 100 items per page.
- Order_statistic_tree abstract "In computer science, an order statistic tree is a variant of the binary search tree (or more generally, a B-tree) that supports two additional operation beyond insertion, lookup and deletion: Select(i) — find the i'th smallest element stored in the tree Rank(x) – find the rank of element x in the tree, i.e. its index in the sorted list of elements of the treeBoth operations can be performed in O(log n) time in the average case; when a self-balancing tree is used as the base data structure, this bound also applies in the worst case.To turn a regular search tree into an order statistic tree, the nodes of the tree need to store one additional value, which is the size of the subtree rooted at that node (i.e., the number of nodes below it). All operations that modify the tree must adjust this information to preserve the invariant thatsize[x] = size[left[x]] + size[right[x]] + 1where size[nil] = 0 by definition. Select can then be implemented asfunction Select(t, i) // Returns the i'th element (zero-indexed) of the elements in t r ← size[left[t]] if i = r return key[t] else if i < r return Select(left[t], i) else return Select(right[t], i - (r + 1))".
- Order_statistic_tree wikiPageExternalLink OrderStatisticsTree.
- Order_statistic_tree wikiPageExternalLink blist.
- Order_statistic_tree wikiPageID "36548922".
- Order_statistic_tree wikiPageRevisionID "602373896".
- Order_statistic_tree hasPhotoCollection Order_statistic_tree.
- Order_statistic_tree subject Category:Binary_trees.
- Order_statistic_tree subject Category:Selection_algorithms.
- Order_statistic_tree comment "In computer science, an order statistic tree is a variant of the binary search tree (or more generally, a B-tree) that supports two additional operation beyond insertion, lookup and deletion: Select(i) — find the i'th smallest element stored in the tree Rank(x) – find the rank of element x in the tree, i.e.".
- Order_statistic_tree label "Order statistic tree".
- Order_statistic_tree sameAs m.0kfx8lh.
- Order_statistic_tree sameAs Q7100701.
- Order_statistic_tree sameAs Q7100701.
- Order_statistic_tree wasDerivedFrom Order_statistic_tree?oldid=602373896.
- Order_statistic_tree isPrimaryTopicOf Order_statistic_tree.