2023q1 quiz3 Tree 學習筆記

contributed by < WangHanChi >

本文整理自參考資料 紅黑樹簡介及左旋、右旋、變色 與 AVL高度平衡二元搜尋樹介紹
雷同的部份很多

二叉搜索樹

首先先從二叉搜尋樹開始，他有以下幾個特性

1. 如果二叉樹的左子樹不為空，則左子樹上所有節點的值均小於它的根節點的值
2. 如果二叉樹的右子樹不為空，則右子樹上所有節點的值均大於它的根節點的值
3. 如果獨立地看，左子樹、右子樹也分別為二叉搜索樹

以 Python 實作二叉搜索數這裡

向二叉搜索樹中插入數據時，為了滿足二叉搜索樹的特性，會遞歸地比較插入節點的值與根節點的值，將數據插入正確的位置，以下圖為例

他是一棵二叉搜索樹，節點為[50, 77, 55, 29, 10, 30, 66, 80, 51, 18, 90]

從結構圖可以看出，這棵二叉搜索樹是平衡的，當在二叉搜索樹中查找數據時，按照二分法查找的思想，從根節點開始，然後到子樹中進行查找，如果沒有查找到目標數據，每次都會往樹的下一層進行查找，需要的最大查找次數等於樹的深度。最壞的情況就是找到樹的最深一層，所以在這棵樹中查找的最壞情況是查找4次。

• 不平衡的二叉搜索樹
  

很明顯，這棵二叉搜索樹是不平衡的。在這棵樹中查找數據的最壞情況需要查找7次，查找次數多的原因就是樹的不平衡，右子樹一直在往深度上延伸。

根據結構圖，這是一棵右斜樹。它雖然是一棵二叉樹，但它更像是一個鏈結串列，正在向鏈結串列退化。鏈結串列的時間複雜度是O(N)，平衡二叉樹的時間複雜度是

$O(logN)$，當N很大的時候，

$O(N)$與

$O(logN)$的性能差距是很大的。

AVL Tree

AVL 樹是為了避免二元搜尋樹在極端情況下退化回 list ( 因為這樣搜尋的時間成本會便很高 )，所設計出來的一種樹，透過頻繁旋轉來維持這顆樹擁有最小花費。

當兩邊深度差達到 2 時就會進行旋轉（代表某邊過重）
平衡因子為左子樹深度減去右子樹深度，當平衡因子達到 2 或 -2 就會進行旋轉

總共會有四種情況，分別是

1. LL(左-左)
2. LR(左-右)
3. RR(右-右)
4. RL(右-左)

第一個字母代表哪邊子樹過重，第二個字母代表是在該子樹中哪邊添加節點導致不平衡

• 左子樹過重
  1. 在左子樹的左子增加節點 (LL)
     
  2. 在左子樹的右子增加節點 (LR)
     
• 右子樹過重
  1. 右子樹的右子增加節點 (RR)
     
  2. 右子樹的左子增加節點 (RL)
     

BF 計算

BF的計算方式是左子樹的高度 - 右子樹的高度
尋找的方式是從樹根開始找，若BF的值為正數，代表左子點的BF較大，就向左找。若為負數，則向右找。

旋轉條件

若有一加入的新節點為N，若一距離N最近且平衡因子為±2的父節點P存在，則四種調整方式的適用時機如下 ：

1. LL：當加入的節點N在節點P的左邊的左邊
2. RR：當加入的節點N在節點P的右邊的右邊
3. LR：當加入的節點N在節點P的左邊的右邊
4. RL：當加入的節點N在節點P的右邊的左邊

調整只需找鄰近的2節點即可。

紅黑樹

紅黑樹( Red Black Tree )是一種自平衡二叉搜索樹(二叉查找樹)，是一種特殊的二叉搜索樹，在進行插入和刪除時通過特定操作保持二叉樹自身的平衡，從而獲得較高的查找性能。

紅黑樹的平衡操作通過左旋、右旋和變色來實現，平衡的過程是比較複雜的，但通過平衡操作，可以獲得更高效的性能。對二叉搜索樹進行平衡後，最壞情況的運行時間得到優化，可以在

$O(logN)$ 的時間複雜度內完成查找、插入和刪除，N 是二叉搜索樹中的節點數。

