In computer science, an order statistic tree is a variant of the binary search tree (or more generally, a B-tree[1]) 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 tree
Both 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.
Read full article from Order statistic tree - Wikipedia, the free encyclopedia
No comments:
Post a Comment