# basic binary search tree implementation

• October 11th, 2013, 02:20 AM
asuna
basic binary search tree implementation
public class BST<Key extends Comparable<Key>,Value>{

private Node root;

private class Node{
private Key key;
private Value val;
private Node left, right;
private int N;

public Node(Key key,Value val,int N)
{ this.key = key; this.val=val; this.N=N;}
}
return size(root);
}
public int size(Node x){
if(x==null) return 0;
else
return x.N;
public int size(){
}
public Value get(Key key){
return get(root,key);
}
private Value get(Node x, Key key){
if(x==null) return null;
int cmp = key.compareTo(x.key);
if (cmp<0) return get(x.left,key);
else if (cmp<0) return get(x.right,key);
else return x.val;
}
public Node put(Key key,Value val){
root = put(root,Key,val);
}
private Node put(Node x, Key key, Value val){
if(x==null ) return new Node(key ,val,1);
int cmp =key.compareTo(x.key);
if(cmp<0) x.left= put(x.left,key,val);
else if(cmp>0) x.right= put(x.right,key,val);
else x.val=val;
x.N=size(x.left)+size(x.right)+1;
return x;
}

public Key min(){
return min(root).key;
}
private Node min(Node x){
if(x.left==null) return x;
return min(x.left);
}
public Key max(){
return min(root).key;
}
private Node max(Node x){
if(x.right==null) return x;
return max(x.right);
}
public Key select(int k){
return select(root,k).key;
}
private Node select(Node x,int k)
{
if(x=null)return null;
int t=size(x.left);
if(t>k) return(x.left,k);
else if(t<k) return(x.right,k-t-1);
else return x;
}
public int rank(Key key,Node x)
{ return rank(key,root); }
private int rank(Key key,Node x){
if(x==null) return 0;
int cmp =key.compareTo(x.key);
if(cmp<0) return rank(key,x.left);
else if(cmp>0) return 1+size(x.left)+rank(key,x.right);
else return size(x.left);
}
public void deleteMin(){
root= deleteMin(root);
}
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;
}

public void delete(Key key){
root=delete(root,key)
}
private Node delete(Node x,Key key){
if(x==null) return null;
int cmp = key.compareTo(x.key);
if(cmp<0)x.left = delete(x.left,key);
else if(cmp>0) x.right= delete(x.right,key);
else{
if(x.right==null) return x.left;
if(x.left==null) return x.right;
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;
}

}

--- Update ---

ive got this from the internet but when i debug it.. it does'nt work (many errors ! what should i do)
• October 11th, 2013, 06:52 AM
Norm
Re: basic binary search tree implementation