紅黑數簡介

是一種自平衡二叉搜索樹，每個節點都有顏色，顏色為紅色或黑色，紅黑樹由此得名。除了滿足二叉搜索樹的特性以外，紅黑樹還具有如下特性:

1. 每個節點不是黑色就是紅色
2. 整個 tree的 root是一定黑色
3. 每個葉子的子節點視為黑色的空節點
4. 紅色節點其左右兩個子節點一定是黑色(意即不會有連續兩個紅色節點做為父子關係)，黑色節點無此限制
5. 從任一節點到其每個葉子節點的所有路徑都包含相同數目的黑色節點

要無時無刻滿足這 5 條規則才算是紅黑樹

紅黑樹的樹高定義也特別的不一樣，用的是 black height

black height 的定義是，對於 bh(x)，從 x 到任何一個它後代到末端 (即 leaf) 節點的路徑上，遇到的標註為「黑」的節點個數 (不含自身)。

從二叉搜尋樹變成紅黑樹

可以先把所有的節點都先視為黑色節點，如下圖所示

再來因為這棵二叉樹顯然不滿足紅黑樹的特性 5 ，例如節點 10 到樹葉的底距離為 1 個黑色節點(走一個左邊路徑)，但是節點 10 走到右邊子節點再到底的話，路徑會是 2 個黑色節點 (走一個右邊路徑)，因此，這時候就很適合把節點 18 變成紅色，就可以避免這個問題，如下圖所示。

或是也可以改這樣

當在紅黑樹中插入節點或刪除節點時，紅黑樹的平衡很可能會被破壞(不滿足其中一條或多條特性)，要立即對紅黑樹進行調整，使紅黑樹重新滿足5條特性。

調整平衡的操作包含左旋、右旋和變色，下面依次對這些操作進行介紹。

紅黑樹旋轉

對於一棵紅黑樹，它滿足紅黑樹的 5 條特性。插入或刪除節點之後，紅黑樹就發生了變化，很可能不再完全滿足紅黑樹的 5 條特性了，也就是不再是一棵紅黑樹了，而是一棵普通的二叉搜索樹。這時候，為了使二叉搜索樹重新變成紅黑樹，就需要對二叉搜索樹進行操作，使它滿足紅黑樹的 5 條特性。

通過旋轉，可以使二叉搜索樹重新滿足紅黑樹的5條特性。旋轉分為左旋和右旋。

紅黑樹的左旋

定義: 左旋：以某個節點作為支點(旋轉節點)，其右子節點變為旋轉節點的父節點，右子節點的左子節點變為旋轉節點的右子節點，旋轉節點的左子節點保持不變。右子節點的左子節點相當於從右子節點上“斷開”，重新連接到旋轉節點上。

左旋時，旋轉節點為節點50，左旋後，旋轉節點的右子節點70變為旋轉節點50的父節點，右子節點的左子節點60從右子節點70上“斷開”，成為旋轉節點50的右子節點。

左旋後，結構如右圖，這個局部重新滿足了紅黑樹的特性5，達到目的。
以下圖為例

再看另一個左旋的例子，左邊是左旋前的局部結構，以節點10作為旋轉節點，左旋後，旋轉節點的右子節點20成為旋轉節點10的父節點，右子節點的左子節點(這裡是一個葉子節點NIL)從右子節點上“斷開”，成為旋轉節點10的右子節點。

左旋的口訣
以下圖為例

把節點 10 定為作為旋轉節點，接著因為是左旋，所以把轉節點往左邊下移一個，然後把旋轉節點的右節點的左節點定為新的頭頭，他的子節點切下來送給節點 10，變成右圖。

紅黑樹的右旋

右旋：以某個節點作為支點(旋轉節點)，其左子節點變為旋轉節點的父節點，左子節點的右子節點變為旋轉節點的左子節點，旋轉節點的右子節點保持不變。左子節點的右子節點相當於從左子節點上“斷開”，重新連接到旋轉節點上。

不難看出，左旋和右旋是相反的，可逆的。

下圖中的例子仍然是紅黑樹的局部，左邊的結構不滿足紅黑樹的特性5。

