【數(shù)據(jù)結(jié)構(gòu)】史上最好理解的紅黑樹講解，讓你徹底搞懂紅黑樹-創(chuàng)新互聯(lián)

目錄
成都創(chuàng)新互聯(lián)是一家專業(yè)提供綏德企業(yè)網(wǎng)站建設(shè),專注與網(wǎng)站設(shè)計制作、網(wǎng)站設(shè)計、H5建站、小程序制作等業(yè)務(wù)。10年已為綏德眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站建設(shè)公司優(yōu)惠進(jìn)行中。
一、紅黑樹簡介
二、為什么需要紅黑樹？
三、紅黑樹的特性
四、紅黑樹的效率
4.1 紅黑樹效率
4.2 紅黑樹和AVL樹的比較
五、紅黑樹的等價變換
六、紅黑樹的操作
6.1 旋轉(zhuǎn)操作
6.2 插入操作
6.2.1 插入操作的所有情況
6.2.2 LL和RR插入情況
6.2.3 LR和RL插入情況
6.2.4 上溢的LL插入情況
6.2.5 上溢的RR插入情況
6.2.6 上溢的LR插入情況
6.2.7 上溢的RL插入情況
6.2.8 插入情況總結(jié)
6.3 刪除操作
6.3.1 刪除操作的所有情況
6.3.2 刪除擁有1個紅色子節(jié)點(diǎn)的黑色節(jié)點(diǎn)
6.3.3 刪除黑色葉子節(jié)點(diǎn)——刪除節(jié)點(diǎn)為根節(jié)點(diǎn)
6.3.4 刪除黑色葉子節(jié)點(diǎn)——刪除節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為黑色
6.3.5 刪除黑色葉子節(jié)點(diǎn)——刪除節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為紅色
七、紅黑樹的平衡
八、紅黑樹的平均時間復(fù)雜度
九、AVL樹 vs 紅黑樹
9.1 AVL樹
9.2 紅黑樹
9.3 如何選擇
9.4 案例對比
9.4.1 二叉搜索樹
9.4.2 AVL樹
9.4.3 紅黑樹

大家應(yīng)該都學(xué)過平衡二叉樹(AVLTree)，了解到AVL樹的性質(zhì)，其實(shí)平衡二叉樹大的作用就是查找,AVL樹的查找、插入和刪除在平均和最壞情況下都是O(logn)。AVL樹的效率就是高在這個地方。如果在AVL樹中插入或刪除節(jié)點(diǎn)后，使得高度之差大于1。此時，AVL樹的平衡狀態(tài)就被破壞，它就不再是一棵二叉樹；為了讓它重新維持在一個平衡狀態(tài)，就需要對其進(jìn)行旋轉(zhuǎn)處理, 那么創(chuàng)建一顆平衡二叉樹的成本其實(shí)不小. 這個時候就有人開始思考，并且提出了紅黑樹的理論，紅黑樹在業(yè)界應(yīng)用很廣泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于紅黑樹結(jié)構(gòu)實(shí)現(xiàn)的。那么紅黑樹到底比AVL樹好在哪里？

一、紅黑樹簡介

紅黑樹是一種自平衡的二叉查找樹，是一種高效的查找樹。它是由 Rudolf Bayer 于1978年發(fā)明，在當(dāng)時被稱為平衡二叉 B 樹(symmetric binary B-trees)。后來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的紅黑樹。紅黑樹具有良好的效率，它可在?O(logN)?時間內(nèi)完成查找、增加、刪除等操作。

二、為什么需要紅黑樹？

對于二叉搜索樹，如果插入的數(shù)據(jù)是隨機(jī)的，那么它就是接近平衡的二叉樹，平衡的二叉樹，它的操作效率（查詢，插入，刪除）效率較高，時間復(fù)雜度是O（logN）。但是可能會出現(xiàn)一種極端的情況，那就是插入的數(shù)據(jù)是有序的（遞增或者遞減），那么所有的節(jié)點(diǎn)都會在根節(jié)點(diǎn)的右側(cè)或左側(cè)，此時，二叉搜索樹就變?yōu)榱艘粋€鏈表，它的操作效率就降低了，時間復(fù)雜度為O(N)，所以可以認(rèn)為二叉搜索樹的時間復(fù)雜度介于O（logN）和O(N)之間，視情況而定。那么為了應(yīng)對這種極端情況，紅黑樹就出現(xiàn)了，它是具備了某些特性的二叉搜索樹，能解決非平衡樹問題，紅黑樹是一種接近平衡的二叉樹（說它是接近平衡因?yàn)樗]有像AVL樹的平衡因子的概念，它只是靠著滿足紅黑節(jié)點(diǎn)的5條性質(zhì)來維持一種接近平衡的結(jié)構(gòu)，進(jìn)而提升整體的性能，并沒有嚴(yán)格的卡定某個平衡因子來維持絕對平衡）。

三、紅黑樹的特性

在講解紅黑樹性質(zhì)之前，先簡單了解一下幾個概念：

parent：父節(jié)點(diǎn)
sibling：兄弟節(jié)點(diǎn)
uncle：叔父節(jié)點(diǎn)（ parent 的兄弟節(jié)點(diǎn)）
grand：祖父節(jié)點(diǎn)（ parent 的父節(jié)點(diǎn)）

首先，紅黑樹是一個二叉搜索樹，它在每個節(jié)點(diǎn)增加了一個存儲位記錄節(jié)點(diǎn)的顏色，可以是RED,也可以是BLACK；通過任意一條從根到葉子簡單路徑上顏色的約束，紅黑樹保證最長路徑不超過最短路徑的二倍，因而近似平衡（最短路徑就是全黑節(jié)點(diǎn)，最長路徑就是一個紅節(jié)點(diǎn)一個黑節(jié)點(diǎn)，當(dāng)從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑上黑色節(jié)點(diǎn)相同時，最長路徑剛好是最短路徑的兩倍）。它同時滿足以下特性：

