前言
本篇文章我將向大家介紹最負(fù)盛名的自平衡二叉查找樹——紅黑樹。
紅黑樹由魯?shù)婪?貝爾——一位慕尼黑科技大學(xué)信息技術(shù)教授發(fā)明。1978 年，在羅伯特.塞奇威克發(fā)表的一篇論文中為這種數(shù)據(jù)結(jié)構(gòu)正式命名為紅黑樹，并提供了完整的復(fù)雜度證明。
紅黑樹雖然繁瑣，但是它在實(shí)踐中有著非常高的效率，因?yàn)榧t黑樹是自平衡的（紅黑樹實(shí)現(xiàn)的其實(shí)是一種偽平衡，在后文中我們會提到），所以它不會出現(xiàn)像二分搜索樹在極端的情況下退化為鏈表的這種情況，可以在 的時間做元素的查找，插入以及刪除操作。因?yàn)槠鋬?yōu)秀的性能，在一些底層數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)中被廣泛使用——譬如 Java 語言中的 TreeMap 與 TreeSet 就是紅黑樹。
接下來，我們就一起探索，紅黑樹究竟是怎樣的一種數(shù)據(jù)結(jié)構(gòu)。
紅黑樹與 2-3 樹
在介紹大名鼎鼎的紅黑樹之前，我們先來看一下 2-3 樹這種數(shù)據(jù)結(jié)構(gòu)。提前了解 2-3 樹對我們接下來學(xué)習(xí)紅黑樹有很大的幫助，因?yàn)榧t黑樹與 2-3 樹的原理是相通的，并且 2-3 樹要比復(fù)雜的紅黑樹更容易理解。
什么是 2-3 樹呢？首先，2-3 樹是一種絕對平衡的多叉樹。
我們都知道平衡二叉樹的概念——平衡二叉樹是一棵二分搜索樹。它或者是一顆空樹，或它的左子樹與右子樹的高度之差（左子樹的高度 - 右子樹的高度，其別名叫平衡因子：balance factor）的絕對值不超過 1，且一棵平衡二叉樹的左右子樹均是一棵平衡二叉樹。
如下圖所示，該樹就是一棵平衡二叉樹：
而所謂的絕對平衡則比平衡二叉樹里面的平衡性要更加嚴(yán)格，絕對平衡的定義是：對于樹中任意一個節(jié)點(diǎn)，左右子樹高度相同。
如上圖所示，該示意圖表示一棵 2-3 樹。這棵樹滿足了絕對平衡的定義。
除此之外， 2-3 樹并不是一棵標(biāo)準(zhǔn)的二叉樹，而是一棵多叉樹。在上圖的 2-3 樹中，我們可以看到，有的節(jié)點(diǎn)存放了一個元素，有的節(jié)點(diǎn)存放了兩個元素。存放了一個元素的節(jié)點(diǎn)我們稱之為 2-節(jié)點(diǎn)，而存放了兩個元素的節(jié)點(diǎn)我們則稱之為 3-節(jié)點(diǎn)，2-3 樹中只具有這兩種類型的節(jié)點(diǎn)，這也是 2-3 樹其名字的由來。
接下來，我將演示向 2-3 樹插入元素的操作，讓我們一起來看一下 2-3 樹究竟是通過什么神奇的操作來維持整棵樹是絕對平衡的。
首先，我們向一棵空的 2-3 樹中插入一個節(jié)點(diǎn) “42”，然后再插入節(jié)點(diǎn) “37”:
向 2-3 樹插入節(jié)點(diǎn)的原則與二分搜索樹是一樣的，不過它還會遵循另外一個原則，那就是：新的節(jié)點(diǎn)永遠(yuǎn)不會插入到一個空的位置上。
如果這棵樹是二分搜索樹，那么節(jié)點(diǎn) “37” 將會插入到節(jié)點(diǎn) “42” 的左孩子的位置上，不過這樣一來，就破壞了 2-3 樹的絕對平衡性。所以，節(jié)點(diǎn) “37” 并不會插入到一個空的位置，而是與節(jié)點(diǎn) “42” 融合成為一個新的 3-節(jié)點(diǎn)：
接下來，我們向 2-3 樹中插入元素 “12”：
依據(jù)我們的原則“新的節(jié)點(diǎn)永遠(yuǎn)不會插入到一個空的位置上”，節(jié)點(diǎn) “12” 將會和當(dāng)前的 3-節(jié)點(diǎn)融合成為一個 “4-節(jié)點(diǎn)”：
然后，這個 4-節(jié)點(diǎn)會分裂成 3 個 2-節(jié)點(diǎn)，來維持絕對平衡的狀態(tài)并保證遵循 2-3 樹的定義：
我們繼續(xù)向當(dāng)前的 2-3 樹中插入元素 ”18“：
向當(dāng)前的 2-3 樹中插入元素 ”6“：
向當(dāng)前的 2-3 樹中插入元素 ”11“：
向當(dāng)前的 2-3 樹中插入元素 ”5“：
通過上面幾張模擬圖的演示，想必大家已經(jīng)能夠初步地掌握 2-3 樹的特點(diǎn)以及在向 2-3 樹添加元素時，2-3 樹如何維護(hù)絕對平衡。
我們之前說過，紅黑樹和 2-3 樹的本質(zhì)是相同的，如果大家理解了 2-3 樹，那么接下來我要介紹的紅黑樹也就不難理解了。2-3 樹中有兩種節(jié)點(diǎn)：2-節(jié)點(diǎn)與 3-節(jié)點(diǎn)，2-節(jié)點(diǎn)存儲一個元素，3-節(jié)點(diǎn)存儲兩個元素。而紅黑樹則是一種“二叉樹形式的 2-3 樹”，它使用單個黑色的節(jié)點(diǎn)來表示 2-節(jié)點(diǎn)，使用 “紅-黑” 這兩個節(jié)點(diǎn)表示一個三節(jié)點(diǎn)：
這樣一來，紅黑樹中所有的紅色節(jié)點(diǎn)必然為左孩子節(jié)點(diǎn)，所以我們也將這種紅黑樹稱為“左傾紅黑樹”（Left-Leaning Red-Black Tree）。
譬如這樣的一棵 2-3 樹：
轉(zhuǎn)換為紅黑樹之后就是這個樣子：
這也就是為什么我們會說紅黑樹與 2-3 樹是等價的，對于任意的一棵 2-3 樹都可以通過這種方式轉(zhuǎn)換為一棵紅黑樹。
紅黑樹的實(shí)現(xiàn)
紅黑樹的基本性質(zhì)
紅黑樹具有以下五條基本性質(zhì)：
1. 每個節(jié)點(diǎn)或者為紅色，或者為黑色。
這一點(diǎn)沒什么可說的，畢竟叫做紅黑樹嘛，節(jié)點(diǎn)非紅即黑。
2. 根節(jié)點(diǎn)的顏色一定是黑色。
我們可以類比考慮一下 2-3 樹，2-3 樹的節(jié)點(diǎn)不是 2-節(jié)點(diǎn)就是 3-節(jié)點(diǎn)，而無論是哪一種節(jié)點(diǎn)作為紅黑樹的根節(jié)點(diǎn)，都會使得根節(jié)點(diǎn)的顏色必然是黑色的。
3. 每一個葉子節(jié)點(diǎn)（最后的空節(jié)點(diǎn)）一定是黑色的。
如果紅黑樹為空，那么根節(jié)點(diǎn)也為空，這一點(diǎn)和第二點(diǎn)可以相互對應(yīng)起來，因?yàn)楦?jié)點(diǎn)的顏色必然是黑色的。
4. 如果一個節(jié)點(diǎn)是紅色的，那么它的孩子節(jié)點(diǎn)都是黑色的。
這一點(diǎn)大家同樣可以類比下 2-3 樹，紅黑樹中紅色節(jié)點(diǎn)的左右節(jié)點(diǎn)不是 2-節(jié)點(diǎn)就是 3-節(jié)點(diǎn)，無論是哪一種節(jié)點(diǎn)，與紅色節(jié)點(diǎn)相連的必然都是黑色節(jié)點(diǎn)。
5. 從任意一個節(jié)點(diǎn)到葉子節(jié)點(diǎn)，經(jīng)過的黑色節(jié)點(diǎn)的數(shù)量一樣多。
上面這棵 2-3 樹轉(zhuǎn)換為紅黑樹之后，是這樣的：
從這張圖里，我們可以清晰地看出，從任意一個節(jié)點(diǎn)到葉子節(jié)點(diǎn)，經(jīng)過黑色節(jié)點(diǎn)的數(shù)量是一樣多的。
這也就是我們所說的——紅黑樹是一棵保持“黑平衡”的二叉樹（黑色節(jié)點(diǎn)是絕對平衡的），而嚴(yán)格意義上來講紅黑樹并不是一棵平衡二叉樹，但是因?yàn)榧t黑樹具有黑平衡的特性，所以可以認(rèn)為紅黑樹保持的是一種近似的平衡。
從這里我們也可以分析出向紅黑樹添加，查找，刪除元素的時間復(fù)雜度。在最差的情況下，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑上，紅色節(jié)點(diǎn)與黑色節(jié)點(diǎn)交替出現(xiàn)，其復(fù)雜度為 ，忽略掉常數(shù)項(xiàng)系數(shù)，我們可以得到紅黑樹的增刪改查的時間復(fù)雜度為
。
向紅黑樹中添加元素的代碼實(shí)現(xiàn)
接下來我們來看一下如何向紅黑樹中添加元素。
紅黑樹中節(jié)點(diǎn)的定義與實(shí)現(xiàn)并不難。因?yàn)榧t黑樹本身是一棵二分搜索樹，所以節(jié)點(diǎn)可以存儲元素值，并且內(nèi)部有指向左，右孩子的指針，這些和二分搜索樹中節(jié)點(diǎn)的實(shí)現(xiàn)是一樣的。不過，紅黑樹的節(jié)點(diǎn)有顏色之分，且顏色非紅即黑，我們就額外使用一個 boolean 變量表示節(jié)點(diǎn)的顏色：
public class Node<E> {
public E e;
public Node left;
public Node right;
public boolean color;
public Node(E e) {
this.e = e;
left = null;
right = null;
color = true; // true 表示紅色，false 表示黑色
}
}
可以看到，我們設(shè)定初始化一個節(jié)點(diǎn)的顏色為紅色。其實(shí)不難理解，在介紹 2-3 樹時我們就提到了，向 2-3 樹中添加節(jié)點(diǎn)的原則是新的節(jié)點(diǎn)永遠(yuǎn)不會插入到一個空的位置上。而我們在添加節(jié)點(diǎn)時，首先要將待添加的節(jié)點(diǎn)與其他節(jié)點(diǎn)進(jìn)行融合，如果初始化節(jié)點(diǎn)的顏色為紅色，那么就表示新添加的節(jié)點(diǎn)與其他節(jié)點(diǎn)進(jìn)行融合這一步驟。
在捋清向紅黑樹添加一個節(jié)點(diǎn)的邏輯之前，我們首先回顧一下向二分搜索樹中插入一個節(jié)點(diǎn)的邏輯：
如果當(dāng)前二分搜索樹的根節(jié)點(diǎn)為空，那么新插入的節(jié)點(diǎn)就會成為根節(jié)點(diǎn)。
如果當(dāng)前二分搜索樹的根節(jié)點(diǎn)不為空，就讓根作為當(dāng)前比較的節(jié)點(diǎn)：新插入的節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)進(jìn)行比較；如果值比當(dāng)前節(jié)點(diǎn)小就要“向左走”，如果值比當(dāng)前節(jié)點(diǎn)大就要“向右走”，然后讓下一層的節(jié)點(diǎn)繼續(xù)作為當(dāng)前比較的節(jié)點(diǎn)，直至走到應(yīng)該插入的位置。
下圖為在向當(dāng)前的二分搜索樹中添加節(jié)點(diǎn)“28”的流程：
Java 代碼：
/**
* @param e 向二分搜索樹中添加新的元素
*/
public void add(E e) {
root = add(e, root);
}
/**
* @param e 向二分搜索樹中新插入的節(jié)點(diǎn)
* @param node 當(dāng)前比較的節(jié)點(diǎn)
* @return 返回二分搜索樹的根節(jié)點(diǎn)
*/
private Node add(E e, Node node) {
if (node == null) {
size++;
return new Node(e);
}
if (e.compareTo((E) node.e) < 0) {
node.left = add(e, node.left);
} else if (e.compareTo((E) node.e) > 0) {
node.right = add(e, node.right);
}
return node;
}
我們要滿足紅黑樹的根節(jié)點(diǎn)始終為黑色，所以每次插入完一個節(jié)點(diǎn)，我們都手動將根節(jié)點(diǎn)置為黑色：
public void add(E e) {
root = add(e, root);
root.color = BLACK; // false
}
基于向二分搜索樹中插入一個節(jié)點(diǎn)的邏輯，我們向紅黑樹中新插入一個節(jié)點(diǎn)有以下幾種情況：
- 當(dāng)前插入的節(jié)點(diǎn)與 2-節(jié)點(diǎn)進(jìn)行融合
- 當(dāng)前插入的節(jié)點(diǎn)與 3-節(jié)點(diǎn)進(jìn)行融合
如果我們插入到一個 2-節(jié)點(diǎn)上，則具有以下兩種情況：
第一種情況為，插入的節(jié)點(diǎn)比當(dāng)前的 2-節(jié)點(diǎn)的元素值小。
如果是這種情況，我們直接將新的節(jié)點(diǎn)與 2-節(jié)點(diǎn)融合為一個 3-節(jié)點(diǎn)即可：
第二種情況為，插入的節(jié)點(diǎn)比當(dāng)前的 2-節(jié)點(diǎn)的元素值大。
將元素 “42” 插入到 “37” 的右孩子的位置上：
此時，當(dāng)前并不滿足左傾紅黑樹的定義，我們需要以節(jié)點(diǎn) ”37“ 進(jìn)行一次 “左旋轉(zhuǎn)” 操作（左旋轉(zhuǎn)為逆時針，右旋轉(zhuǎn)為順時針），并將顏色重置：
為了不失一般性，我在節(jié)點(diǎn) “37” 與節(jié)點(diǎn) “42” 的孩子節(jié)點(diǎn)上分別添加了對應(yīng)的子樹，通過上圖中偽代碼的邏輯，我們看到“左旋轉(zhuǎn)”后的樹既保持了紅黑樹的特性，也保持了二分搜索樹的特性。
左旋轉(zhuǎn)操作的 Java 代碼如下：
/**
* 左旋轉(zhuǎn):
*
* node x
* / \ / \
* T1 x =========> node T3
* / \ / \
* T2 T3 T1 T2
*
*/
private Node leftRotate(Node node){
Node x = node.right;
// 左旋轉(zhuǎn)
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
在討論了新插入的節(jié)點(diǎn)與 2-節(jié)點(diǎn)進(jìn)行融合的所有情況后，我們來看一下新插入的節(jié)點(diǎn)與 3-節(jié)點(diǎn)進(jìn)行融合的情況。
如果我們插入到一個 3-節(jié)點(diǎn)上，則具有以下幾種情況：
第一種情況為，新的節(jié)點(diǎn)比 3-節(jié)點(diǎn)上的黑色節(jié)點(diǎn)的值還要大：
插入節(jié)點(diǎn) “66” 后：
這一步操作相當(dāng)于我們新插入的節(jié)點(diǎn)與 3-節(jié)點(diǎn)融合成為了一個 4-節(jié)點(diǎn)，對應(yīng)到 2-3 樹上，我們的操作是這樣的：
接下來，我們需要將當(dāng)前的 4-節(jié)點(diǎn)變成 3 個 2-節(jié)點(diǎn)，并讓 “42” 繼續(xù)向上融合：
所以，對應(yīng)地，在紅黑樹中，我們應(yīng)該將節(jié)點(diǎn) “37” 與 “66” 變?yōu)楹谏?2-節(jié)點(diǎn)，將節(jié)點(diǎn) “42” 置為繼續(xù)與上一個節(jié)點(diǎn)融合的紅色節(jié)點(diǎn)：
這一步驟的操作叫做 flipColors，顧名思義就是將這三個節(jié)點(diǎn)的顏色全部進(jìn)行翻轉(zhuǎn)，其代碼對應(yīng)如下：
// flipColors
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
第二種情況為，新的節(jié)點(diǎn)比 3-節(jié)點(diǎn)上的紅色節(jié)點(diǎn)的值還要小：
節(jié)點(diǎn) “12” 插入后：
此時，我們需要對節(jié)點(diǎn) “42” 進(jìn)行一次右旋轉(zhuǎn)：
再進(jìn)行一次 flipColors：
右旋轉(zhuǎn)的 Java 代碼如下：
/**
* 右旋轉(zhuǎn):
*
* node x
* / \ / \
* x T2 ===========> y node
* / \ / \
* y T1 T1 T2
*
*/
private Node rightRotate(Node node) {
Node x = node.left;
// 右旋轉(zhuǎn)
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
第三種情況為，新的節(jié)點(diǎn)比 3-節(jié)點(diǎn)上的紅色節(jié)點(diǎn)的值要大，但是比黑色節(jié)點(diǎn)的值要?。?/p>
節(jié)點(diǎn) “40” 插入后：
此時，我們首先對節(jié)點(diǎn) “37” 進(jìn)行一次左旋轉(zhuǎn)，然后對 "42" 節(jié)點(diǎn)進(jìn)行一次右旋轉(zhuǎn)，最后再執(zhí)行一次 flipColors 操作即可：
總的來看，向紅黑樹中添加元素的操作有如下的邏輯：
向紅黑樹中添加節(jié)點(diǎn)的完整 Java 代碼如下：
public class RBTree<E extends Comparable<E>> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root;
private int size;
public RBTree() {
root = null;
size = 0;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* 判斷節(jié)點(diǎn) node 的顏色
*
* @param node
* @return
*/
public boolean isRed(Node node) {
if (node == null)
return false;
return node.color;
}
/**
* @return 返回紅黑樹的根節(jié)點(diǎn)
*/
public Node getRoot() {
return root;
}
/**
* 左旋轉(zhuǎn):
*
* node x
* / \ / \
* T1 x ===========> node T3
* / \ / \
* T2 T3 T1 T2
*
*/
private Node leftRotate(Node node){
Node x = node.right;
// 左旋轉(zhuǎn)
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
/**
* 右旋轉(zhuǎn):
*
* node x
* / \ / \
* x T2 ===========> y node
* / \ / \
* y T1 T1 T2
*
*/
private Node rightRotate(Node node) {
Node x = node.left;
// 右旋轉(zhuǎn)
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
// 顏色翻轉(zhuǎn)
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
/**
* @param e 向紅黑樹中添加新的元素
*/
public void add(E e) {
root = add(e, root);
root.color = BLACK;
}
/**
* @param e 向紅黑樹中新插入的節(jié)點(diǎn)
* @param node 當(dāng)前比較的節(jié)點(diǎn)
* @return 返回紅黑樹的根節(jié)點(diǎn)
*/
private Node add(E e, Node node) {
if (node == null) {
size++;
return new Node(e); // 默認(rèn)插入的是紅色節(jié)點(diǎn)
}
if (e.compareTo((E) node.e) < 0) {
node.left = add(e, node.left);
} else if (e.compareTo((E) node.e) > 0) {
node.right = add(e, node.right);
}
if(isRed(node.right) && !isRed(node.left))
node = leftRotate(node);
if(isRed(node.left) && isRed(node.left.left))
rightRotate(node);
if(isRed(node.left) && isRed(node.right))
flipColors(node);
return node;
}
}
那么至此，向紅黑樹中插入一個節(jié)點(diǎn)的操作就已經(jīng)介紹完畢了。
以上內(nèi)容就是我對紅黑樹的學(xué)習(xí)總結(jié)。關(guān)于向紅黑樹中刪除節(jié)點(diǎn)的操作，在本篇文章中將不會涉及。
總結(jié)
今天我主要向大家分享了紅黑樹這種數(shù)據(jù)結(jié)構(gòu)。
我們在介紹紅黑樹之前首先介紹了 2-3 樹。如果理解了 2-3 樹，那么理解紅黑樹其實(shí)并不難。
然后我們介紹了紅黑樹的五大基本特性：
- 每個節(jié)點(diǎn)或者為紅色，或者為黑色
- 根節(jié)點(diǎn)的顏色一定是黑色
- 每一個葉子節(jié)點(diǎn)（最后的空節(jié)點(diǎn)）一定是黑色的
- 如果一個節(jié)點(diǎn)是紅色的，那么它的孩子節(jié)點(diǎn)都是黑色的
- 從任意一個節(jié)點(diǎn)到葉子節(jié)點(diǎn)，經(jīng)過的黑色節(jié)點(diǎn)的數(shù)量一樣多
并且從 2-3 樹的原理上對紅黑樹這 5 條基本特性進(jìn)行了分析。
最后，我們介紹了如何向紅黑樹中添加一個節(jié)點(diǎn)及它的代碼實(shí)現(xiàn)。
好啦，至此為止，這篇文章就到這里了～歡迎大家關(guān)注我的公眾號，在這里希望你可以收獲更多的知識，我們下一期再見！
