資料結構之紅黑樹，二進制的奇妙冒險！

目錄

簡述

1. 何為紅黑樹

2. 紅黑樹由來

3. 樹平衡手段

4. 平衡限制條件

5. 增刪節點邏輯

1. 增加節點

2. 洗掉節點

6. 紅黑狀態

1. 平衡限制帶來的優化

2. 相對深度計算

3. 旋轉的紅黑狀態變化

4. 洗掉的紅黑狀態變化

5. 惰性檢查

Cheers！

要說在程式員間廣為人知而又頗具難度的資料結構，紅黑樹算是首當其沖，如果掌握其原理，茶余飯后也能增加一份吹牛資本，但網上大量博文介紹均以紅黑樹性質證明其結構可行（以結果證明原因？），讓人著實費解，本文將從紅黑樹設計目的出發分析其原理構成，希望能為大家提供新的理解思路，當然，博主才疏學淺，如有漏洞或錯誤歡迎在評論區指出，

那么事不宜遲，各位看官就同我來看看今日的瞎掰小知識吧，

簡述

本篇博客較長，在此簡述紅黑樹的設計思路，若看官們對部分細節存在疑問可根據目錄跳轉查看詳細內容與證明，

紅黑樹源于二叉排序樹，在原基礎上通過左右旋進行樹深度平衡，并且以"左右節點的子樹最小深度之差不超過1"作為是否執行平衡操作的判斷條件，其紅黑狀態設計目的是為了優化各個子樹間的深度比較方法，用紅（1）黑（0）在二叉樹上進行二進制的加減法運算，并實作子樹間的相對深度表達，其中對于二進制加法進位還增加了惰性檢查機制以降低樹平衡頻率，

大佬們制作的在線紅黑樹操作模擬網頁：紅黑樹模擬，用于學習與驗證比較方便，

1. 何為紅黑樹

紅黑樹是一種具備自排序性質的資料結構，且每次操作（增刪改查）的時間復雜度均為O(logN)，自排序性質再加上高性能使得紅黑樹在各種場景中被應用，如c++中stl的set與map結構，還有java中的hashmap（JDK1.8版本中采用了哈希表+鏈表+紅黑樹的結構），當然hashmap也是一種優秀的資料結構，博主在之后的文章中會對其進行介紹，

2. 紅黑樹由來

其最初設想來源于二叉排序樹的缺陷：若不進行干預，二叉排序樹的時間復雜度O(N*logN)可能會隨著資料寫入降低至最低O(N*N)水平，退化為鏈表結構，為了解決這一問題，諸多大佬們提出了樹的自平衡概念，在每次操作中不斷平衡樹結構讓其接近于完全二叉樹結構，從而維持時間復雜度在O(N*logN)水平，

在此基礎上，演變出了兩種有名的平衡二叉樹，AVL樹與紅黑樹，兩者原理類似，但AVL樹的平衡限制條件更高，為"任意節點左右子樹的深度差最大為1"，所以在增刪操作中，觸發平衡策略的頻率較高，而紅黑樹更偏向于工業化應用，通過適當放寬平衡限制條件，換取了更低頻率的平衡操作，因此在高讀寫的業務場景中，紅黑樹的表現會更優秀一些，而在高讀低寫的業務場景中，AVL樹可能更有優勢，當然，除非追求特定方面的極致性能，一般情況下使用紅黑樹已足夠，

3. 樹平衡手段

對于以下這顆失衡的二叉排序樹，各位看官們應該都能想到其平衡辦法：把根節點10轉變為節點18的左子節點，各節點的樹深度就平均了，且其仍然保持著二叉排序樹的性質（左節點總小于父節點，而右節點總大于父節點），

這實際上就是樹平衡中左旋的雛形（相對的也有右旋），通過調整右子節點與父節點的關系，從而實作左右子樹的深度調整，此時各位看官可能有話想說：舉例模型過于簡單，如果18節點存在左子節點那不是沖突了嗎？正好，我們接下來看一例完全的樹結構模型，

圖中LL/LR/RL/RR并不是單一的一個節點（之后的大部分舉例中也都如此），而是代表了左節點L的左右子樹（LL與LR），與右節點R的左右子樹(RL與RR)，可以確認的是在整個左旋程序中，涉及變化的只有三個部分：M、R節點以及RL子樹，之前提出的問題在該圖得到了解答：當右子節點R成為父節點M的父節點時，父節點M就空出了其右子樹的位置，此時將右子樹被替換下來的左子樹(RL)接替到該位置，左旋操作便完成了，