節(jié)點(diǎn)是紅色或黑色
根是黑色
葉子節(jié)點(diǎn)（外部節(jié)點(diǎn)，空節(jié)點(diǎn)）都是黑色，這里的葉子節(jié)點(diǎn)指的是最底層的空節(jié)點(diǎn)（外部節(jié)點(diǎn)），下圖中的那些null節(jié)點(diǎn)才是葉子節(jié)點(diǎn)，null節(jié)點(diǎn)的父節(jié)點(diǎn)在紅黑樹里不將其看作葉子節(jié)點(diǎn)
紅色節(jié)點(diǎn)的子節(jié)點(diǎn)都是黑色
1. 紅色節(jié)點(diǎn)的父節(jié)點(diǎn)都是黑色
2. 從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑上不能有 2 個連續(xù)的紅色節(jié)點(diǎn)
從任一節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)

根據(jù)上面的性質(zhì)，我們來判斷一下下面這課樹是不是紅黑樹

上面這棵樹首先很容易就能知道是滿足性質(zhì)1-4條的，關(guān)鍵在于第5條性質(zhì)，可能乍一看好像也是符合第5條的，但實(shí)際就會陷入一個誤區(qū)，直接將圖上的最后一層的節(jié)點(diǎn)看作葉子節(jié)點(diǎn)，這樣看的話每一條從根節(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑確實(shí)都經(jīng)過了3個黑節(jié)點(diǎn)。

但實(shí)際上，在紅黑樹中真正被定義為葉子結(jié)點(diǎn)的，是那些空節(jié)點(diǎn)，如下圖。

這樣一來，路徑1有4個黑色節(jié)點(diǎn)（算上空節(jié)點(diǎn)），路徑2只有3個黑色節(jié)點(diǎn)，這樣性質(zhì)5就不滿足了，所以這棵樹并不是一個紅黑樹節(jié)點(diǎn)。

注：下面的講解圖中將省略紅黑樹的null節(jié)點(diǎn)，請自行腦補(bǔ)

四、紅黑樹的效率 4.1 紅黑樹效率

紅黑樹的查找，插入和刪除操作，時間復(fù)雜度都是O(logN)。

查找操作時，它和普通的相對平衡的二叉搜索樹的效率相同，都是通過相同的方式來查找的，沒有用到紅黑樹特有的特性。

但如果插入的時候是有序數(shù)據(jù)，那么紅黑樹的查詢效率就比二叉搜索樹要高了，因?yàn)榇藭r二叉搜索樹不是平衡樹，它的時間復(fù)雜度O(N)。

插入和刪除操作時，由于紅黑樹的每次操作平均要旋轉(zhuǎn)一次和變換顏色，所以它比普通的二叉搜索樹效率要低一點(diǎn)，不過時間復(fù)雜度仍然是O(logN)?？傊?，紅黑樹的優(yōu)點(diǎn)就是對有序數(shù)據(jù)的查詢操作不會慢到O(logN)的時間復(fù)雜度。

4.2 紅黑樹和AVL樹的比較

AVL樹的時間復(fù)雜度雖然優(yōu)于紅黑樹，但是對于現(xiàn)在的計算機(jī)，cpu太快，可以忽略性能差異
紅黑樹的插入刪除比AVL樹更便于控制操作
紅黑樹整體性能略優(yōu)于AVL樹（紅黑樹旋轉(zhuǎn)情況少于AVL樹）

五、紅黑樹的等價變換

上面這顆紅黑樹，我們來將所有的紅色節(jié)點(diǎn)上移到和他們的父節(jié)點(diǎn)同一高度上，就會形成如下結(jié)構(gòu)

這個結(jié)構(gòu)很明顯，就是一棵四階B樹（一個節(jié)點(diǎn)最多放三個數(shù)據(jù)），如果畫成如下的樣子大家應(yīng)該就能看的更清晰了。

由上面的等價變換我們就可以得到如下結(jié)論：

紅黑樹和 4階B樹（2-3-4樹）具有等價性
黑色節(jié)點(diǎn)與它的紅色子節(jié)點(diǎn)融合在一起，形成1個B樹節(jié)點(diǎn)
紅黑樹的黑色節(jié)點(diǎn)個數(shù) 與 4階B樹的節(jié)點(diǎn)總個數(shù)相等
在所有的B樹節(jié)點(diǎn)中，永遠(yuǎn)是黑色節(jié)點(diǎn)是父節(jié)點(diǎn)，紅色節(jié)點(diǎn)是子節(jié)點(diǎn)。黑色節(jié)點(diǎn)在中間，紅色節(jié)點(diǎn)在兩邊。

我們可以利用四階B樹與紅黑樹等價的性質(zhì)，以紅黑樹轉(zhuǎn)換成B樹之后的節(jié)點(diǎn)情況來進(jìn)行一個分類

六、紅黑樹的操作

紅黑樹的基本操作和其他樹形結(jié)構(gòu)一樣，一般都包括查找、插入、刪除等操作。前面說到，紅黑樹是一種自平衡的二叉查找樹，既然是二叉查找樹的一種，那么查找過程和二叉查找樹一樣，比較簡單，這里不再贅述。相對于查找操作，紅黑樹的插入和刪除操作就要復(fù)雜的多。尤其是刪除操作，要處理的情況比較多，下面就來分情況講解。

6.1 旋轉(zhuǎn)操作

在分析插入和刪除操作前，先說明一下旋轉(zhuǎn)操作，這個操作在后續(xù)操作中都會用得到。旋轉(zhuǎn)操作分為左旋和右旋，左旋是將某個節(jié)點(diǎn)旋轉(zhuǎn)為其右孩子的左孩子，而右旋是節(jié)點(diǎn)旋轉(zhuǎn)為其左孩子的右孩子。這話聽起來有點(diǎn)繞，所以還是請看下圖：

上圖包含了左旋和右旋的示意圖，這里以右旋為例進(jìn)行說明，右旋節(jié)點(diǎn) M 的步驟如下：

將節(jié)點(diǎn) M 的左孩子引用指向節(jié)點(diǎn) E 的右孩子
將節(jié)點(diǎn) E 的右孩子引用指向節(jié)點(diǎn) M，完成旋轉(zhuǎn)

旋轉(zhuǎn)操作本身并不復(fù)雜，上面分析了右旋操作，左旋操作與此類似，只是右旋轉(zhuǎn)的逆操作。

6.2 插入操作

