一、背景引入
????二叉排序樹的性能取決于二叉樹的層數(shù)，最好的情況O(log n)存在于完全二叉排序樹的情況下，其訪問性能近似于折半查找（圖左）；最差的情況是O(n)，比如插入的元素是有序的，生成的二叉樹就是一個(gè)鏈表，這種情況下，需要遍歷全部元素才能找到目標(biāo)元素（圖右）。
????為了改變排序二叉樹存在的不足，Rudolf Bayer 在 1972 年發(fā)明了另一種改進(jìn)后的排序二叉樹：紅黑樹，他將這種排序二叉樹稱為“對(duì)稱二叉 B 樹”，而紅黑樹這個(gè)名字則由 Leo J. Guibas 和 Robert Sedgewick 于 1978 年首次提出。
二、什么是紅黑樹
先來看看Wikipedia 中有關(guān)Red–black tree的介紹：
A red–black tree is a kind of self-balancing binary search tree. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.
簡單翻譯：
紅黑樹，一種自平衡的二叉查找樹，但在每個(gè)結(jié)點(diǎn)上有一個(gè)額外的存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是Red或Black。這些顏色位用來確保紅黑樹在插入和刪除操作后仍能夠近乎平衡。
性能分析：插入、刪除、查找 最壞時(shí)間復(fù)雜度都為
![]()
image.png
應(yīng)用領(lǐng)域
????由于統(tǒng)計(jì)性能好于平衡二叉樹（AVL樹），因此在很多地方都有應(yīng)用。，比如在 Java 集合框架中，很多部分(HashMap, TreeMap, TreeSet 等)都有紅黑樹的應(yīng)用，這些集合均提供了很好的性能。
應(yīng)用舉例
????HashMap作為Map接口的一個(gè)實(shí)現(xiàn)類，在java開發(fā)中經(jīng)常用到。其數(shù)據(jù)結(jié)構(gòu)如下圖所示：
????從圖中可以看出，HashMap底層使用的結(jié)構(gòu)包括兩部分:table和bucket。table指的是數(shù)組，是HashMap的主體，哈希表利用數(shù)組一次定位的特性，將當(dāng)前元素的關(guān)鍵字通過某個(gè)函數(shù)映射到數(shù)組中的某個(gè)位置，通過數(shù)組下標(biāo)一次定位就可以完成操作，存儲(chǔ)位置=f(關(guān)鍵字)。bucket指的是鏈表，主要是為了解決哈希沖突而存在的，試想如果插入的元素中存在大量哈希沖突，那么鏈表的長度會(huì)越來越長，這樣對(duì)于查找某一個(gè)元素可能需要遍歷整個(gè)鏈表才能找到，其性能可想而知。因此在jdk1.8中HashMap的bucket部分引入了紅黑樹。
????首先看看紅黑樹長啥樣：
????圖中的葉節(jié)點(diǎn)并沒有畫出來，而是以NIL指針代替，這是因?yàn)槿~節(jié)點(diǎn)在這里并不包含數(shù)據(jù)，只是作為結(jié)束符。
????為了便于理解，我們拿TreeMap來分析：
紅黑樹的數(shù)據(jù)結(jié)構(gòu)
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;
.......
}
其中Entry是TreeMap的內(nèi)部類。
紅黑樹特性
紅黑樹在原有的二叉查找樹基礎(chǔ)上增加了如下幾個(gè)要求：
1.Every node is either red or black.
2.The root is black.
3.Every leaf (NIL) is black.
4.If a node is red, then both its children are black.
5.For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
中文意思是：
1.每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色；
2.根節(jié)點(diǎn)永遠(yuǎn)是黑色的；
3.所有的葉節(jié)點(diǎn)都是是黑色的（注意這里說葉子節(jié)點(diǎn)其實(shí)是上圖中的 NIL 節(jié)點(diǎn)）；
4.每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)一定都是黑色；
5.從任一節(jié)點(diǎn)到其子樹中每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)；
其中：
性質(zhì) 3 中指定紅黑樹的每個(gè)葉子節(jié)點(diǎn)都是空節(jié)點(diǎn)，而且并葉子節(jié)點(diǎn)都是黑色。但 Java 實(shí)現(xiàn)的紅黑樹將使用 null 來代表空節(jié)點(diǎn)，因此遍歷紅黑樹時(shí)將看不到黑色的葉子節(jié)點(diǎn)，反而看到每個(gè)葉子節(jié)點(diǎn)都是紅色的。
性質(zhì) 4 的意思是：從每個(gè)根到節(jié)點(diǎn)的路徑上不會(huì)有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)，但黑色節(jié)點(diǎn)是可以連續(xù)的。 因此若給定黑色節(jié)點(diǎn)的個(gè)數(shù) N，最短路徑的情況是連續(xù)的 N 個(gè)黑色，樹的高度為 N - 1;最長路徑的情況為節(jié)點(diǎn)紅黑相間，樹的高度為 2(N - 1)
性質(zhì) 5 是成為紅黑樹最主要的條件，后序的插入、刪除操作都是為了遵守這個(gè)規(guī)定。
紅黑樹并不是標(biāo)準(zhǔn)平衡二叉樹，它以性質(zhì) 5 作為一種平衡方法，使自己的性能得到了提升。
三、紅黑樹的三大基本操作
左旋：
右旋：
著色
紅黑樹的左旋右旋
????紅黑樹的左右旋是比較重要的操作，左右旋的目的是調(diào)整紅黑節(jié)點(diǎn)結(jié)構(gòu)，轉(zhuǎn)移黑色節(jié)點(diǎn)位置，使其在進(jìn)行插入、刪除后仍能保持紅黑樹的 5 條性質(zhì)。比如 X 左旋(右圖轉(zhuǎn)成左圖)的結(jié)果，是讓在 Y 左子樹的黑色節(jié)點(diǎn)跑到 X 右子樹去。
左旋
指定節(jié)點(diǎn) x 的左旋 (右圖轉(zhuǎn)成左圖)：
//這里 p 代表 x
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
Entry<K,V> r = p.right; // p 是上圖中的 x，r 就是 y
p.right = r.left; // 左旋后，x 的右子樹變成了 y 的左子樹 β
if (r.left != null)
r.left.parent = p; //β 確認(rèn)父親為 x
r.parent = p.parent; //y 取代 x 的第一步：認(rèn) x 的父親為爹
if (p.parent == null) //要是 x 沒有父親，那 y 就是最老的根節(jié)點(diǎn)
root = r;
else if (p.parent.left == p) //如果 x 有父親并且是它父親的左孩子，x 的父親現(xiàn)在認(rèn) y 為左孩子，不要 x 了
p.parent.left = r;
else //如果 x 是父親的右孩子，父親就認(rèn) y 為右孩子，拋棄 x
p.parent.right = r;
r.left = p; //y 逆襲成功，以前的爸爸 x 現(xiàn)在成了它的左孩子
p.parent = r;
}
}
可以看到，x 節(jié)點(diǎn)的左旋就是把 x 變成 右孩子 y 的左孩子，同時(shí)把 y 的左孩子送給 x 當(dāng)右孩子
右旋
指定節(jié)點(diǎn) y 的右旋 (左圖轉(zhuǎn)成右圖)：
private void rotateRight(Entry<K,V> p) {
if (p != null) {
Entry<K,V> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
同理，y 節(jié)點(diǎn)的右旋就是把 y 變成 左孩子 x 的右孩子，同時(shí)把 x 的右孩子送給 x 當(dāng)左子樹。
四、紅黑樹的平衡插入
紅黑樹的插入主要分兩步：
首先和二叉查找樹的插入一樣，查找、插入
然后調(diào)整結(jié)構(gòu)，保證滿足紅黑樹狀態(tài)
?? ?? 對(duì)結(jié)點(diǎn)進(jìn)行重新著色
?? ??以及對(duì)樹進(jìn)行相關(guān)的旋轉(zhuǎn)操作
紅黑樹的插入在二叉查找樹插入的基礎(chǔ)上，為了重新恢復(fù)平衡，繼續(xù)做了插入修復(fù)操作。
紅黑樹的插入修復(fù)
?? 紅黑樹的第 5 條特征規(guī)定，任一節(jié)點(diǎn)到它子樹的每個(gè)葉子節(jié)點(diǎn)的路徑中都包含同樣數(shù)量的黑節(jié)點(diǎn)。也就是說當(dāng)我們往紅黑樹中插入一個(gè)黑色節(jié)點(diǎn)時(shí)，會(huì)違背這條特征。
?? 同時(shí)第 4 條特征規(guī)定紅色節(jié)點(diǎn)的左右孩子一定都是黑色節(jié)點(diǎn)，當(dāng)我們給一個(gè)紅色節(jié)點(diǎn)下插入一個(gè)紅色節(jié)點(diǎn)時(shí)，會(huì)違背這條特征。
??因此我們需要在插入黑色節(jié)點(diǎn)后進(jìn)行結(jié)構(gòu)調(diào)整，保證紅黑樹始終滿足這 5 條特征。
調(diào)整思想
插入、染紅后的調(diào)整有 2 種情況：
情況1.父親節(jié)點(diǎn)和叔叔節(jié)點(diǎn)都是紅色：
情況2.父親節(jié)點(diǎn)為紅色，叔叔節(jié)點(diǎn)為黑色
前面說了，插入一個(gè)節(jié)點(diǎn)后要擔(dān)心違反特征 4 和 5，數(shù)學(xué)里最常用的一個(gè)解題技巧就是把多個(gè)未知數(shù)化解成一個(gè)未知數(shù)。我們這里采用同樣的技巧，把插入的節(jié)點(diǎn)直接染成紅色，這樣就不會(huì)影響特征 5，只要專心調(diào)整滿足特征 4 就好了。這樣比同時(shí)滿足 4、5 要簡單一些。染成紅色后，我們只要關(guān)心父節(jié)點(diǎn)是否為紅，如果是紅的，就要把父節(jié)點(diǎn)進(jìn)行變化，讓父節(jié)點(diǎn)變成黑色，或者換一個(gè)黑色節(jié)點(diǎn)當(dāng)父親，這些操作的同時(shí)不能影響 不同路徑上的黑色節(jié)點(diǎn)數(shù)一致的規(guī)則。
情況1：父親節(jié)點(diǎn)和叔叔節(jié)點(diǎn)都是紅色：
假設(shè)插入的是節(jié)點(diǎn) N，這時(shí)父親節(jié)點(diǎn) P 和叔叔節(jié)點(diǎn) U 都是紅色，爺爺節(jié)點(diǎn) G 一定是黑色。
紅色節(jié)點(diǎn)的孩子不能是紅色，這時(shí)不管 N 是 P 的左孩子還是右孩子，只要同時(shí)把 P 和 U 染成黑色，G 染成紅色即可。這樣這個(gè)子樹左右兩邊黑色個(gè)數(shù)一致，也滿足特征 4。
但是這樣改變后 G 染成紅色，G 的父親如果是紅色豈不是又違反特征 4 了？
這個(gè)問題和我們插入、染紅后一致，因此需要以 爺爺節(jié)點(diǎn) G 為新的調(diào)整節(jié)點(diǎn)，再次進(jìn)行調(diào)整操作，以此循環(huán)，直到父親節(jié)點(diǎn)不是紅的，就沒有問題了。
情況2：父親節(jié)點(diǎn)為紅色，叔叔節(jié)點(diǎn)為黑色
假設(shè)插入的是節(jié)點(diǎn) N，這時(shí)父親節(jié)點(diǎn) P 是紅色，叔叔節(jié)點(diǎn) U 是黑色，爺爺節(jié)點(diǎn) G 一定是黑色。
紅色節(jié)點(diǎn)的孩子不能是紅色，但是直接把父親節(jié)點(diǎn) P 涂成黑色也不行，這條路徑多了個(gè)黑色節(jié)點(diǎn)。怎么辦呢？
既然改變不了你，那我們就此別過吧，我換一個(gè)更適合我的！
我們?cè)趺窗?P 弄走呢？看來看去，還是右旋最合適，通過把 爺爺節(jié)點(diǎn) G 右旋，P 變成了這個(gè)子樹的根節(jié)點(diǎn)，G 變成了 P 的右子樹。
右旋后 G 跑到了右子樹上，這時(shí)把 P 變成黑的，多了一個(gè)黑節(jié)點(diǎn)，再把 G 變成紅的，就平衡了！
情況2：父親節(jié)點(diǎn)為紅色，叔叔節(jié)點(diǎn)為黑色
N 位于 P 的右孩子位置，將 P 左旋，就化解成上述情況了。
源碼分析
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED; //直接染成紅色，少點(diǎn)麻煩
//這里分析的都是父親節(jié)點(diǎn)為紅色的情況，不是紅色就不用調(diào)整了
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // 插入節(jié)點(diǎn) x 的父親節(jié)點(diǎn)位于左孩子
Entry<K,V> y = rightOf(parentOf(parentOf(x))); // y 是 x 的叔叔節(jié)點(diǎn)
if (colorOf(y) == RED) { //如果 y 也是紅色，只要把父親節(jié)點(diǎn)和 y 都變成黑色，爺爺節(jié)點(diǎn)變成紅的，就 Ok 了
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else { //如果叔叔節(jié)點(diǎn) y 不是紅色，就需要右旋，讓父親節(jié)點(diǎn)變成根節(jié)點(diǎn)，爺爺節(jié)點(diǎn)去右子樹去，然后把父親節(jié)點(diǎn)變成黑色、爺爺節(jié)點(diǎn)變成紅色
//特殊情況：x 是父親節(jié)點(diǎn)的右孩子，需要對(duì)父親節(jié)點(diǎn)進(jìn)行左旋，把 x 移動(dòng)到左子樹
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else { 。。。。。。}} //和上面對(duì)稱的操作
五、一句話概括
在插入調(diào)整時(shí)為了簡化操作我們直接把插入的節(jié)點(diǎn)涂成紅色，這樣只要保證插入節(jié)點(diǎn)的父節(jié)點(diǎn)不是紅色就可以了。
