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:
http://blueocean-penn.blogspot.com/2015/01/order-statistics-binary-search-tree.html
https://github.com/aorzecho/ds/blob/master/src/main/java/org/aorzecho/ds/java/util/TreeMap.java
final Entry<K,V> getIthEntry(Entry<K,V> entry, int i) {
if (i > size || i<=0)
throw new IndexOutOfBoundsException("Size is " + size
+ ", requested i=" + i + " out of bounds");
int r = 1;
if (entry.left != null)
r += entry.left.size;
if (i == r)
return entry;
else if (i < r)
return getIthEntry(entry.left, i);
else
return getIthEntry(entry.right, i-r);
}
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;
int size = 1;
}
Read full article from Order statistic tree - Wikipedia, the free encyclopedia
- 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
http://blueocean-penn.blogspot.com/2015/01/order-statistics-binary-search-tree.html
Order statistics binary search tree. This is probably one of the simplest high order binary search tree. It is just like binary search tree, except we store additional information in the node, usually this additional information can be computed recursively and bubble-up approach by taking advantaging of the tree's inherent characteristics.
For example, we can store the size of subtree rooted at each node.
Node.size = Node.left.size + Node.right.size
Once we have that data, then we can support the following two operations in O(lgN) time.
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
public class OrderStatisticTreeQ {
public class Node {
int data;
int size;
Node left;
Node right;
}
/*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
*/
//k starts at 0
public int findKthSmallest(Node root, int k){
int level = k;
Node curr = root;
while(curr!=null){
int leftSize = (curr.left ==null? 0 : curr.left.size);
if(level == leftSize )
return curr.data;
if(leftSize > level)
curr = curr.left;
else{
curr = curr.right;
level = level - (leftSize+1);
}
if(level == leftSize )
return curr.data;
if(leftSize > level)
curr = curr.left;
else{
curr = curr.right;
level = level - (leftSize+1);
}
}
return -1;
}
//index starts at 0
public int findIndexFor(Node root, int value){
Node curr = root;
int passed = 0;
while(curr!=null){
if(curr.data == value){
return (curr.left==null?0:curr.left.size) + passed;
}else if(curr.data > value){
curr = curr.left;
}else{
passed + = (curr.left==null?0:curr.left.size) + 1;
curr = curr.right;
}
}
return -1;
}
}
final Entry<K,V> getIthEntry(Entry<K,V> entry, int i) {
if (i > size || i<=0)
throw new IndexOutOfBoundsException("Size is " + size
+ ", requested i=" + i + " out of bounds");
int r = 1;
if (entry.left != null)
r += entry.left.size;
if (i == r)
return entry;
else if (i < r)
return getIthEntry(entry.left, i);
else
return getIthEntry(entry.right, i-r);
}
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;
int size = 1;
}
Read full article from Order statistic tree - Wikipedia, the free encyclopedia
