1. 2-3 search trees

1. 每個Node有1或2個key

   • 2-node：one key夷陋，two children
   • 3-node：two keys终惑，three children

2. Perfect balance：

   • 每一條path立倍，從root到null-link都是相同長度

3. Symmetric order

   • 橫向從左到右升序

4. Search

   • search key與各個Node的key比較
   • 沿著對應(yīng)的link（recursively），直到找到相同的key

5. Insertion

   • 若每個key都已經(jīng)有2個key，將新key加入這個3-node形成臨時的4-node

   • 將這個4-node中間值的key晉升為parent

   • 重復(fù)直到結(jié)束

   • 當(dāng)這條search path從root起的每一個node都是2-node唁桩，那么再加入一個key号杠，length+1

2. Red-Black BSTs

Represent 2-3 tree as a BST

1. Definition:

   • 每一個Node最多只有一個red-link
   • 每一條path從root到null-link都有相同數(shù)量的black-links
   • Red-link只在左側(cè)
   • 當(dāng)將red-link平方蚪腋，red-black BST就是2-3 tree

2. Insertion

   1. 找到的null-link的parent node只有black-link

      • 若key小于parent node，帶著red-link加在左邊就完成
      • 若key大于parent node姨蟋，帶著red-link加在右邊屉凯，再rotate left即可

   2. 找到的null-link的parent node已經(jīng)有red-link（相當(dāng)于在2-3tree中，3-node要臨時變4-node）

      • case 1（larger：已有a芬探，b(parent)神得，插入c）：找到null-link，加入新的node（key=c偷仿， red-link）哩簿，然后flip color
      • case 2（smaller：已有b，c(parent)酝静，插入a）：找到null-link节榜，加入新的node（key=a， red-link）”鹬牵現(xiàn)在b有兩個red-links宗苍，不符合規(guī)定。c進(jìn)行rotate right操作薄榛，回歸case 1讳窟，然后flip color
      • case 3（middle：已有a，c(parent)敞恋，插入b）：找到null-link丽啡，加入新的node（key=b， red-link）硬猫。此時red-link在a的右側(cè)补箍，不符合規(guī)定。b進(jìn)行rotate left啸蜜，回歸case2坑雅，然后c進(jìn)行rotate right操作，最后flip color

3. Java implementation

   public class RBtree<Key extends Comparable<Key>, Value>{
   
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private Node root; // root of BST
   
    private class Node{
        Key key;
        Value val;
        Node left, right;
        boolean color;  // color of parent link
   
        public Node(Key key, Value val, boolean color){
            this.key = key;
            this.val = val;
            this.color = color;
        }
    }
   
    public void put(Key key, Value val){
         root = put(root, key, val);
       }
   
    private Node put(Node h, Key key, Value val){
        // find the null-link, insert at bottom (and color it red)
        if(h == null){ 
            return new Node(key, val, RED);
        }
   
        int cmp = key.compareTo(x.key);
        if(cmp < 0){
            h.left = put(h.left, key, val);
        }else if(cmp > 0){
            h.right = put(h.right, key, val);
        }else{
            h.val = val;
        }
   
        // Right child red, left child black: rotate left.
        if(isRed(h.right) && !isRed(h.left)){
            h = rotateLeft(h);
        }
        // Left child, left-left grandchild red: rotate right.
        if(isRed(h.left) && isRed(h.left.left)){
            h = rotateRight(h);
        }
        // Both children red: flip colors.
        if(isRed(h.left) && isRed(h.right)){
            flipColor(h);
        }
   
        return h;
   
    }
   
    private boolean isRed(Node x){
        if(x == null){
            return false;
        }
        return x.color == RED;
    }
   
    // Orient a (temporarily) right-leaning red link to lean left.
    private Node rotateLeft(Node h){
        // assert isRed(h.right);
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        return x
    }
   
    // Orient a left-leaning red link to (temporarily) lean right.
    private Node rotateRight(Node h){
        // assert isRed(h.left);
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        return x;
   
    }
   
    // Recolor to split a (temporary) 4-node.
    private void flipColors(Node h){
        // assert !isRed(h);
        // assert isRed(h.left);
        // assert isRed(h.right);
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }
   
    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{
                return null;
            }
        }
    } 
   }