當然，一切要按規矩來，子樹RL之所以能接替在節點M的右子分支上，是因為二叉排序樹的性質：當前節點右子樹R下的值均大于當前節點M的值，那么節點M的右子樹R的左子樹RL，其所有值也必然大于M，將其接替在節點M的右子分支上并不會破壞二叉排序樹的性質，同理，RR子樹接替在節點M的右子分支上也不會破壞二叉排序樹性質（雖然不需要這樣做），

從上述例子中可以看出，該方法可通用于二叉排序樹上任何節點并保持其性質穩定，而其達到的具體效果如何呢？根據圖示，左旋的影響為：子樹LL/LR深度均+1，子樹RL深度不變，子樹RR深度-1，

了解這一點對后續設計平衡策略至關重要，畢竟調整樹深度全依賴于左右旋，剩下還有右旋的操作方式與影響，相信各位看官能根據左旋進行推敲，這邊直接上結論，

右旋的影響為：子樹RL/RR深度均+1，子樹LR深度不變，子樹LL深度-1，

為了方便記憶，可以這樣理解左右旋，左旋：將節點從右邊分到左邊，右旋：將節點從左邊分到右邊，

講回兩種操作的深度影響，可以看到僅有LL或者RR才會出現深度降低，同時另一側樹深度上升，在完整的應用場景里，這還缺少了降低LR和RL子樹深度的方法，這時候可能有看官想到了：如果在LL/LR/RL/RR四個子樹里LR深度最大且超出限制，那就先基于L和LR左旋，把深度交換一部分給LL，讓LL變成四個子樹中深度最大的，然后就可以基于L和M右旋了，同樣，可以推理降低RL子樹深度的方式，

將不同場景的深度降低方式總結下來，一共是四種（不用特地記憶，理解即可）：

1）降低LL：直接右旋

2）降低LR：先左旋，和LL進行深度調整，最后右旋

3）降低RL：先右旋，和RR進行深度調整，最后左旋

4）降低RR：直接左旋

各位看官看到這里辛苦了，可以先捋捋思路，對博主提供的看點進行驗證推翻，例如在LL/LR/RL/RR四個子樹的模型下，出現某一子樹深度最大的情況如何平衡，當然，能用左右旋以外的方法解決最好，請務必在評論區與博主分享一下，

4. 平衡限制條件

既然調整樹深度的工具已經到手，就可以將這顆二叉排序樹修剪成我們想要的樣子了，接下來請大家自由發揮，

常見的平衡限制條件基本是與樹深度相關的，比如最大深度 / 最小深度，亦或是兩者并用（AVL樹），另外平衡限制條件對樹上任意節點都生效，這一點請勿遺漏，

對于AVL樹來說，其要求為左右子樹互相之間的最大深度 - 最小深度之差不超過1，若超過則進行平衡，如果我們想要打造一顆自己的平衡二叉樹，設定的平衡限制條件必須能明確樹的傾斜邊界，即任何情況下樹中最大深度和最小深度的葉子節點深度之差是可確定范圍的，否則樹歪起來沒有限制可就糟糕了，

講了這么多都是虛的，不如實際動手設計一顆平衡二叉樹，我們暫定平衡限制條件為"左右子樹的最大深度之差不超過1"，其平衡邊界是否為可確定的呢？來即刻探究一下吧，

用于驗證的樹模型結構可以略微簡化，默認右子樹的深度總小于左子樹，這樣最大深度就位于最左邊的左子樹上，最小深度則位于最右邊的右子樹上，固定好左端子樹最大深度為K，再加上之前預設的平衡限制條件就可以得到下圖（L/RL1/RL2等都代表一顆子樹，其子節點就不畫出來了）：

從圖中可以觀察到，RL1節點的最大深度為K-1（K為樹最大深度），但若除去父節點的深度，留給RL1自己的深度僅有K-3（減去M/R兩個節點深度），同樣可得RL2自身深度為K-5，RL3自身深度為K-7，

不難看出RLn的自深度構成了-2的等引數列，其通項公式為self_dep(RLn)=K-2*n-1，其中K為整顆樹上的最大深度，同時n也等于RLn節點的父節點深度減一，而當self_dep(RLn)<=1時，作為其兄弟節點的右子樹Rn深度為0已無法再繼續向下分裂，從而抵達了最小深度所在之處，

