1. Symbol tables

1. Symbol tables：插入鍵值對；給定一個key，可以搜索對應的value

2. Conventions:

   • value不會是null
   • get() 返回null，如果key不存在
   • put() 重寫舊的value，如果同一個key有一個新的value

3. Binary search

   public Value get(Key key){
     if(isEmpty()){
       return null;
     }
     int i = rank(key);
     if(i < n && keys[i].compareTo(key) == 0){
       return vals[i];
     }else{
       return null;
     }
   }
   
   private int rank(Key key){
     int lo = 0, hi = n-1;
     while(lo <= hi){
       int mid = (lo + hi) / 2;
       int cmp = key.compareTo(keys[mid]);
       if(cmp < 0){
         hi = mid -1;
       }else if(cmp > 0){
         lo = mid + 1;
       }else{ // cmp == 0
         return mid;
       }
     }
     return lo;
   }
   

2. Binary search trees

1. 定義（BST）：對稱排序的二叉樹

   • 每個節(jié)點Node都有一個鍵值Key， 每個Key都比它左邊的subtree大，比它右邊的subtree小
   • Node：有一個key，一個value，兩個引用指向left和right的subtree
   • Search: 如果比節(jié)點小，向左比；如果比節(jié)點大，向右比；一樣大，search hit
   • Deletion:
     • 刪除最小的：向左找，直到找到一個node，它的left-link是null（說明這個node是本tree最小），然后用這個node的right-link代替它，最后update數(shù)目
     • 普通刪除：
       • 0 child：這個node的parent-link直接用null代替
       • 1 child：這個node的parent-link與它的child相連
       • 2 children：找的這個node的右邊subtree的最小值，將這個最小值作為繼承者，然后刪除這個最小值

2. BST performance:

   • N個獨立不同的的Key以隨機的順序插入BST, 期望的compares（ for a search/insert）：~ 2 ln N.

     implemen	guarantee	average	ordered ops?	operations on keys
     sequential search (unordered list)	Search: N insert: N delete: N	Search: N/2 insert: N delete: N/2	No	equals()
     binary search (ordered array)	Search: lgN insert: N delete: N	Search: lgN insert: N/2 delete: N/2	Yes	compareTo()
     BST	Search: N insert: N delete: N	Search: 1.39lgN insert: 1.39lgN delete:	Yes	compareTo()

3. BST implementation

   public class BST<Key extends Comparable<Key>, Value>{
      private Node root; // root of BST
   
      private class Node{
         private Key key;
         private Value val;
         private Node left;
         private Node right;
         private int count;
   
         public Node(Key key, Value val){
            this.key = key;
            this.val = val;
         }
      }
   
      // 尋找key，如有，重置value；若沒有，添加新的node
      // 根據(jù)相應的Key返回相應的value，若沒有這個key，返回null
      public void 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);
         }
         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{ // cmp == 0
            x.val = val;
         }
         x.count = 1 + size(x.left) + size(x.right);
         return x;
      }
   
      // 根據(jù)相應的Key返回相應的value，若沒有這個key，返回null
      // cost: #compares = 1 + depth of node
      public Value get(Key key){ 
         Node x = root;
         while(x != null){
            int cmp = key.compareTo(x.key);
            if(cmp < 0){
               x = x.left;
            }else if(cmp > 0){
               x = x.right;
            }else{ // cmp == 0
               return x.val;
            }
         }
         return null;
      }
   
      // 返回小于給定key的最大的key
      public Key floor(Key key){
         Node x = floor(root, key);
         if(x == null){
            return null;
         }
         return x.key;
      }
   
      private Node floor(Node x, Key key){
         if(x == null){
            return null;
         }
         int cmp = key.compareTo(x.key);
         if(cmp == 0){ // floor 就是這個key自己
            return x;
         }
         if(cmp < 0){ // 給定的key比root的key小，說明這個key的floor一定在root的left subtree
            return floor(x.left, key);
         }
         // cmp > 0, 可能這個root就是我的floor，也可能在這個root的right subtree有我的floor
         Node t = floor(x.right, key);
         if(t != null){
            return t;
         }else{
            return x;
         }
   
      }
   
      // 一共有幾key
      public int size(){
         return size(root);
      }
   
      private int size(Node x){
         if(x == null){
            return 0;
         }
         return x.count;
      }
   
      // 一共有幾個小于給定key的keys
      public int rank(Key key){
         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{ // cmp == 0
            return size(x.left);
         }
      }
   
      public void deletMin(){
         root = deleteMin(root);
      }
   
      private Node deleteMin(Node x){
         if(x.left == null){
            return x.right;
         }
         x.left = deleteMin(x.left);
         x.count = 1 + size(x.left) + size(x.right);
         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);
         // search for 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; // no right child
            }
            if(x.left == null){
               return x.right; // no left child
            }
   
            // replace with successor
            Node t = x;
            x = min(t.right);
            x.right = deleteMin(t.right);
            x.left = t.left;
         }
         x.count = size(x.left) + size(x.right) + 1;
         return x;
      }
      
      // inorder traversal
      public Iterable<Key> keys(){
         Queue<key> q = new Queue<Key>();
         inorder(root, q);
         return q;
      }
   
      private void inorder(Node x, Queue<Key> q){
         if(x == null){
            return;
         }
         inorder(x.left, q);
         q.enqueue(x.key);
         inorder(x.right, q);
      }
   }