## 2015年10月2日 星期五

### [ Algorithm ] Red-Black BST

Source From Here
Left-leaning red-black BSTs (Guibas-Sedgewick 1979 and Sedgewick 2007)
1. Represent 2–3 tree as a BST
2. Use "internal" left-leaning links as "glue" for 3–nodes

An equivalent definition
A BST such that:

* No node has two red links connected to it.
* Every path from root to null link has the same number of black links.

1-1 correspondence with 2-3 trees
Key property. 1–1 correspondence between 2–3 and LLRB.

Search implementation for red-black BSTs
Observation. Search is the same as for elementary BST (ignore color).

Red-black BST representation
Each node is pointed to by precisely one link (from its parent) which can be encoded with color of BLACK or RED

Elementary red-black BST operations
Left rotation. Orient a (temporarily) right-leaning red link to lean left.

Right rotation. Orient a left-leaning red link to (temporarily) lean right.

Color flip. Recolor to split a (temporary) 4-node.

Invariants. Maintains symmetric order and perfect black balance.

Insertion in a LLRB tree: overview
Basic strategy. Maintain 1-1 correspondence with 2-3 trees by applying elementary red-black BST operations.

Warmup 1. Insert into a tree with exactly 1 node.

Case 1. Insert into a 2-node at the bottom.
* Do standard BST insert; color new link red.

Warmup 2. Insert into a tree with exactly 2 nodes.

Case 2. Insert into a 3-node at the bottom.
* Do standard BST insert; color new link red.
* Rotate to balance the 4-node (if needed).
* Flip colors to pass red link up one level.
* Rotate to make lean left (if needed).
* Repeat case 1 or case 2 up the tree (if needed).

Java implementation
Same code for all cases.
* Right child red, left child black: rotate left.
* Left child, left-left grandchild red: rotate right.
* Both children red: flip colors.

The complete sample code in Groovy:
- RedBlackBST.groovy
1. package ds
2.
3. class RedBlackBSTextends Comparable,V> {
4.     private static boolean      RED=true
5.     private static boolean      BLACK=false
6.     private Node         root=null
7.
8.     private class Node{
9.         K           key
10.         V           value
11.         Node     left=null
12.         Node     right=null
13.         Boolean     color=false
14.
15.         @Override
16.         public String toString()
17.         {
18.             return String.format("(%s,%s,%s)|%s|%s", key, value, color, left, right)
19.         }
20.
21.         public void b(){color=false}
22.         public void r(){color=true}
23.     }
24.
25.     private boolean isRed(Node n){
26.         if(n==nullreturn false
27.         else return n.color
28.     }
29.     public void put(K key, V value)
30.     {
31.         root=put(root, key, value)
32.         root.color=false
33.     }
34.
35.     public Node put(Node h, K key, V value)
36.     {
37.         if(h == nullreturn new Node(key:key, value:value,color:true)
38.         int cmp = key.compareTo(h.key)
39.         if(cmp < 0)          h.left =  put(h.left,  key, value)
40.         else if(cmp > 0) h.right = put(h.right, key, value)
41.         else                h.value = value
42.
43.         if(isRed(h.right) && !isRed(h.left))        h = rotateLeft(h)
44.         if(isRed(h.left)  && isRed(h.left.left))    h = rotateRight(h)
45.         if(isRed(h.left)  && isRed(h.right))        flipColors(h)
46.
47.         return h
48.     }
49.     public V get(K k)
50.     {
51.         Node node = root
52.         while(node!=null)
53.         {
54.             int c = k.compareTo(node.key)
55.             if(c==0return node.value
56.             else if(c<0) node = node.left
57.             else node = node.right
58.         }
59.         return null
60.     }
61.     private Node rotateLeft(Node h)
62.     {
63.         assert(isRed(h.right))
64.         Node x = h.right
65.         h.right = x.left
66.         x.left = h
67.         x.color = h.color
68.         h.r()
69.         return x
70.     }
71.     private Node rotateRight(Node h)
72.     {
73.         assert(isRed(h.left))
74.         Node x = h.left
75.         h.left = x.right
76.         x.right = h
77.         x.color = h.color
78.         h.r()
79.         return x
80.     }
81.     private Node flipColors(Node h)
82.     {
83.         assert(!isRed(h))
84.         assert(isRed(h.left))
85.         assert(isRed(h.right))
86.         h.r()
87.         h.left.b()
88.         h.right.b()
89.     }
90. }
Testing Code:
1. package lab
2.
3. import ds.RedBlackBST
4.
5. class W5_E1 {
6.     static void main(args)
7.     {
8.         RedBlackBST rbBST = new RedBlackBST()
9.         def data = [] as Set
10.         Random rdm = new Random()
11.         100.times{
12.             def k = rdm.nextInt(100)
14.             rbBST.put(k, k)
15.         }
16.
17.         printf("BST Size=%d...\n", data.size())
18.         data.each{ key->
19.             assert(key==rbBST.get(key))
20.         }
21.         printf("Pass!")
22.     }
23. }
ST implementations: summary

## 關於我自己

Where there is a will, there is a way!