當K為奇數時，有最終項K-2*n-1=0可得n=(K-1)/2，其父節點深度dep=n+1，即min_dep=(n+1)/2，

當K為偶數時，有最終項K-2*n-1=1可得n=K/2-1，其父節點深度dep=n+1，即min_dep=n/2，

由上可知，在"左右子樹的最大深度之差不超過1"的平衡條件中，平衡樹中最大深度不會超出最小深度的兩倍，其傾斜邊界可確定，條件可行，那么是否存在錯誤示范呢？自然是有的，例如"左右子樹的最小深度之差不超過1"的平衡條件就無法確定傾斜邊界，下圖中樹結構符合上述平衡條件，但樹已經歪至天際，其RLn的自深度可以一直保持不下降，導致最大深度無線增長，傾斜邊界無法確定，

最小深度是否不能作為平衡條件呢？并不是，上述樣例的問題是因為其忽略了二叉樹性質，當前節點可選一顆子樹作為最小深度，用以解除另一顆子樹的深度限制，從而繞過平衡條件實作增長，知道了漏洞所在，只要進行填補即可，我們使用新的平衡限制條件為"左右節點的子樹最小深度之差不超過1"，此條件覆寫了向下一層的所有節點，不存在繞過平衡條件的情況，并且碰巧的是，紅黑樹采用的平衡限制條件就是它，

同樣我們對驗證模型做細微簡化，默認樹模型中右子樹的最小深度大于等于左子樹的最小深度，以探究最右側的樹深度（即最大深度）能達到多少，其中仍然采取"棄左保右"策略，通過讓左子樹繼承父節點的min_dep，解放右子樹深度限制，可以達到父節點min_dep+1的深度，但在該平衡條件中受到LL/LR/RLn/Rn四顆子樹中的最小值限制，Rn的min_dep是無法一直進行增長的，其具體模型如下所示：

圖中self_dep為當前節點除去父節點深度后剩下的深度，當其等于零時說明已經抵達最大深度節點處，讓我們把self_dep資料單獨抽取出來，每層均存在四個節點，分別代表了LL/LR/RL/RR，其值規律為：

即每加兩層深度，RR子樹自身深度下降一，LL/LR/RL/RR四顆子樹任意一顆self_dep降至0時擴展結束，其中LL為最小值，可知當self_dep(LL)=0時，RR子樹可達到的深度已經增長到2K或者2K-1（初始深度為K，K，K，K+1情況下），

綜上所述，可得結論：在"左右節點的子樹最小深度之差不超過1"的平衡條件中，平衡樹中最大深度不會超出最小深度的兩倍，是否感覺很眼熟？是的，平衡條件"左右子樹的最大深度之差不超過1"得到的傾斜邊界也為這個，因此若想區分不同平衡樹，使用平衡條件進行描述是個更好的方法，

5. 增刪節點邏輯

調整樹的工具和平衡樹的理想形狀都已設計完成，接下來要做的就是讓其向外提供服務了，外部的操作主要分為增刪改查四部分，其中改和查不影響樹結構（改是指value，并不是key），直接讓其走二叉排序樹的邏輯即可，重要的是其中增加節點與洗掉節點兩部分，

1. 增加節點

增加節點首先要確定節點位置，這一點可通過二叉排序樹的查邏輯實作，而后將其作為葉子節點連接到對應位置上，然后向上更新父節點的深度資料一路到根節點，例如平衡條件設定的是"左右子樹的最大深度之差不超過1"，則可在每個節點上存盤對應的最大深度值，同時父節點最大深度=max(左子樹最大深度,右子樹最大深度)+1，一旦發現超出了平衡條件，就要根據子樹的深度情況進行旋轉，之前樹平衡手段中所說的內容博主這邊再放一遍：

1）降低LL：直接右旋

2）降低LR：先左旋，和LL進行深度調整，最后右旋

3）降低RL：先右旋，和RR進行深度調整，最后左旋

4）降低RR：直接左旋

因為不存在一次性增加多個節點的情況，所以能確保每次最多一個節點突破平衡條件，當然，每次旋轉完后記得更新相關節點存盤的深度資料，并且向上更新至根節點，各位小伙伴可根據自己設定的平衡條件確認不同情況下的平衡流程，

