紅黑樹插入算法實現原理分析
引言
紅黑樹是在實際工程中被廣泛應用的一種數據結構，比如Linux中的線程調度就是使用的紅黑樹來管理進程控制塊，而Nginx中也是使用紅黑樹來管理的timer，Java中的TreeMap和TreeSet也是基于紅黑樹來實現的。紅黑樹相比普通二叉查找樹的一個優勢就是它的樹高為~lgN，所以不管是查找/插入/刪除操作它均能保證能夠在對數時間之內完成。本文我們就先來了解一下紅黑樹插入算法的實現。
紅黑樹的定義
紅黑樹可以定義成含有紅黑鏈接并且滿足下列條件的二叉查找樹：
- 紅鏈接均為左鏈接。
- 沒有任何一個節點同時和兩條紅鏈接相連。
- 任意空鏈接到根節點的路徑上的黑鏈接數目相同。p.s: 我們將指向一棵空樹的鏈接稱為空鏈接。
比如下圖就是一棵典型的紅黑樹，如果之前了解過2-3樹的話(不了解也沒有關系，我們下面的內容并不會涉及到2-3樹)，可以發現如果將紅黑樹中的紅色結點畫平，實際上它就是2-3樹的一種變形，不過相比2-3樹，紅黑樹的查找操作要簡單的多，但它同時也結合了2-3樹中高效的插入操作，所以說紅黑樹其實是普通的二叉查找樹和2-3樹兩種數據結構優點的結合。
紅黑樹的定義
在實現紅黑樹之前我們先來定義一棵紅黑樹：
public class RedBlackLiteBST<Key extends Comparable<Key>, Value> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root; // root of the BST
private int n; // number of key-value pairs in BST
// BST helper node data type
private class Node {
private Key key; // key
private Value val; // associated data
private Node left, right; // links to left and right subtrees
private boolean color; // color of parent link
public Node(Key key, Value val, boolean color) {
this.key = key;
this.val = val;
this.color = color;
}
}
}
在上面的代碼中，我們將鏈接的顏色保存在表示該結點的 Node 對象中的 color 變量中。如果指向它的鏈接是紅色的，那么該變量為true，黑色則為false，我們規定空鏈接都為黑色。如下圖所示，指向結點 C 的鏈接是紅色，那么我們就將 h.left.color 設置為紅色，指向結點 J 的鏈接是黑色的，我們就將 h.right.color 設置為黑色。
紅黑樹的顏色表示
紅黑樹的幾種基本操作
紅黑樹相比普通的二叉查找樹的一個重要優勢就是插入的高效性，但是正因為如此紅黑樹的插入操作的算法實現相比普通的二叉樹要復雜一些。在正式實現插入算法之前，我們有必要先了解一下對于紅黑樹的幾種基本操作。
左旋轉
如下圖所示，現在我們有一條紅色的右鏈接，現在我們想要將這條紅色右鏈接轉換為左鏈接，這個操作過程就叫做左旋轉：
左旋轉之前
我們要做的就是在保持紅黑樹平衡性的同時，將上圖的結構變為下面這樣：
左旋轉之后
仔細觀察可以發現，我們要實現的其實就是將紅色鏈接關聯的兩個節點中由較小的節點 E 作為根節點轉換成由較大的節點 S 作為根節點。同時在這個過程中為了保持二叉樹中左子樹都要小于根節點，右子樹都要大于根節點，所以如果 S 節點還存在的話左鏈接我們還需要將它變成 E 節點的右鏈接。具體的實現代碼如下：
private Node rotateLeft(Node h) {
assert (h != null) && isRed(h.right);
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
return x;
}
右旋轉
右旋轉的實現和左旋轉的實現是類似的，就是將一個紅色左鏈接轉換成一個紅色右鏈接：
右旋轉之前
與左旋轉的時候相反，我們要做的其實就是紅色鏈接關聯的兩個節點中較大的節點 S 作為根節點轉換成由較小的節點 E 作為根節點：
右旋轉之后
所以轉換成具體的代碼，我們只需要將left和right相互轉換就行了：
private Node rotateRight(Node h) {
assert (h != null) && isRed(h.left);
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
return x;
}
顏色轉換
上面我們提到紅黑樹的一個重要特性就是紅鏈接均為做左鏈接，所以對于下面這種情形，如果一個結點的兩個子結點均為紅色鏈接，我們就將子結點的顏色全部由紅色轉換成黑色，同時將父結點的顏色由黑變紅。
顏色轉換之前
顏色轉換之后
具體的實現代碼非常簡單：
private void flipColors(Node h) {
assert !isRed(h) && isRed(h.left) && isRed(h.right);
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK;
}
插入操作的實現
上面說了這么多，其實都是為接下來的插入操作做的預熱。接下來結合下圖，我們來分析紅黑樹插入操作過程我們會遇到的三種情形：
- 插入的新結點 c 大于樹中現存的兩個鍵，所以我們要將它連接到 b 結點的右鏈接。因為這個時候 b 的兩條鏈接都是紅鏈接，所以我們要進行 flipColors 。接下來可以發現，我們下面的兩種情況都會轉換成這種情形。
- 插入的新結點 a 要比樹中現存的兩個鍵都要小，所以我們先將它連接到結點 b 的左鏈接，前面我們提到紅黑樹的一個特性就是沒有任何一個節點可以同時和兩個紅色鏈接相連，而現在 b 結點卻違背了這一原則，所以我們要進行右旋轉操作，接下來情形1是一模一樣的了。
- 插入的新結點 b 在樹中現存的兩個鍵之間，所以我們先將它連接到結點 a 的右鏈接，前面我們提到紅黑樹中紅色鏈接都是左鏈接，所以我們首先要進行左旋轉操作，接下來就和情形2一模一樣了。
插入操作的3種情形
插入操作的具體實現代碼如下，下面的代碼直到 // fix-up any right-leaning right 之前我們做的都是為了找到合適的插入位置，而之后的3個 if 語句實際上就是對上圖中情形3的一種總結。
public void put(Key key, Value val) {
root = insert(root, key, val);
root.color = BLACK;
// assert check(); // Check integrity of red-black tree data structure.
}
private Node insert(Node h, Key key, Value val) {
if (h == null) {
n++;
return new Node(key, val, RED);
}
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = insert(h.left, key, val);
else if (cmp > 0) h.right = insert(h.right, key, val);
else h.val = val;
// fix-up any right-leaning links
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);
return h;
}
isRed 的實現非常簡單，我就不解釋了：
// is node x red (and non-null) ?
private boolean isRed(Node x) {
if (x == null) return false;
return x.color == RED;
}
來自：http://www.importnew.com/24071.html