紅黑樹的插入過程和二叉查找樹插入過程基本類似，不同的地方在于，紅黑樹插入新節(jié)點(diǎn)后，需要進(jìn)行調(diào)整，以滿足紅黑樹的性質(zhì)。

性質(zhì)1規(guī)定紅黑樹節(jié)點(diǎn)的顏色要么是紅色要么是黑色，那么在插入新節(jié)點(diǎn)時，這個節(jié)點(diǎn)應(yīng)該是紅色還是黑色呢？答案是紅色，原因也不難理解。如果插入的節(jié)點(diǎn)是黑色，那么這個節(jié)點(diǎn)所在路徑比其他路徑多出一個黑色節(jié)點(diǎn)，這個調(diào)整起來會比較麻煩（參考紅黑樹的刪除操作，就知道為啥多一個或少一個黑色節(jié)點(diǎn)時，調(diào)整起來這么麻煩了）。如果插入的節(jié)點(diǎn)是紅色，此時所有路徑上的黑色節(jié)點(diǎn)數(shù)量不變，僅可能會出現(xiàn)兩個連續(xù)的紅色節(jié)點(diǎn)的情況。這種情況下，通過變色和旋轉(zhuǎn)進(jìn)行調(diào)整即可，比之前的簡單多了。所以插入的時候?qū)⒐?jié)點(diǎn)設(shè)置為紅色，可以保證滿足性質(zhì) 1、2、3、5 ，只有性質(zhì)4不一定滿足，需要進(jìn)行相關(guān)調(diào)整。如果是添加根節(jié)點(diǎn)，則將節(jié)點(diǎn)設(shè)定為黑色。

6.2.1 插入操作的所有情況

我們在分析紅黑樹各種插入情況的時候，將其等價轉(zhuǎn)換為B樹，這樣我們能夠更直觀的進(jìn)行分類，首先確定幾條性質(zhì)：

B樹中，新元素必定是添加到葉子節(jié)點(diǎn)中（最底層的節(jié)點(diǎn)）
4階B樹所有節(jié)點(diǎn)的元素個數(shù) x 都符合 1 ≤ x ≤ 3

在上一章節(jié)紅黑樹的等價變換中，我們講到了紅黑樹轉(zhuǎn)換成B樹總共有四種情況，也就是上圖中葉子節(jié)點(diǎn)這四種情況，那么在我們進(jìn)行插入操作的時候，會將節(jié)點(diǎn)插入到所有的葉子節(jié)點(diǎn)中，總共就會有12種情況，其中四種情況滿足紅黑樹的性質(zhì)，8種情況不滿足紅黑樹性質(zhì)。

6.2.1.1滿足紅黑樹性質(zhì)4

有 4 種情況滿足紅黑樹的性質(zhì) 4 ：parent 為黑色節(jié)點(diǎn)。這四種情況不需要做任何額外的處理。

6.2.1.2不滿足紅黑樹性質(zhì)4

有 8 種情況不滿足紅黑樹的性質(zhì) 4 ：parent 為紅色節(jié)點(diǎn)（ Double Red ），其中左面4種屬于B樹節(jié)點(diǎn)上溢的情況（一個4階B樹節(jié)點(diǎn)中最多存放三個數(shù)，這四種情況本來已經(jīng)有3個了，又插入了1個，變成了4個，超出了4階B樹節(jié)點(diǎn)的容量范圍，這種情況稱為上溢）。這八種情況需要進(jìn)行額外的處理。

6.2.2 LL和RR插入情況

如上圖，插入52和60的位置分別是RR情況和LL情況。

RR情況：父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的右節(jié)點(diǎn)，插入節(jié)點(diǎn)為父節(jié)點(diǎn)的右節(jié)點(diǎn)

LL情況：父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的左節(jié)點(diǎn)，插入節(jié)點(diǎn)為父節(jié)點(diǎn)的左節(jié)點(diǎn)

這兩種情況很明顯，插入節(jié)點(diǎn)為紅色，父節(jié)點(diǎn)也為紅色，父節(jié)點(diǎn)的子節(jié)點(diǎn)為紅色顯然違背了紅黑樹的性質(zhì)四，我們需要對這種情況進(jìn)行修復(fù)，使其重新滿足紅黑樹性質(zhì)。

判定條件：uncle 不是紅色節(jié)點(diǎn)。

這里的兩種情況，他們的插入節(jié)點(diǎn)都是沒有叔父節(jié)點(diǎn)的，所以叔父節(jié)點(diǎn)也不可能是紅色。

案例修復(fù)：

我們在紅黑樹等價轉(zhuǎn)換那一章節(jié)也講過了，紅黑樹等價轉(zhuǎn)換成B樹之后，B樹節(jié)點(diǎn)的中間節(jié)點(diǎn)（父節(jié)點(diǎn)）都是黑色，兩邊的節(jié)點(diǎn)（子節(jié)點(diǎn)）都是紅色。但是上面兩種情況插入后，插入位置的B樹節(jié)點(diǎn)并不滿足這個條件，所以我們對其進(jìn)行修復(fù)，使其滿足B樹節(jié)點(diǎn)的條件之后，也就重新恢復(fù)了紅黑樹性質(zhì)。

B樹節(jié)點(diǎn)中的中間節(jié)點(diǎn)大小介于兩個子節(jié)點(diǎn)之間。以上圖RR情況為例，插入節(jié)點(diǎn)52的原父節(jié)點(diǎn)應(yīng)該放在B樹節(jié)點(diǎn)中間的位置，應(yīng)當(dāng)將其染成黑色。插入節(jié)點(diǎn)52的原祖父節(jié)點(diǎn)46，應(yīng)當(dāng)將其轉(zhuǎn)換為插入節(jié)點(diǎn)原父節(jié)點(diǎn)的子節(jié)點(diǎn)，所以將其染成紅色。LL情況同理

完成染色之后，需要對原祖父節(jié)點(diǎn)進(jìn)行單旋操作，來進(jìn)行父節(jié)點(diǎn)，子節(jié)點(diǎn)的重新分配。以上圖為例：

RR情況應(yīng)該原祖父節(jié)點(diǎn)46左旋，將插入節(jié)點(diǎn)的原父節(jié)點(diǎn)50旋轉(zhuǎn)到中間的位置。
LL情況應(yīng)當(dāng)原祖父節(jié)點(diǎn)76右旋，將插入節(jié)點(diǎn)的原父節(jié)點(diǎn)72旋轉(zhuǎn)到中間的位置。