2. 洗掉節點

洗掉節點的查找部分不再贅述，主要是其對樹結構的破壞需要注意，一共三種情況：

1）葉子節點洗掉，只需要將深度資訊向上更新，如果觸發平衡條件就進行旋轉，與增加節點的流程基本一致，

2）非葉子節點洗掉，這種情況下直接洗掉目標節點會引起樹結構大規模變動，設計較為麻煩，一種較好的方式是將洗掉節點與其后繼節點或者前繼節點進行交換，可以在不破壞二叉排序樹性質的情況下，將洗掉非葉子節點轉變為洗掉葉子節點，其中還可能會存在一種情況：找到的后繼節點存在右子節點，該情況下將后繼節點直接洗掉即可，用右子節點接替原位置并不會引起性質破壞，但向上的深度更新仍是要做的，不同場景下旋轉情況有所不同，此處暫不做列舉介紹，

至此為止，實作一顆平衡樹所需要的結構流程都已設計完畢，大家沒事的時候可以手寫試試，

6. 紅黑狀態

最后，讓我們將注意力調回紅黑樹上原來這是篇紅黑樹博客，紅黑樹其命名來源于樹中的紅黑節點狀態，之所以在原有平衡樹結構上增加了該設計，其目的是優化增刪程序中存盤的深度資料，改為以更少記憶體占用的紅黑二進制狀態存盤，且平衡判斷邏輯更加簡單順滑，其中二進制的進位還采用了惰性檢測的機制降低平衡頻率，為了讓討論的模型盡量簡單以下部分將不會加入該機制，改為在最后分段解釋，

1. 平衡限制帶來的優化

紅黑樹的平衡限制條件之前已經討論過，其內容為"左右節點的子樹最小深度之差不超過1"，相比起左右節點的子樹最小深度差值可能會超過1（此時觸發平衡），左右節點的最小深度差值永遠不會超過1（可自行證明），若能將左右節點的子樹深度比較轉換為左右節點比較，則各節點只需存盤一位二進制便可模擬所有場景【左右子樹均為1或0時代表深度相等，為1和0時代表深度差1】，

那么是否存在方法轉換比較的模式呢？讓我們來分析一下平衡條件的觸發場景，拋開左右的排列組合（即默認右子樹深度高一些），其只有一種情況，如下圖所示，其中的self_dep均代表以自身為根節點的最小深度值，

LL/LR其中的一個最小深度可以為K+1，并不會影響條件觸發，至于RL子樹，首先不能為K，否則在RL與RR之間已經觸發平衡條件，其次也不能為K+2，因為此時R最小深度已達到K+3，超出L節點最小深度2層，因此RL只能等于K+1，

普通的判斷步驟是LL/LR/RL/RR最小深度值相互比較，查看其中是否存在超出1的差值，但在樹結構上我們可以挖掘到更多資訊：RL與RR的最小深度均大于等于K+1，可得R的最小深度為K+2，同理L的最小深度為K+1，若以左右節點比較的方式來描述該場景則為：當觸發平衡限制時，可知左右子樹存在深度差，且深度更大的一側子樹中，其左右子樹也存在深度差（深度差只能為1），該因果關系反向也能成立，看官們若有興趣可自行證明，

將上述得到的結論以二進制形式應用，便衍生出了新的深度檢查機制：每個節點存盤一位二進制，其值代表與兄弟節點的相對深度，當左右子樹的相對深度為1和0，且為1的一側子樹中，其左右子樹深度也1和0時，觸發平衡限制，看起來比較繞口，讓我們將其畫成圖：

可以看到當兩個相連節點均為1時，若高位節點的兄弟節點為0，此時觸發平衡限制，從這里可以推匯出的另一個結論是平衡情況下，不會存在兩個相連節點同時為1，紅色在紅黑樹中代表1，黑色代表0，紅節點的父節點或子節點必為黑節點的結論可從此處得來，

2. 相對深度計算

既然利用相對深度進行判斷可行且占用空間較少，那么得想辦法實作相對深度的計算，

新增的節點默認值可設定為1（相對深度為1），而父節點相對深度推算可根據子節點情況進行：僅當左右節點相對深度均為1時，說明整體的最小深度增加了1，此時需要向上進位，將父節點值增加1（深度增加），左右節點重置為0，等待下一層深度的進位，簡單來看，就是基于二叉樹結構進行的二進制加法，

