public class binarytree<Value> {
private Node root = null;
private class Node{
private Value val;
private int key;
private Node left,right;
private int N; //the number of the all nodes of its child nodes and itself
//private int num;//the number
public Node(Value val,int key,int N){
this.val = val; this.N = N;this.key = key;
}
}
public void walk(Node x) { //O(n) time
if(x!=null){
walk(x.left);
System.out.println(x.key);
walk(x.right);
}
}
public Value get(Node x,int key){
if(x == null){
return null;
}
if(x.key>key){
return get(x.left,key);
}
else if(x.key < key){
return get(x.right,key);
}
else{
return x.val;
}
}
private Node min(Node x){
if(x.left == null) return x;
return min(x.left);
}
private Node deletemin(Node x){
if(x.left == null){return x.right;}
x.left = deletemin(x.left);
x.N = size(x.left) + size(x.right) + 1;
return x;
}
private Node delete(Node x,int key){
if(key < x.key) x.left = delete(x.left,key);
else if(key > x.key) x.right = delete(x.right,key);
else{
if(x.left == null) return x.right;
if(x.right == null) return x.left;
Node t = x;
x = min(t.right);
x.right = deletemin(t.right);
x.left = t.left;
}
x.N = size(x.left) +size(x.right)+1;
return x;
}
private Node put(Node x,Value val,int key){
if(x == null) return new Node(val,key,1);
if(key < x.key) x.left = put(x.left,val,key);
else if(key > x.key) x.right = put(x.right,val,key);
else x.key = key;
x.N = size(x.left) + size(x.right) + 1;
return x;
}
private int size(Node x){
if(x == null){return 0;}
else return x.N;
}
private Node select(Node x,int k){
if(x == null) return null;
int t = size(x.left);
if (t>k) return select(x.left,k);
else if(t<k) return select (x.right,k-t-1);
else return x;
}
}