修復(fù)之后的結(jié)果如下圖：

修復(fù)步驟總結(jié)：

parent 染成黑色，grand 染成紅色
grand 進(jìn)行單旋操作
1. LL：右旋轉(zhuǎn)
2. RR：左旋轉(zhuǎn)

6.2.3 LR和RL插入情況

如上圖，插入48和74的位置分別是RL情況和LR情況。

RL情況：父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的右節(jié)點(diǎn)，插入節(jié)點(diǎn)為父節(jié)點(diǎn)的左節(jié)點(diǎn)

LR情況：父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的左節(jié)點(diǎn)，插入節(jié)點(diǎn)為父節(jié)點(diǎn)的右節(jié)點(diǎn)

這兩種情況和上面的兩種情況一樣，插入節(jié)點(diǎn)為紅色，父節(jié)點(diǎn)也為紅色，父節(jié)點(diǎn)的子節(jié)點(diǎn)為紅色顯然違背了紅黑樹的性質(zhì)四，我們需要對這種情況進(jìn)行修復(fù)，使其重新滿足紅黑樹性質(zhì)。

判定條件：uncle 不是紅色節(jié)點(diǎn)。

這兩種情況的插入節(jié)點(diǎn)也是沒有叔父節(jié)點(diǎn)的。

案例修復(fù)：

B樹節(jié)點(diǎn)中的中間節(jié)點(diǎn)大小介于兩個子節(jié)點(diǎn)之間。以上圖RL情況為例，插入節(jié)點(diǎn)48大小介于原父節(jié)點(diǎn)和原祖父節(jié)點(diǎn)之間，它應(yīng)該是B樹節(jié)點(diǎn)中的中間節(jié)點(diǎn)，所以將插入節(jié)點(diǎn)48染成黑色，將原祖父節(jié)點(diǎn)46染成紅色來作為插入節(jié)點(diǎn)的子節(jié)點(diǎn)。LR情況同理

完成染色之后，需要進(jìn)行雙旋操作，來進(jìn)行父節(jié)點(diǎn)，子節(jié)點(diǎn)的重新分配。以上圖為例：

RL情況應(yīng)該原父節(jié)點(diǎn)50右旋，將插入節(jié)點(diǎn)48上移到原父節(jié)點(diǎn)50的高度，然后將插入節(jié)點(diǎn)的原祖父節(jié)點(diǎn)46進(jìn)行左旋，將插入節(jié)點(diǎn)48移動到中間位置，成為中間節(jié)點(diǎn)。
LR情況應(yīng)該原父節(jié)點(diǎn)72左旋，將插入節(jié)點(diǎn)74上移到原父節(jié)點(diǎn)72的高度，然后將插入節(jié)點(diǎn)的原祖父節(jié)點(diǎn)76進(jìn)行右旋，將插入節(jié)點(diǎn)74移動到中間位置，成為中間節(jié)點(diǎn)。

修復(fù)之后的結(jié)果如下圖：

修復(fù)步驟總結(jié)：

插入節(jié)點(diǎn)染成黑色，grand 染成紅色
進(jìn)行雙旋操作
- LR：parent 左旋轉(zhuǎn)， grand 右旋轉(zhuǎn)
- RL：parent 右旋轉(zhuǎn)， grand 左旋轉(zhuǎn)

6.2.4 上溢的LL插入情況

如上圖，插入10的位置是上溢的LL情況。

上溢LL情況：父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的左節(jié)點(diǎn)，插入節(jié)點(diǎn)為父節(jié)點(diǎn)的左節(jié)點(diǎn)。并且構(gòu)成的新的B樹節(jié)點(diǎn)已經(jīng)超過了B樹節(jié)點(diǎn)容量大小范圍。

這種情況和之前非上溢的四種情況一樣，插入節(jié)點(diǎn)為紅色，父節(jié)點(diǎn)也為紅色，父節(jié)點(diǎn)的子節(jié)點(diǎn)為紅色顯然違背了紅黑樹的性質(zhì)四，我們需要對這種情況進(jìn)行修復(fù)，使其重新滿足紅黑樹性質(zhì)。

判定條件：uncle 是紅色節(jié)點(diǎn)。滿足這個條件的就都是上溢的情況，上溢的修復(fù)只需要染色，不需要旋轉(zhuǎn)。

案例修復(fù)：

像這種上溢的情況，就需要從溢出的B樹節(jié)點(diǎn)中選出一個節(jié)點(diǎn)進(jìn)行向上合并，選擇B樹節(jié)點(diǎn)中中間的樹去進(jìn)行向上合并，這里中間的兩個節(jié)點(diǎn)就是原父節(jié)點(diǎn)17和原祖父節(jié)點(diǎn)25，選這兩個哪一個向上合并都是對的，但是我們最好選擇以后方便操作的，很顯然，應(yīng)該選擇原祖父節(jié)點(diǎn)25來進(jìn)行向上合并，因?yàn)橄蛏虾喜⒕褪呛妥钌蠈拥?8和55來組合成新的B樹節(jié)點(diǎn)，向上合并的節(jié)點(diǎn)肯定是一個子節(jié)點(diǎn)，需要與上層相連，而原祖父節(jié)點(diǎn)25本身就已經(jīng)和上層連接了，相對更加方便后續(xù)的操作。原祖父節(jié)點(diǎn)向上合并后，將其染成紅色。

原祖父節(jié)點(diǎn)25向上合并后，它原來左右兩邊的節(jié)點(diǎn)需要分裂成兩個子樹，也就是原父節(jié)點(diǎn)17和插入節(jié)點(diǎn)10形成一個子樹，原叔父節(jié)點(diǎn)33形成一個子樹。這兩個分裂形成的樹都是以后25的子樹。左邊的子樹由原父節(jié)點(diǎn)作為中間節(jié)點(diǎn)，染成黑色，右邊的子樹由原叔父節(jié)點(diǎn)作為中間節(jié)點(diǎn)，染成黑色。

修復(fù)之后的結(jié)果如下圖：

修復(fù)步驟總結(jié)：

