BinarySearchTree(BST)


Appendix


Binary Search Tree Definition

Definition

BST is a Linked Structure composed by Node structure, which contains a Comparable Key and two referenced Node called left Node and right Node.All the key of left child node have to be less than it’s parent, and all the key of right child node have to be larger than it’s parent.

Implement

public class BST<Key extends Comparable<? super Key>,Value extends Comparable<? super Value>>{
  private Node root;
  private class Node{

    private Key key;
    private Value val;
    private Node left;
    private Node right;

    private Node(Key key, Value val){
      this.key = key;
      this.val = val;
    }  
  }
}

Following Implementation are based on this class.


Implementation of BST

Size & Height

Recursively build those two methods. For Size, Size(Root) = Size(Left) + Size(right) + 1. For Height, Height(Root) = Max(height(left),height(right)) + 1

The core idea to implement code recursively is assumed the function is correct for all cases, break down the problem to smaller part by thinking out the base case and general case

  1. Size
public int size(){
  return size(Node root);
  //supportive function//
}
private int size(Node x)
{
  if(x == null) return 0;
  return size(x.left) + size(x.right) +1;
}
  1. Height
public int height(){
  return height(Node root);
}

private int height(Node x){
  if(x == null) return 0;
  return Math.max(height(x.left), height(x.right)) +1;
}

Get & Put

  1. Get

Compare each node’s key with the target key, if less, search in the left subtree, if higher, search in the right subtree until it hit the node with the same key, then return the value. If hit the null node ,return null.

public Value get(Key key){
  return get(root, key);
}

private Value get(Node x, Key key){
  if(x == null) return null;
  int cmp = x.key.compareTo(key);
  if(cmp == 0) return x.val;
  else if(cmp <=0) return get(x.right,key);
  else return get(x.left,key);
}
  1. Put

If root is empty, set new node to root. If the target key is equal to some keys in the tree, update the current key. If there is no such key in current tree, put it in the tree

public void put(Key key, Value val){
  return root = put(root,key,val)
}

private Node put(Node x, Key key, Value val){
  if(x == null) return new Node(key,val);
  int cmp = x.key.compareTo(key);
  if(cmp == 0) x.val = val;
  if(cmp < 0) x.right = put(x.right, key,val);
  if(cmp > 0) x.left = put(x.left,key,val);
  return x;
}

Max & Min

The node which is in the leftmost part of the tree has Min key; The node which is in the rightmost part of the tree has MAX key

  1. Max
    public Value max(){
      return max(root);
    }
    private Value max(Node x){
      if(x.left == null) return x.val;
      return max(x.left);
    }
    
  2. Min
public Value min(){
  return min(root);
}
private Value min(Node x){
  if(x.right == null) return x.val;
  return min(x.right);
}

floor & ceiling

  1. floor

If tree is empty, return null; if target key is less than the key of current node, search at left subtree; if target key is larger than the key of current node, it MIGHT be in the right subtree.

public Key floor(Key key){
  return floor(root,key).key;
}

private Node floor(Node x, Key key){
  if(x == null) return null;
  int cmp = x.key.compareTo(key);
  if(cmp == 0) return x;
  if(cmp >0) return floor(x.left,key);
  else
  Node t = floor(x.right,key);
  if(t!=null) return t;
  else return x;
}
  1. Ceiling

If tree is empty, return null; if target key is higher than the key of current node, search at right subtree; if target key is less than the key of current node, it MIGHT be in the left subtree.

public Key Ceiling(Key key){
  return Ceiling(root,key).key;
}

private Node Ceiling(Node x, Key key){
  if(x == null) return null;
  int cmp = x.key.compareTo(key);
  if(cmp == 0) return x;
  if(cmp <0) return Ceiling(x.right,key);
  else
  Node t = Ceiling(x.left,key);
  if(t!=null) return t;
  else return x;
}

Rank & Select

  1. Rank

Rank return the number of keys that are less than itself. If the target key is less than the key of current node, return the size of its left subtree; If higher, return 1 + size(x.left) + rank(key,x.right)

public int rank(Key key){
  return rank(root, key);
}

private int rank(Node x, Key key){
  if(x =null) return 0;
  int cmp = x.key.compareTo(key);
  if (cmp == 0) return size(x.left)
  else if(cmp > 0) return rank(x.left, key);
  else return rank(x.right,key) + size(x.left) +1;
}
  1. Select

Return the key of node which rank is specified by user

public Key select(int s){
  return select(root,s).key;
}

private Key select(Node x,int s){
  if(x == null) return null;
  int t = size(x.left);
  if(s > t) select(x.right, s-t-1);
  else if(s<t) select(x.left, s)
}

Delete

Following the step to do the delete

  • Find the node(Y) of which key needs to be deleted.

  • In the right subtree of Y, find the node(Z) with min key.

  • Delete Z in tree which root is Y.

  • Linked Z:

    • Z.left = Y.left.

    • Z.right = Delete(Z).

public void delete(Key key){
  root = delete(root, key);
}

private Node delete(Node x, Key key){
  if(x == null) return null;
  int cmp = x.key.compareTo(key);
  if(cmp < 0) x.right = delete(x.right, key);
  else if (cmp >0) x.left = delete(x.left,key);
  else
  {
  if(x.left == null) return x.right;
  if(x.right == null) return x.left
  Node Y = x;
  Z = min(Y.right);
  Z.right = Y.Delete(Z);
  Z.left = Y.left;
  }
  return x
}

Range Queries

Return the key between lower bound and higher bound, Use iterable interface to build the keys function

//return the BTS in order
public Iterable<Key> keys(){
  return keys(min(),max());
}

public Iterable<Key> keys(int lo, int hi){
  Queue<Key> queue = new Queue<Key>();
  keys(root, queue, lo, hi);
  return queue;
}

public Iterable<Key> keys(Node x, Queue<Key> queue, int lo, int hi){
  if(x==null) return
  int cmplo = lo.compareTo(x.key);
  int cmphi = hi.compareTo(x.key);
  if(cmplo < 0) keys(x.left, queue,lo, hi);
  if(cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key);
  if(cmphi >0) keys(x.right, queue,lo,hi);
}

Iteration Order

Post Order

process left subtree first, then right subtree, finally root itself

In Order

process left subtree first, then root itself, finally right subtree

  1. recursive method

To implement Iterable function recursively, we use queue as the container to hold the key

public Iterable<Key> keysinorder(){
  Queue<Key> q = new Queue<Key>();
  return keysinorder(root,q);
}

private Iterable<Key> keysinorder(Node x, Queue q){
  if(x == null) return q;
  q = keysinorder(x.left, q);
  q.enqueue(x.key);
  q = keysinorder(x.right,q);  
}
  1. Using stack
public Iterable<Key> keysinorder(Node x){
  ArrayList<Key> out = new ArrayList();
  if(x == null) return out;
  Stack<Key> stack = new Stack<Key>();
  Node p = x;
  while(!stack.isEmpty() || p != null){
    if(p != null){
      stack.push(p.key);
      p = p.left;
    }else{
      Node t = stack.pop();
      out.add(t.key);
      p = p.right
    }
  }
}

Pre Order

process root itself first, then left subtree, finally right subtree