紅黑樹是比較常見的數(shù)據(jù)結(jié)構(gòu)之一，在Linux內(nèi)核中的完全公平調(diào)度器、高精度計時器、多種語言的函數(shù)庫(如,Java的TreeMap)等都有使用。

在學(xué)習(xí)紅黑樹之前，先來熟悉一下二叉查找樹。

二叉查找樹(Binary Search Tree)

二叉查找樹，它有一個根節(jié)點，且每個節(jié)點下最多有只能有兩個子節(jié)點，左子節(jié)點的值小于其父節(jié)點，右子節(jié)點的值大于其父節(jié)點。



插入節(jié)點


從根節(jié)點向下查找，當(dāng)新插入節(jié)點大于比較的節(jié)點時，新節(jié)點插入到比較節(jié)點的右側(cè)，當(dāng)小于比較的節(jié)點時，插入到比較節(jié)點的左側(cè)，一直向下比較大小，找到要插入元素的位置并插入元素。

如圖: 依次插入節(jié)點[100,50,200,80,300,10]



偽代碼(來源Java TreeMap，有省略和修改):
void put(K key, V value) { if (root == null) { root = new Node<>(key, value,
null); return; } Node<K,V> t = root; int cmp; // 比較結(jié)果 Node<K,V> parent;
Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp =
k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right;
else return; // 節(jié)點存在直接返回 } while (t != null); Node<K,V> e = new Node<>(key,
value, parent); if (cmp < 0){ parent.left = e; }else{ parent.right = e; } }
查找節(jié)點

從根節(jié)點開始向下查找，當(dāng)查找節(jié)點大于比較的節(jié)點時，向右查找，當(dāng)小于當(dāng)前比較節(jié)點時，就向左查找。一直向下查找，直到找到對應(yīng)的節(jié)點或到終點查找結(jié)束。

如圖: 查找節(jié)點[80]



偽代碼(來源Java TreeMap，有省略和修改):
Node<K,V> getNode(Object key) { Comparable<? super K> k = (Comparable<? super
K>) key; Node<K,V> p = root; while (p != null) { int cmp = k.compareTo(p.key);
if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } return
null; }
刪除節(jié)點

刪除節(jié)點首先要查找要刪除的節(jié)點，找到后執(zhí)行刪除操作。

刪除節(jié)點的節(jié)點有如下幾種情況：

* 刪除的節(jié)點有兩個子節(jié)點
* 刪除的節(jié)點有一個子節(jié)點
* 刪除的節(jié)點沒有子節(jié)點
Case 1：

該種情況下，涉及到節(jié)點的“位置變換”，用右子樹中的最小節(jié)點替換當(dāng)前節(jié)點。從右子樹一直 left 到 NULL。最后會被轉(zhuǎn)換為 Case 2 或 Case 3
的情況。

所以對于刪除有兩個孩子的節(jié)點，刪除的是其右子樹的最小節(jié)點，最小節(jié)點的內(nèi)容會替換要刪除節(jié)點的內(nèi)容。

如圖:刪除節(jié)點[50]



Case 2：

有一個子節(jié)點的情況下，將其父節(jié)點指向其子節(jié)點，然后刪除該節(jié)點。

如圖:刪除節(jié)點[200]



Case 3：

在沒有子節(jié)點的情況，其父節(jié)點指向空，然后刪除該節(jié)點。

如圖:刪除節(jié)點[70]



偽代碼(來源Java TreeMap，有省略和修改):
Node remove(Object key) { // 查找節(jié)點(參考上面查找代碼) Node<K,V> p = getNode(key); //
節(jié)點變換。 p 有兩個子節(jié)點，將其轉(zhuǎn)換為刪除后繼節(jié)點 if (p.left != null && p.right != null) { Entry<K,V>
s = t.right; while (s.left != null){ s = s.left; } p.key = s.key; p.value =
s.value; p = s; } Entry<K,V> replacement = (p.left != null ? p.left : p.right);
// p 有一個子節(jié)點 if (replacement != null) { replacement.parent = p.parent; if
(p.parent == null){ root = replacement; } else if (p == p.parent.left){
p.parent.left = replacement; } else{ p.parent.right = replacement; } p.left =
p.right = p.parent = null; } else if (p.parent == null) { // 根節(jié)點 root = null; }
else { // p 沒有子節(jié)點 if (p == p.parent.left){ p.parent.left = null; } else if (p
== p.parent.right){ p.parent.right = null; } p.parent = null; } return p; }
樹的優(yōu)勢