parent、uncle 染成黑色
grand 向上合并
1. 將向上合并的grand染成紅色，相對上一層，就當(dāng)做是新添加的節(jié)點(diǎn)，再次來一遍插入情況的判斷，進(jìn)行處理。

grand 向上合并時，可能繼續(xù)發(fā)生上溢。這種情況就繼續(xù)遞歸調(diào)用修復(fù)方法就可以了。若上溢持續(xù)到根節(jié)點(diǎn)，只需將根節(jié)點(diǎn)染成黑色即可（這個意思就是說斷向上上溢，一直上溢到了B樹的根節(jié)點(diǎn)位置了，只需要將向上合并的節(jié)點(diǎn)變成黑色作為紅黑樹的根節(jié)點(diǎn)即可。因?yàn)閺腂樹根節(jié)點(diǎn)選擇出來上溢的節(jié)點(diǎn)，肯定就是作為整個紅黑樹的根節(jié)點(diǎn)了）。

6.2.5 上溢的RR插入情況

如上圖，插入36的位置是上溢的RR情況。

上溢RR情況：父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的右節(jié)點(diǎn)，插入節(jié)點(diǎn)為父節(jié)點(diǎn)的右節(jié)點(diǎn)。并且構(gòu)成的新的B樹節(jié)點(diǎn)已經(jīng)超過了B樹節(jié)點(diǎn)容量大小范圍。

判定條件：uncle 是紅色節(jié)點(diǎn)

案例修復(fù)：

上溢RR情況的修復(fù)，和上溢LL情況基本一致，只是修復(fù)的位置不同，這里中間的兩個節(jié)點(diǎn)就是原父節(jié)點(diǎn)33和原祖父節(jié)點(diǎn)25，選擇原祖父節(jié)點(diǎn)25來進(jìn)行向上合并，原祖父節(jié)點(diǎn)向上合并后，將其染成紅色。

原祖父節(jié)點(diǎn)25向上合并后，它原來左右兩邊的節(jié)點(diǎn)需要分裂成兩個子樹，也就是原父節(jié)點(diǎn)33和插入節(jié)點(diǎn)36形成一個子樹，原叔父節(jié)點(diǎn)17形成一個子樹。這兩個分裂形成的樹都是以后25的子樹。左邊的子樹由原叔父節(jié)點(diǎn)作為中間節(jié)點(diǎn)，染成黑色，右邊的子樹由原父節(jié)點(diǎn)作為中間節(jié)點(diǎn)，染成黑色。

修復(fù)之后的結(jié)果如下圖：

修復(fù)步驟總結(jié)：

parent、uncle 染成黑色
grand 向上合并
- 染成紅色（其實(shí)染成紅色就已經(jīng)是完成了向上合并，因?yàn)樽娓腹?jié)點(diǎn)和祖父節(jié)點(diǎn)的父節(jié)點(diǎn)的連接指向并沒有變），當(dāng)做是新添加的節(jié)點(diǎn)進(jìn)行處理

6.2.6 上溢的LR插入情況

如上圖，插入20的位置是上溢的LR情況。

上溢LR情況：父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的左節(jié)點(diǎn)，插入節(jié)點(diǎn)為父節(jié)點(diǎn)的右節(jié)點(diǎn)。并且構(gòu)成的新的B樹節(jié)點(diǎn)已經(jīng)超過了B樹節(jié)點(diǎn)容量大小范圍。

判定條件：uncle 是紅色節(jié)點(diǎn)

案例修復(fù)：

上溢LR情況的修復(fù)，和其他上溢情況基本一致，只是修復(fù)的位置不同，這里中間的兩個節(jié)點(diǎn)就是原父節(jié)點(diǎn)17和原祖父節(jié)點(diǎn)25，選擇原祖父節(jié)點(diǎn)25來進(jìn)行向上合并，原祖父節(jié)點(diǎn)向上合并后，將其染成紅色。

原祖父節(jié)點(diǎn)25向上合并后，它原來左右兩邊的節(jié)點(diǎn)需要分裂成兩個子樹，也就是原父節(jié)點(diǎn)17和插入節(jié)點(diǎn)20形成一個子樹，原叔父節(jié)點(diǎn)33形成一個子樹。這兩個分裂形成的樹都是以后25的子樹。左邊的子樹由原父節(jié)點(diǎn)作為中間節(jié)點(diǎn)，染成黑色，右邊的子樹由原叔父節(jié)點(diǎn)作為中間節(jié)點(diǎn)，染成黑色。

修復(fù)之后的結(jié)果如下圖：

修復(fù)步驟總結(jié)：

parent、uncle 染成黑色
grand 向上合并
- 染成紅色，當(dāng)做是新添加的節(jié)點(diǎn)進(jìn)行處理

6.2.7 上溢的RL插入情況

如上圖，插入30的位置是上溢的RL情況。

上溢RL情況：父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的右節(jié)點(diǎn)，插入節(jié)點(diǎn)為父節(jié)點(diǎn)的左節(jié)點(diǎn)。并且構(gòu)成的新的B樹節(jié)點(diǎn)已經(jīng)超過了B樹節(jié)點(diǎn)容量大小范圍。

判定條件：uncle 是紅色節(jié)點(diǎn)

案例修復(fù)：

上溢RL情況的修復(fù)，和其他上溢情況基本一致，只是修復(fù)的位置不同，這里中間的兩個節(jié)點(diǎn)就是原父節(jié)點(diǎn)33和原祖父節(jié)點(diǎn)25，選擇原祖父節(jié)點(diǎn)25來進(jìn)行向上合并，原祖父節(jié)點(diǎn)向上合并后，將其染成紅色。

原祖父節(jié)點(diǎn)25向上合并后，它原來左右兩邊的節(jié)點(diǎn)需要分裂成兩個子樹，也就是原父節(jié)點(diǎn)33和插入節(jié)點(diǎn)30形成一個子樹，原叔父節(jié)點(diǎn)17形成一個子樹。這兩個分裂形成的樹都是以后25的子樹。左邊的子樹由原叔父節(jié)點(diǎn)作為中間節(jié)點(diǎn)，染成黑色，右邊的子樹由原父節(jié)點(diǎn)作為中間節(jié)點(diǎn)，染成黑色。

修復(fù)之后的結(jié)果如下圖：