右旋時，旋轉節點為節點70，右旋後，旋轉節點的左子節點50變為旋轉節點70的父節點，左子節點的右子節點60從左子節點50上“斷開”，成為旋轉節點70的左子節點。右旋後(右圖)，重新滿足了紅黑樹的特性5。

以下圖為例

同樣再看一個右旋的例子，左邊是右旋前的局部結構，以節點30作為旋轉節點，右旋後，旋轉節點的左子節點20成為旋轉節點30的父節點，左子節點的右子節點(這裡是一個葉子節點NIL)從左子節點上“斷開”，成為旋轉節點30的左子節點。

紅黑樹的變色操作

用途: 當對紅黑樹進行插入或刪除節點之後，如果不再完全滿足紅黑樹的5條特性，除了旋轉，變色也可以使二叉搜索樹重新滿足紅黑樹的5條特性。

變色：將節點的顏色由紅變黑或由黑變紅。

向紅黑樹中插入節點時，新節點的顏色都設置為紅色。不管新節點是什麼顏色，特性3都不可能被破壞，特性 1、2、4 都有可能被破壞。如果插入的節點是黑色，則一定會破壞特性 5，需要進行調整，如果插入的節點是紅色，則一定不會破壞特性 5。所以將新節點設置為紅色，可以降低破壞紅黑樹特性的可能性。

添加節點

如下的左圖是紅黑樹的一個局部，一開始是滿足紅黑樹的特性的，在其中插入了紅色節點 10，兩個紅節點連在一起了，不再滿足紅黑樹的特性 4。

通過變色，先將節點20變成黑色，特性4滿足了，但又不滿足特性5，所以繼續將節點30變成紅色，節點40變成黑色。

經過3次變色後，從局部看，已經重新滿足了紅黑樹的特性。但是，從整棵樹來看，還不一定滿足紅黑樹的特性，如果節點30的父節點也是紅色，則還需要繼續對這棵樹進行調整(上面的左旋和右旋例子中也有這種情況)。

刪除節點

如下的左圖是紅黑樹的一個局部，一開始是滿足紅黑樹的特性的，將節點90刪除後，不再滿足紅黑樹的特性5。

通過變色，先將節點80變成黑色，但仍不滿足特性5，繼續將節點70變成紅色，重新滿足了紅黑樹的特性。

經過兩次變色，重新滿足了紅黑樹的特性，對於這個例子，只要局部滿足了，整棵樹一定是滿足紅黑樹的。

綜合案例

詳情情見五、紅黑樹的旋轉和變色綜合案例

多執行緒版本的紅黑樹

因為最近在學習多執行緒程式的撰寫，因此想藉由紅黑樹來練習

完整的專案在這邊 mtrbt

而它可以表現出多個執行緒或是開一個執行緒等等的插入效能，如下

perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./test > record.txt

 Performance counter stats for './test' (5 runs):

     1,466,041,388      cache-misses              #   30.934 % of all cache refs      ( +-  0.71% )
     4,759,139,334      cache-references                                              ( +-  0.38% )
   251,563,836,349      instructions              #    0.52  insn per cycle           ( +-  0.43% )
   469,541,363,026      cycles                                                        ( +-  2.44% )

            27.598 +- 0.398 seconds time elapsed  ( +-  1.44% )

perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./compare >> record.txt

 Performance counter stats for './compare' (5 runs):

        70,327,676      cache-misses              #    2.730 % of all cache refs      ( +-  1.62% )
     2,564,128,406      cache-references                                              ( +-  0.54% )
   157,895,813,708      instructions              #    2.91  insn per cycle           ( +-  0.01% )
    54,219,636,042      cycles                                                        ( +-  0.16% )

           12.3947 +- 0.0183 seconds time elapsed  ( +-  0.15% )

perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./single >> record.txt

 Performance counter stats for './single' (5 runs):

        88,817,413      cache-misses              #    2.640 % of all cache refs      ( +-  2.11% )
     3,388,855,098      cache-references                                              ( +-  0.66% )
   207,286,639,117      instructions              #    2.98  insn per cycle           ( +-  0.01% )
    68,744,499,247      cycles                                                        ( +-  1.15% )

            15.992 +- 0.211 seconds time elapsed  ( +-  1.32% )

參考資料

• 紅黑樹簡介及左旋、右旋、變色