紅黑樹
什麼是紅黑樹
紅黑樹依然是一棵二分搜索樹，《演算法導論》中的紅黑樹定義如下：
- 每個節點或者是紅色的，或者是黑色的
- 根節點是黑色的
- 每一個葉子節點（最後的空節點）是黑色的
- 如果一個節點是紅色的，那麼他的孩子節點都是黑色的
- 從任意一個節點到葉子節點，經過的黑色節點是一樣的
在學習紅黑樹之前，我們有必要先學習一下什麼是2-3樹，學習2-3樹不僅對於理解紅黑樹有幫助，對於理解B類樹，也是有巨大幫助的。我們常用到的磁碟存儲、文件系統、資料庫等相應的數據存儲都是採用的B類型這樣的數據結構。
什麼是2-3樹
2-3樹依然滿足二分搜索樹的基本性質，但2-3樹不是一種二叉樹，2-3樹有兩種節點，節點可以存放一個元素或者兩個元素；2-3樹是一棵絕對平衡的樹，2-3樹對於任意一個節點的的左右子樹的高度一定是相等的
2-3樹的添加操作
2-3樹的添加操作將新節點添加到空的位置，若添加一個比根節點小的元素，並且根節點的左子樹為空，待添加的新元素會和根節點先融合，由二節點變成三節點，當此時再添加一個元素時，會發現根節點的左子樹仍然為空，就還是會先和根節點向融合，但2-3樹不能有四節點，最多只能有三節點，所以需要將這個四節點分裂成有三個二節點的絕對平衡二叉樹，如圖：
讓我們再來看一下2-3樹添加元素的過程：
再向2-3樹中添加一些元素，找出規律：
通過如上的分析，不難知道，如果添加一個元素是添加到一個2-節點，會直接與之融合，如果是添加到一個3-節點，會暫時融合形成一個四節點，然後分裂成一個絕對平衡樹。如下圖所示：
紅黑樹與2-3樹的等價性
我們在這裡定義所有的紅色節點都是向左傾斜的，紅色節點代表與父親節點相融合，由於我們可以通過2-3樹畫出一個棵紅黑樹：
由此可知，紅黑樹是保持「黑平衡」的二叉樹，嚴格意義上 ，不是平衡二叉樹，最大高度為2logn,並且從圖中也可以看出，只有三節點左側的元素才是紅色的。紅黑樹和AVL樹：由於紅黑樹的最大高度是2logn,所以在查找時，相比於AVL樹會慢一些，而紅黑樹的添加和刪除元素比AVL樹更快一些，如果只是用於查詢，AVL樹的性能要更高一些。
向紅黑樹中添加一個新元素，類比於2-3樹中添加一個新元素，就是或者添加進2-節點，形成3-節點；或者添加進3-節點，暫時形成一個4-節點，這樣我們可以讓我們的紅黑樹，永遠添加紅節點。由於我們在本文是定義的所有紅色節點都是向左傾斜的，當我們新添加的紅色節點在根節點的右側時，我們需要先進行左旋轉擦歐總，然後再進行染色操作，在我們左旋轉的過程中並不保持紅黑樹的性質，如下圖：
左旋轉的程式碼實現：
// node x
// / \ 左旋轉 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
private Node leftRotate(Node node){
Node x = node.right;
// 左旋轉
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
當我們向紅黑樹中的「3-節點」添加新元素，由於添加的新節點顏色都默認是紅色的，紅色節點表示是去和 父親節點融合的，當4-節點分裂成3個2-節點時，新的根節點需要和父親節點去融合，這意味著這個新的根節點需要變成紅色節點。
顏色翻轉的程式碼實現：
// 顏色翻轉
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
三個2-節點的自平衡，如圖：
右旋轉程式碼實現：
// node x
// / \ 右旋轉 / \
// x T2 -------> y node
// / \ / \
// y T1 T1 T2
private Node rightRotate(Node node){
Node x = node.left;
// 右旋轉
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
三節點的另外一種情況：
像紅黑樹中添加節點，就分析到這裡了，下面讓我們來用程式碼實現一個紅黑樹和紅黑樹的添加操作：
public class RBTree<K extends Comparable<K>, V> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node{
public K key;
public V value;
public Node left, right;
public boolean color;
public Node(K key, V value){
this.key = key;
this.value = value;
left = null;
right = null;
color = RED;
}
}
private Node root;
private int size;
public RBTree(){
root = null;
size = 0;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
// 判斷節點node的顏色
private boolean isRed(Node node){
if(node == null)
return BLACK;
return node.color;
}
// node x
// / \ 左旋轉 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
private Node leftRotate(Node node){
Node x = node.right;
// 左旋轉
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
// node x
// / \ 右旋轉 / \
// x T2 -------> y node
// / \ / \
// y T1 T1 T2
private Node rightRotate(Node node){
Node x = node.left;
// 右旋轉
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
// 顏色翻轉
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
// 向紅黑樹中添加新的元素(key, value)
public void add(K key, V value){
root = add(root, key, value);
root.color = BLACK; // 最終根節點為黑色節點
}
// 向以node為根的紅黑樹中插入元素(key, value)，遞歸演算法
// 返回插入新節點後紅黑樹的根
private Node add(Node node, K key, V value){
if(node == null){
size ++;
return new Node(key, value); // 默認插入紅色節點
}
if(key.compareTo(node.key) < 0)
node.left = add(node.left, key, value);
else if(key.compareTo(node.key) > 0)
node.right = add(node.right, key, value);
else // key.compareTo(node.key) == 0
node.value = value;
if (isRed(node.right) && !isRed(node.left))
node = leftRotate(node);
if (isRed(node.left) && isRed(node.left.left))
node = rightRotate(node);
if (isRed(node.left) && isRed(node.right))
flipColors(node);
return node;
}
// 返回以node為根節點的二分搜索樹中，key所在的節點
private Node getNode(Node node, K key){
if(node == null)
return null;
if(key.equals(node.key))
return node;
else if(key.compareTo(node.key) < 0)
return getNode(node.left, key);
else // if(key.compareTo(node.key) > 0)
return getNode(node.right, key);
}
public boolean contains(K key){
return getNode(root, key) != null;
}
public V get(K key){
Node node = getNode(root, key);
return node == null ? null : node.value;
}
public void set(K key, V newValue){
Node node = getNode(root, key);
if(node == null)
throw new IllegalArgumentException(key + " doesn't exist!");
node.value = newValue;
}
// 返回以node為根的二分搜索樹的最小值所在的節點
private Node minimum(Node node){
if(node.left == null)
return node;
return minimum(node.left);
}
// 刪除掉以node為根的二分搜索樹中的最小節點
// 返回刪除節點後新的二分搜索樹的根
private Node removeMin(Node node){
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
// 從二分搜索樹中刪除鍵為key的節點
public V remove(K key){
Node node = getNode(root, key);
if(node != null){
root = remove(root, key);
return node.value;
}
return null;
}
private Node remove(Node node, K key){
if( node == null )
return null;
if( key.compareTo(node.key) < 0 ){
node.left = remove(node.left , key);
return node;
}
else if(key.compareTo(node.key) > 0 ){
node.right = remove(node.right, key);
return node;
}
else{ // key.compareTo(node.key) == 0
// 待刪除節點左子樹為空的情況
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
// 待刪除節點右子樹為空的情況
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
return leftNode;
}
// 待刪除節點左右子樹均不為空的情況
// 找到比待刪除節點大的最小節點, 即待刪除節點右子樹的最小節點
// 用這個節點頂替待刪除節點的位置
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
}
最後，在這裡做一個紅黑樹的總結：
對於完全隨機的數據，普通的二分搜索樹就很好用，缺點:機端情況會退化成鏈表（或者高度布不平衡）；對於查詢較多的情況，AVL樹很好用！紅黑樹犧牲了平衡性（2logn的高度），統計性能更優（總和增刪改查所有的操作）。