修復(fù)步驟總結(jié)：

parent、uncle 染成黑色
grand 向上合并
- 染成黑色，當(dāng)做是新添加的節(jié)點(diǎn)進(jìn)行處理

6.2.8 插入情況總結(jié)

插入一共有12種情況：

插入節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色的情況有4種
這種情況仍然會維持紅黑樹的性質(zhì)，則不需要進(jìn)行額外處理。
插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的情況有8種
這種情況不滿足紅黑樹的性質(zhì)4，需要進(jìn)行額外的修復(fù)處理。
這8種情況中：
1. 叔父節(jié)點(diǎn)不是紅色的情況有4種
  這些情況都是非上溢，需要通過重新染色和旋轉(zhuǎn)來進(jìn)行修復(fù)
2. 叔父節(jié)點(diǎn)是紅色的情況有4種
  這些情況都是上溢的，只需要通過祖父節(jié)點(diǎn)上溢合并和染色即可完成修復(fù)

6.3 刪除操作

相較于插入操作，紅黑樹的刪除操作則要更為復(fù)雜一些。B樹中，最后真正被刪除的元素都在葉子節(jié)點(diǎn)中。所以在紅黑樹中，被刪除的節(jié)點(diǎn)一定也在最后一層。

6.3.1 刪除操作的所有情況

上面我們說刪除節(jié)點(diǎn)一定都在最后一層，最后一層有紅色節(jié)點(diǎn)和黑色節(jié)點(diǎn)，我們就以刪除節(jié)點(diǎn)的顏色來區(qū)分刪除操作的所有情況。

6.3.1.1刪除紅色節(jié)點(diǎn)

如果刪除的節(jié)點(diǎn)是紅色直接刪除，不用作任何調(diào)整。因?yàn)閯h除最后一層的紅色節(jié)點(diǎn)，并沒有影響紅黑樹的任何性質(zhì)。

6.3.1.2刪除黑色節(jié)點(diǎn)

有3種情況：

擁有 2 個紅色子節(jié)點(diǎn)的黑色節(jié)點(diǎn)
- 不可能被直接刪除，因?yàn)闀宜淖庸?jié)點(diǎn)替代刪除，因此不用考慮這種情況
擁有 1 個紅色子節(jié)點(diǎn)的黑色節(jié)點(diǎn)
黑色葉子節(jié)點(diǎn)

6.3.2 刪除擁有1個紅色子節(jié)點(diǎn)的黑色節(jié)點(diǎn)

刪除擁有1個紅色子節(jié)點(diǎn)的黑色節(jié)點(diǎn)的情況，是需要我們做相關(guān)的處理的。這里刪除的就是節(jié)點(diǎn)46和76，他們只有一個紅色子節(jié)點(diǎn)。

對于一個二叉樹來說，刪除一個度為1的節(jié)點(diǎn)（度指的是一個節(jié)點(diǎn)的子節(jié)點(diǎn)個數(shù)），將其刪除后需要用它唯一的子節(jié)點(diǎn)來進(jìn)行替換。而紅黑樹的這種情況的判定條件，就是判定要替代刪除節(jié)點(diǎn)的子節(jié)點(diǎn)是不是紅色

判定條件：用以替代的子節(jié)點(diǎn)是紅色節(jié)點(diǎn)

案例修復(fù)：

刪除黑色節(jié)點(diǎn)46和76

第一步：

將46與父節(jié)點(diǎn)的連接斷開

第二步：

46唯一的紅色子節(jié)點(diǎn)50作為代替46的節(jié)點(diǎn)，將其與46的父節(jié)點(diǎn)進(jìn)行連接

第三步：

斷開46與50的連接，將46刪除

刪除節(jié)點(diǎn)76的過程與刪除節(jié)點(diǎn)46相同

第一步：

第二步：

第三步：

但是現(xiàn)在我們發(fā)現(xiàn)，80是紅色節(jié)點(diǎn)，它的子節(jié)點(diǎn)72還是紅色節(jié)點(diǎn)，這樣明顯不符合紅黑樹的性質(zhì)，還需要進(jìn)一步修復(fù)。

將替代的子節(jié)點(diǎn)染成黑色即可保持紅黑樹性質(zhì)，修復(fù)完成

修復(fù)步驟總結(jié)：

用刪除節(jié)點(diǎn)的唯一子節(jié)點(diǎn)對其進(jìn)行替代
將替代節(jié)點(diǎn)染成黑色

6.3.3 刪除黑色葉子節(jié)點(diǎn)——刪除節(jié)點(diǎn)為根節(jié)點(diǎn)

一棵紅黑樹只有一個黑色根節(jié)點(diǎn)（也就是唯一的一個葉子節(jié)點(diǎn)，整個紅黑樹只有這一個黑色節(jié)點(diǎn)），可直接刪除該節(jié)點(diǎn)，無需做其他操作。

6.3.4 刪除黑色葉子節(jié)點(diǎn)——刪除節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為黑色

講這種刪除情況前先舉一個例子

上面這個我們要刪除節(jié)點(diǎn)88，該節(jié)點(diǎn)為黑色葉子節(jié)點(diǎn)，它的兄弟節(jié)點(diǎn)是黑色76。從B樹的角度來看，如果刪除88，因?yàn)樗碾AB樹的節(jié)點(diǎn)中最少存有1個元素，如果不足，則會造成下溢。也就是需要從88的兄弟節(jié)點(diǎn)中借一個子節(jié)點(diǎn)出來。這就是這一節(jié)我們討論的刪除情況的核心修復(fù)思想。

6.3.4.1兄弟節(jié)點(diǎn)至少有1個紅色子節(jié)點(diǎn)

下面三個圖分別對應(yīng)著兄弟節(jié)點(diǎn)至少有一個紅色子節(jié)點(diǎn)的三種情況。刪除節(jié)點(diǎn)為88，為黑色葉子節(jié)點(diǎn)，它的兄弟節(jié)點(diǎn)是76，為黑色。兄弟節(jié)點(diǎn)76都至少有一個紅色子節(jié)點(diǎn)，三種情況分別為76擁有一個紅色右子節(jié)點(diǎn)，76擁有一個紅色左子節(jié)點(diǎn)，76擁有兩個紅色子節(jié)點(diǎn)。因?yàn)樾值芄?jié)點(diǎn)有紅色子節(jié)點(diǎn)，所以可以借出一個節(jié)點(diǎn)來進(jìn)行修復(fù)。