我們知道，有序數(shù)組刪除或插入數(shù)據(jù)較慢（向數(shù)組中插入數(shù)據(jù)時，涉及到插入位置前后數(shù)據(jù)移動的操作），但根據(jù)索引查找數(shù)據(jù)很快，可以快速定位到數(shù)據(jù)，適合查詢。而鏈表正好相反，查找數(shù)據(jù)比較慢，插入或刪除數(shù)據(jù)較快，只需要引用移動下就可以，適合增刪。

而二叉樹就是同時具有以上優(yōu)勢的數(shù)據(jù)結(jié)構(gòu)。

該樹缺點

上面的樹是非平衡樹，由于插入數(shù)據(jù)順序原因，多個節(jié)點可能會傾向根的一側(cè)。極限情況下所有元素都在一側(cè)，此時就變成了一個相當(dāng)于鏈表的結(jié)構(gòu)。

如圖:依次插入節(jié)點[100,150,170,300,450,520 ...]



這種不平衡將會使樹的層級增多（樹的高度增加），查找或插入元素效率變低。

那么只要當(dāng)插入元素或刪除元素時還能維持樹的平衡，使元素不至于向一端嚴重傾斜，就可以避免這個問題。

到此，紅黑樹閃亮登場， 紅黑樹就是一種平衡二叉樹。

紅黑樹（Red Black Tree）

紅黑樹是一種平衡二叉樹，遵守如下規(guī)則來保證紅黑樹的平衡，保證每個節(jié)點在它左邊的后代數(shù)目和在它右邊的后代數(shù)目應(yīng)該是大致相等（最長路徑也不會超過最短路徑的2倍）。

紅黑樹的規(guī)則

紅黑樹是在二叉查找樹基礎(chǔ)之上再遵循如下規(guī)則的樹

* 每個節(jié)點顏色不是黑色就是紅色
* 根節(jié)點一定為黑色
* 兩個紅色節(jié)點不能相鄰（紅色節(jié)點的子節(jié)點一定是黑色）
* 從任意節(jié)點到葉子節(jié)點的每條路徑包含的黑色節(jié)點數(shù)目相同（黑色高度）
* 每個葉子節(jié)點(NULL節(jié)點，空節(jié)點)是黑色
當(dāng)插入或刪除節(jié)點時，必須要遵守紅黑樹的規(guī)則，根據(jù)這些規(guī)則來決定是否需要改變樹的結(jié)構(gòu)或節(jié)點顏色，使其達到平衡。

查找節(jié)點并不影響樹的平衡，所以紅黑樹的節(jié)點查找和二叉查找樹的操作是一樣的（請參考二叉查找樹）。

如圖: 紅黑樹 - 依次插入節(jié)點[100,200,300,400,500,600,700,800]



最終樹的結(jié)構(gòu)是大致平衡的，不像二叉查找樹那樣偏向一側(cè)。

了解變色和旋轉(zhuǎn)

如果新插入元素或刪除元素后，紅黑樹的規(guī)則被破壞，這時需要對樹進行調(diào)整來重新滿足紅黑樹規(guī)則。調(diào)整有變色和旋轉(zhuǎn)（左旋或右旋）兩種方式，接下來分別了解這兩種方式：

* 變色
通過改變節(jié)點顏色修正紅黑樹，節(jié)點由紅變黑或黑變紅

* 旋轉(zhuǎn)
通過改變節(jié)點的位置關(guān)系修正紅黑樹

如圖: 以右旋為例



左旋則與右旋對稱，為逆時針旋轉(zhuǎn)。



圖中空節(jié)點位置可以是多個節(jié)點構(gòu)成的子樹，也可以是一個具體節(jié)點。

右旋(來源Java TreeMap):
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; } }
左旋(來源Java TreeMap):
private void rotateLeft(Entry<K,V> p) { if (p != null) { Entry<K,V> r =
p.right; p.right = r.left; if (r.left != null) r.left.parent = p; r.parent =
p.parent; if (p.parent == null) root = r; else if (p.parent.left == p)
p.parent.left = r; else p.parent.right = r; r.left = p; p.parent = r; } }


紅黑樹的插入和刪除節(jié)點請看下一篇： 數(shù)據(jù)結(jié)構(gòu)之紅黑樹-動圖演示(下) - 更新中 ...

• ? 上一篇：后端小白的VUE入門筆記, 進階篇
• ? 下一篇：公司為什么需要建立一套統(tǒng)一的開發(fā)框架？