個別小伙伴可能會有擔心：如果父節點已經為1，子節點再上進位會怎么樣？答案是不會出現該情況：在父節點為1的情況下，若子節點任意一個為1時就會觸發平衡，沒有湊成兩個1節點的機會，當然，如果你將平衡條件放寬就會出現這種情況，但那時一個節點所需要保存的也不只是一個二進制位了，

到目前為止，二進制模式已經支持紅黑樹增量操作中的平衡判斷了：

1）新增節點默認為1，

2）增加節點后，檢查其兄弟節點是否為1，若為1則向上進位，然后在父節點重復該步，

3）若無法進位，檢查其父節點是否為1，若為1則需基于父節點和祖父節點進行平衡操作，

另外需要一提的是根節點固定為0，因為其沒有父節點也沒有兄弟節點，沒有存盤相對深度的必要，在整個二進制模式中充當的更像是處理資料溢位的角色，

3. 旋轉的紅黑狀態變化

洗掉操作對二進制狀態的改變類似于做二進制減法，而左右旋的改變既不是加法也不是減法（也可能博主是沒想到加減法的方式），而是節點轉移，讓我們暫且放下洗掉操作，先來看看旋轉的影響吧，

旋轉的場景較少，此處我們分析降低RR深度與RL深度兩種情況即可（左子樹的可以類推），

1）降低RR節點：左旋操作，

在旋轉程序中，確定相對深度的坐標系非常重要，我們需要基于該值重新推算旋轉后各節點的相對深度，例如以M節點為頂點的這顆子樹向外提供的相對深度基于實際深度K+2（上圖所示），那么在旋轉后，R節點替代了M節點且實際深度達到K+3，在原K+2的基礎上增加1，因此R節點當前的相對深度應為1，然后依次向下推導相對深度，剩余的M與RR，L與RL實際深度相同，因此均為0（均為1時相對深度就不平衡了），至于LL和LR子樹，其作為兄弟節點就沒有發生變化過，那么相對深度保持原狀即可，

2）降低RL節點：先右旋后左旋操作，

對于RL節點的深度降低，需要基于R與RL進行右旋操作將節點轉移給右子樹，受到平衡條件限制，RL的子樹RLL與RLR最小深度只可能是K+1，否則若存在K+2的深度，與RRL/RRR產生差距2，在RL與RR層就已發生平衡旋轉（更新都是從下向上發起的），

可以從上圖觀察到，旋轉操作執行完畢后，RL替代了原頂點R且實際深度未變，因此相對深度也仍保持原值1，而位于下一層的R與RLL節點存在1的深度差距，因此R節點設定為1，RLL節點相對深度設定為0，剩余的RLR/RR，RRL/RRR實際深度不變，相對深度也保持不變，

在一步右旋操作后，當前樹狀態已轉換為（1）中的情況，后續的左旋操作不再贅述，根據上述模擬得到的資訊，實際代碼實作時只需對發生變動的節點進行狀態位設定即可，

4. 洗掉的紅黑狀態變化

新增節點和旋轉操作的二進制運算模式均已設計完畢，讓我們來看看最后的洗掉操作，新增節點采用的是二進制加法進位，那么大家也容易想到洗掉節點使用的方法：二進制減法退位，而增加節點的時候默認賦值1，在洗掉節點時自然也要將1識訓，

在5.2節中，介紹了洗掉操作的幾種情況：1）洗掉葉子節點 2）洗掉非葉子節點，其中在洗掉非葉子節點時，通過后繼節點或前繼節點的替換，可以將其轉換為洗掉葉子節點的模式，所以我們主要觀察洗掉葉子節點的場景即可，

在圖中，L和RL分別代表一顆子樹，且RL可能為空，RR為洗掉的目標節點，且是葉子節點，那么洗掉有以下幾種情況：

1）RR節點為1，RL只能為0（兩者均為1時會進位），即空節點，洗掉節點后未觸發平衡條件，洗掉結束，

2）RR節點為0，當前位不足時，需要向高位借一，

在紅黑樹中借位有兩種方式：<1> 通過讓父節點減一，左右節點同時加一，<2> 通過左右旋從兄弟子樹獲取深度，