這三種情況，黑色葉子節(jié)點(diǎn)被刪除后，會導(dǎo)致B樹節(jié)點(diǎn)下溢（比如刪除88），就可以從兄弟節(jié)點(diǎn)中借出一個紅色子節(jié)點(diǎn)來進(jìn)行修復(fù)。

判定條件：兄弟節(jié)點(diǎn)至少有 1 個紅色子節(jié)點(diǎn)

案例修復(fù)：

1、兄弟節(jié)點(diǎn)有一個右子節(jié)點(diǎn)：

先將88節(jié)點(diǎn)刪除

刪掉之后，從B樹的角度來看就出現(xiàn)了下溢，這個時候就需要父節(jié)點(diǎn)下來，在兄弟節(jié)點(diǎn)的子結(jié)點(diǎn)中找一個，將他升上去代替。具體的實(shí)現(xiàn)就是要對節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)。

我們可以看出，80、76、78組成的樹是一個LR的情況，先對76進(jìn)行左旋轉(zhuǎn)（可以將76看作父節(jié)點(diǎn)），這樣78就上去了，再對80進(jìn)行右旋轉(zhuǎn)（可以將80看成祖父節(jié)點(diǎn)），80就下去了。

旋轉(zhuǎn)完了之后，如上圖。將旋轉(zhuǎn)完之后的中心節(jié)點(diǎn)（就是78、76、80組成的樹的最中心的節(jié)點(diǎn)，這里就是78）進(jìn)行重新染色，繼承刪除節(jié)點(diǎn)的父節(jié)點(diǎn)80的顏色。最后再將78、76、80組成的樹的左右兩個節(jié)點(diǎn)染成黑色即可完成修復(fù)。

2、兄弟節(jié)點(diǎn)有一個左子節(jié)點(diǎn)：

先將88節(jié)點(diǎn)刪除

我們可以看出，80、76、72組成的樹是一個LL的情況，直接對80進(jìn)行右旋（將80看成是祖父節(jié)點(diǎn)）。

旋轉(zhuǎn)完了之后，如上圖。將旋轉(zhuǎn)完之后的中心節(jié)點(diǎn)（就是76、72、80組成的樹的最中心的節(jié)點(diǎn)，這里就是76）進(jìn)行重新染色，繼承刪除節(jié)點(diǎn)的父節(jié)點(diǎn)80的顏色。最后再將76、72、80組成的樹的左右兩個節(jié)點(diǎn)染成黑色即可完成修復(fù)。

3、兄弟節(jié)點(diǎn)有兩個左右子節(jié)點(diǎn)：

先將88節(jié)點(diǎn)刪除

刪除之后，其實(shí)可以有兩種旋轉(zhuǎn)可以進(jìn)行修復(fù)，既可以使用LL方式進(jìn)行旋轉(zhuǎn)，也可以使用LR方式進(jìn)行旋轉(zhuǎn)。但是因?yàn)長L方式只需要旋轉(zhuǎn)一次，我們就選用LL方式。

直接對80進(jìn)行右旋

旋轉(zhuǎn)完了之后，如上圖。將旋轉(zhuǎn)完之后的中心節(jié)點(diǎn)（就是78、72、76、80組成的樹的最中心的節(jié)點(diǎn)，這里就是76）進(jìn)行重新染色，繼承刪除節(jié)點(diǎn)的父節(jié)點(diǎn)80的顏色。最后再將78、72、76、80組成的樹的左右兩個節(jié)點(diǎn)染成黑色即可完成修復(fù)。

修復(fù)步驟總結(jié)：

進(jìn)行旋轉(zhuǎn)操作
旋轉(zhuǎn)之后的中心節(jié)點(diǎn)繼承父節(jié)點(diǎn)（刪除節(jié)點(diǎn)的父節(jié)點(diǎn)）的顏色
旋轉(zhuǎn)之后的左右節(jié)點(diǎn)染為黑色

6.3.4.2兄弟節(jié)點(diǎn)沒有紅色子節(jié)點(diǎn)

當(dāng)刪除節(jié)點(diǎn)的兄弟節(jié)點(diǎn)沒有紅色節(jié)點(diǎn)可以借出的情況下，就需要父節(jié)點(diǎn)來向下合并進(jìn)行修復(fù)，父節(jié)點(diǎn)向下和兄弟節(jié)點(diǎn)合并成新的B樹節(jié)點(diǎn)來解決下溢。

判定條件：兄弟節(jié)點(diǎn)沒有1個紅色子節(jié)點(diǎn)

案例修復(fù)：

1、父節(jié)點(diǎn)為紅色：

刪除節(jié)點(diǎn)88，出現(xiàn)下溢

因?yàn)樾值芄?jié)點(diǎn)76沒有可以借出的紅色節(jié)點(diǎn)，所以需要父節(jié)點(diǎn)80來向下與76合并進(jìn)行修復(fù)

將兄弟節(jié)點(diǎn)76染成紅色，父節(jié)點(diǎn)80染成黑色即可完成修復(fù)

2、父節(jié)點(diǎn)為黑色：

刪除節(jié)點(diǎn)88，刪除之后節(jié)點(diǎn)88就會出現(xiàn)下溢

刪除之后父節(jié)點(diǎn)80應(yīng)該向下合并進(jìn)行修復(fù)，但是因?yàn)楦腹?jié)點(diǎn)80為黑色，如果向下合并之后，其實(shí)就相當(dāng)于80這個節(jié)點(diǎn)也出現(xiàn)了下溢。

這個時候只需要把父節(jié)點(diǎn)當(dāng)作被刪除的節(jié)點(diǎn)進(jìn)行處理即可

修復(fù)步驟總結(jié)：

父節(jié)點(diǎn)向下與兄弟節(jié)點(diǎn)進(jìn)行合并
將兄弟染成紅色、父節(jié)點(diǎn)染成黑色即可修復(fù)紅黑樹性質(zhì)
- 如果父節(jié)點(diǎn)是黑色，直接將父節(jié)點(diǎn)當(dāng)成被刪除的節(jié)點(diǎn)處理，來修復(fù)父節(jié)點(diǎn)的下溢情況

6.3.5 刪除黑色葉子節(jié)點(diǎn)——刪除節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為紅色

如果刪除節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為紅色，這樣刪除節(jié)點(diǎn)出現(xiàn)下溢后沒辦法通過兄弟節(jié)點(diǎn)來進(jìn)行修復(fù)。這就需要先把紅黑樹轉(zhuǎn)換為兄弟節(jié)點(diǎn)為黑色的情況，就可以套用上面講的修復(fù)方法來進(jìn)行修復(fù)了。

判定條件：兄弟節(jié)點(diǎn)是紅色

案例修復(fù)：

刪除88節(jié)點(diǎn)之前，需要先轉(zhuǎn)換成兄弟節(jié)點(diǎn)為黑色的情況，當(dāng)前88的兄弟節(jié)點(diǎn)是紅色55?？梢詫⑵淇醋鱈L情況，對父節(jié)點(diǎn)88進(jìn)行右旋轉(zhuǎn)，這樣55就被移動上去了，成了80的父節(jié)點(diǎn)。76也被移動上去了，成了80的子節(jié)點(diǎn)。

這種情況，刪除節(jié)點(diǎn)88的兄弟節(jié)點(diǎn)就變成了黑色，并且沒有紅色子節(jié)點(diǎn)，可以繼續(xù)套用之前講的方法來進(jìn)行修復(fù)了。

刪除掉88，將80染成黑色，76染成紅色，完成修復(fù)。

修復(fù)步驟總結(jié)：

兄弟節(jié)點(diǎn)染成 BLACK，父節(jié)點(diǎn)染成染成 RED，對父節(jié)點(diǎn)進(jìn)行右旋
于是又回到兄弟節(jié)點(diǎn)是黑色的情況（侄子節(jié)點(diǎn)變?yōu)樾值芄?jié)點(diǎn)），繼續(xù)使用兄弟節(jié)點(diǎn)為黑色的方法進(jìn)行修復(fù)

七、紅黑樹的平衡

AVL是靠平衡因子來保持平衡的，比如平衡因子為1，那么左右子樹的高度差就不能超過1，是一種強(qiáng)平衡。

對于紅黑樹而言，為何那5條性質(zhì)，就能保證紅黑樹是平衡的？

因?yàn)槟?條性質(zhì)，可以保證紅黑樹等價于4階B樹

B樹比較矮，它本身就是平衡的，高度越小越平衡。

紅黑樹就是能保證這個樹高度不會特別高，紅黑樹的大高度是 2 ? log2(n + 1) ，依然是 O(logn) 級別，因?yàn)楦叨炔粫艽筮M(jìn)而維持一種相對平衡的狀態(tài)。相比AVL樹，紅黑樹的平衡標(biāo)準(zhǔn)比較寬松：沒有一條路徑會大于其他路徑的2倍。這是是一種弱平衡、黑高度平衡（黑高度只算黑色節(jié)點(diǎn)個數(shù)，紅黑樹的任何一條路徑的黑色節(jié)點(diǎn)數(shù)一樣，則黑高度都是一樣）。

八、紅黑樹的平均時間復(fù)雜度

搜索：O(logn)
添加：O(logn)，O(1) 次的旋轉(zhuǎn)操作
刪除：O(logn)，O(1) 次的旋轉(zhuǎn)操作

九、AVL樹 vs 紅黑樹 9.1 AVL樹

平衡標(biāo)準(zhǔn)比較嚴(yán)格：每個左右子樹的高度差不超過1
大高度是 1.44 ? log2 n + 2 ? 1.328（100W個節(jié)點(diǎn)，AVL樹大樹高28）
搜索、添加、刪除都是 O(logn) 復(fù)雜度，其中添加僅需 O(1) 次旋轉(zhuǎn)調(diào)整、刪除最多需要 O(logn) 次旋轉(zhuǎn)調(diào)整

9.2 紅黑樹

平衡標(biāo)準(zhǔn)比較寬松：沒有一條路徑會大于其他路徑的2倍
大高度是 2 ? log2(n + 1)（ 100W個節(jié)點(diǎn)，紅黑樹大樹高40）
搜索、添加、刪除都是 O(logn) 復(fù)雜度，其中添加、刪除都僅需 O(1) 次旋轉(zhuǎn)調(diào)整

9.3 如何選擇

搜索的次數(shù)遠(yuǎn)遠(yuǎn)大于插入和刪除，選擇AVL樹；搜索、插入、刪除次數(shù)幾乎差不多，選擇紅黑樹
相對于AVL樹來說，紅黑樹犧牲了部分平衡性以換取插入/刪除操作時少量的旋轉(zhuǎn)操作，整體來說性能要優(yōu)于AVL樹
紅黑樹的平均統(tǒng)計性能優(yōu)于AVL樹，實(shí)際應(yīng)用中更多選擇使用紅黑樹

9.4 案例對比

10, 35, 47, 11, 5, 57, 39, 14, 27, 26, 84, 75, 63, 41, 37, 24, 96組成一棵樹

9.4.1 二叉搜索樹

非常不平衡

9.4.2 AVL樹

最平衡

9.4.3 紅黑樹

相對比較平衡

相關(guān)文章：【Java集合】HashMap系列（一）——底層數(shù)據(jù)結(jié)構(gòu)分析
?【Java集合】HashMap系列（二）——底層源碼分析
【Java集合】HashMap系列（三）——TreeNode內(nèi)部類源碼分析
?【Java集合】一文快速了解HashMap底層原理

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文題目：【數(shù)據(jù)結(jié)構(gòu)】史上最好理解的紅黑樹講解，讓你徹底搞懂紅黑樹-創(chuàng)新互聯(lián)
分享URL：http://www.rwnh.cn/article0/doegoo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、搜索引擎優(yōu)化、ChatGPT、動態(tài)網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

中文字幕日韩精品一区二区免费_精品一区二区三区国产精品无卡在_国精品无码专区一区二区三区_国产αv三级中文在线

【數(shù)據(jù)結(jié)構(gòu)】史上最好理解的紅黑樹講解，讓你徹底搞懂紅黑樹-創(chuàng)新互聯(lián)