其中方式<2>一般用于特定情況下優化步驟，因為目標葉子節點洗掉后，其歸屬的子樹最小深度減1，變相讓兄弟節點的相對深度加1，若兄弟節點為1或兄弟節點的子節點為1，此時便觸發或超出了平衡限制條件，需要進行旋轉操作，且基于平衡限制進行的旋轉操作，最終必然會出現進位（可參考6.3節中的旋轉操作），這就抵消了洗掉節點時向原父節點的借位操作，

因此與其洗掉節點觸發父節點借位，再旋轉平衡后重新進位抵消，不如先旋轉獲取深度，然后執行洗掉操作，

最終可得洗掉（減法）執行步驟：

1）目標節點若為1，則將其降為0后減法結束，否則轉步驟2，

2）目標節點為0，若兄弟節點為1或兄弟節點的子節點為1，則基于兄弟節點與父節點進行旋轉，之后轉步驟3，

3）兄弟節點已無額外深度可提供，則需要向父節點借1，然后執行減法，若父節點為1流程結束，否則將父節點設定為目標節點重復步驟2，（即向更上層借位）

待減法流程完成后，最后將原目標節點洗掉即可，另外根節點的借位無限制，可無視其狀態位直接借位，

上圖為兄弟節點為1的情況，旋轉后向R借位，最后洗掉RR節點，

上圖為兄弟節點的子節點為1的情況，若圖中RLR為1，則需要先左旋后右旋，具體請參照降低LR或RL的方法，

5. 惰性檢查

基于紅黑狀態的增刪以及旋轉操作均已實作，最后讓我們來看看紅黑樹的惰性檢查機制吧，

相比起前面即刻觸發的進位操作，紅黑樹選擇了將其與平衡限制檢查的操作合并，即發現當前節點與父節點均為1時，才檢查父節點的兄弟節點，若兄弟節點值為1，則觸發進位操作，否則判斷已超出平衡限制，觸發旋轉操作，

從上圖中可以看見，左右節點同為1時并不會立刻觸發進位，僅當前目標與父節點同為1，此時不得不進行進位操作，否則會影響平衡判斷，其中基于M和R1的左旋也與之前稍有不同：并不是讓R1直接進位為1，而是將其拖延下來，存盤于M與R2上，等待M/R2的任意子節點為1時才進位，

該機制源于樹的深度范圍：在平衡限制條件"左右節點的子樹最小深度之差不超過1"下，其傾斜邊界為樹的最大深度不超出最小深度兩倍，但實際平衡時，左右子樹的傾斜情況各不相同，最大深度的差距從差2到差兩倍不等，

如果在保證傾斜邊界（也就是深度范圍）的情況下，盡量等到樹不能再傾斜后再進行平衡，此時一次平衡操作所轉移的節點數更多，效率更高（相比起小傾斜度平衡，高平衡頻率），但實際情況中，節點的增加方式完全是隨機的，上述抵達傾斜邊界的情況并不可控，

聰明的設計者決定在原有的平衡限制條件上做一個越界操作，也就是我們前面看到的惰性檢查機制，該機制導致左右節點的紅色進位必須要子節點為紅色"推著"才能走，紅節點每向上走一層，就要增加一層的節點用以進位，向上走N層，就必須要增加N層的子節點，最終實作每次平衡時均達到傾斜邊界的效果，

（惰性檢查機制下的節點進位，其實已經越過了原有"左右節點的子樹最小深度差不超過1"的平衡限制條件）

惰性檢查在保證查詢深度范圍的情況下，通過小幅度降低查詢效率的代價，換取更低的平衡頻率，提高增刪處理效率，且其在頻繁增刪節點的場景中，也起到了降低紅黑狀態進退位頻率的作用，

無論是在最初的平衡條件上，亦或是惰性檢查的機制上，紅黑樹的設計者都做了不少的讀寫效率取舍，方方面面的調整也是為了更貼合各種場景的泛型應用，至少對于你我來說，封裝好的紅黑樹已是日常開發中趁手的好工具了，

Cheers！

好，到此為止紅黑樹的原理決議全部完成（熱烈鼓掌）！各位看官們辛苦了，今天的小知識有get到嗎？

另外可以看幾個簡單問題來檢驗下學習成果呦，

1. 在無惰性檢查機制時，左右節點分別為紅和黑時代表了什么意義？

2. 什么時候樹中的紅節點占比最多？

3. 常態情況下為什么沒有相連的紅節點？

都看到這里了 不點個贊再走么