誰説前端不能搞紅黑樹，用這55張圖拿JS一起手撕紅黑樹

語言: CN / TW / HK
時間 2022-06-28 03:15:33

theme: fancy highlight: atom-one-light

持續創作，加速成長！這是我參與「掘金日新計劃 · 6 月更文挑戰」的第26天，點擊查看活動詳情

Hi~，我是一碗周，如果寫的文章有幸可以得到你的青睞，萬分有幸~

🍎 寫在前面

紅黑樹是數據結構與算法中比較難理解的一個樹狀結構了，在前端開發中，如果僅僅是業務開發的話，幾乎是用不到紅黑樹的；那為什麼還有學習紅黑樹呢？紅黑樹可以説是現在應用的最複雜的二叉樹之一，如果紅黑樹都能掌握還會怕其他的樹狀結構嘛？

通過本篇文章你將會掌握下面這些內容，我大概説明了內容以及難度：

wolai-minder-btw7rLJBou3pGWNawK6btZ-6eXwmpcasAoS4DbR7zhowm.png

上面的難度劃分僅僅是我按照文中的內容進行劃分，如果大佬非説紅黑樹的操作簡單，大佬，請收下我的膝蓋。

R-C_rBsak-WJMS.jpg

🥭 平衡樹和不平衡樹

二叉搜索樹又分為平衡樹和不平衡樹，如下圖所示：

01_平衡樹與非平衡樹_UsSlq5pGUQ.png

上圖的兩棵樹都是二叉搜索樹，左邊這顆平衡的二叉搜索樹查找一個節點的時間複雜度是，假如有10個億的數據只需要查找30次即可；右邊這顆不平衡的二叉搜索樹就相當於是一個排序後的鏈表，時間複雜度最壞為，假如還是10億數據，查找可能需要10億次。

假如我們依次往二叉搜索樹插入1, 2, 3, 4, 5, ... n，插入的數量為n，樹的高度也是n，因為我們最新插入的節點永遠都是葉子節點。

常見的平衡樹主要有AVL樹和紅黑樹：

  • AVL樹的出現早於紅黑樹的，它是一顆高度平衡樹，它的任意節點的左右子樹的高度差不會超過1，每為其增加一個節點，如果其左右子樹的高度差超過了1，都會進行旋轉，直到平衡為止；由於其需要頻繁進行旋轉，所以其性能要低於紅黑樹。
  • 紅黑樹通過變色、左旋、右旋來保持二叉搜索樹的平衡性（這裏的平衡性指的是黑色平衡，所謂的黑色平衡就是每個節點到葉子節點所經過的黑色節點是一致的），性能要優於AVL樹，所以現在平衡樹的應用都是紅黑樹。

🍏 AVL樹

AVL樹並不是這篇文章的重點，這裏僅僅介紹一個AVL樹的構建過程，從而説明為什麼紅黑樹的性能要優於AVL樹。

假如我們往二叉搜索樹中依次插入10, 9 ,8, 7, 6, 5, 4, 3, 2, 1，二叉搜索樹是下面這個樣子的：

01_二叉搜索樹（10-1依次插入）_MkZMz4iNxu.png

根據這個圖我們可以看出這棵二叉樹已經退化成了一個有序鏈表，現在我們用AVL樹來優化一下。

第一步：插入10和9，這個沒有什麼可説的直接插入就好；

02_AVL樹插入10和9_vVY720Pwz6.png

第二步，插入8，發現10的左子樹的高度為2，右子樹的高度為0，需要進行旋轉，如下圖：

03_AVL樹插入數據8__4_h9kgzXA.png

第三步：插入數據7，插入後任意一個節點都滿足左右子樹的高度差不大於1，所以不用進行旋轉。

04_AVL樹插入數據7_4gtvLrFfHM.png

第四步：插入數據6，插入後發現節點8和節點9的左右子樹高度差都是大於1的，需要進行旋轉，當出現多個節點不滿足左右子樹高度差都是大於1時，旋轉距離插入節點最近的祖先節點 ，如下圖所示：

05_AVL樹插入數據6_yL6Tx6Z0Yz.png

第五步：插入數據5後，對於根節點9來説，左子樹的高度為3，右子樹的高度為1，需要進行旋轉，過程如下：

06_AVL樹插入數據5_DxvCZhpXt8.png

第六步，插入數據4，對於節點6來説，左子樹的高度為2，右子樹的高度為0，需要進行旋轉，過程如下：

07_AVL樹插入數據4_U5R__ax7e6.png

第七步：插入數據3，插入後插入後任意一個節點都滿足左右子樹的高度差不大於1，所以不用進行旋轉。

08_AVL樹插入數據3_Fp2wKJbigO.png

第八步：插入數據2，對於節點4來説，左子樹的高度為2，右子樹的高度為0，需要進行旋轉，過程如下：

09_AVL樹插入數據2_X89mpCZc7t.png

最後一步，插入數據1，插入數據1後需要

10_AVL樹插入數據1_oEcywWQzdS.png

AVL樹為每個節點都維護一個平衡因子，平衡因子的值是左子樹的高度減去右子樹的高度或者右子樹的高度減去左子樹的高度；當節點的平衡因子的值為1、0、-1，則説明它是平衡的，當節點的平衡因子的絕對值大於2時，則説明這棵樹是不平衡的，需要進行旋轉。

11_AVL樹的插入過程_PB5fXqiNI-.gif

上圖出自為維基百科

🍑 AVL樹和紅黑樹優缺點對比

首先我們先來看一下如果上面那些數據依次插入紅黑樹是什麼樣子的，先不用管紅黑樹是怎麼構建的，這裏主要分析一下AVL樹和紅黑樹的優缺點。

11_紅黑樹_6tv1VMS-tf.png

從上圖中我們可以看到：

  • 紅黑樹並沒有追求完全平衡，它只是黑色節點平衡（即根節點到葉子節點的黑色節點數量一致，例如節點5到任何葉子節點的黑色節點數量都是2），而AVL樹是高度平衡樹，也就是追求完全平衡；這就意味這AVL樹隨着節點數量的越來越多，出現不平衡時，旋轉次數也就會也來越多，而紅黑樹出現任何不平衡，旋轉三次之內一定會解決（後面會驗證這個結論）
  • 刪除一個樹種的節點導致失衡，AVL樹需要從維護從根節點到刪除節點路徑上所有節點的平衡，時間時間複雜度時為O(logn)，而紅黑樹最多隻需旋轉三次即可恢復平衡，時間複雜度為O(1)；
  • 由於AVL樹是高度平衡樹，查找效率要高於紅黑樹，但是紅黑樹比AVL樹不平衡最多一層，也就是説差多最多就差一次。

基於以上幾點得出紅黑樹的綜合能力要優於AVL樹，表現會更加穩定。

🍒2-3-4樹

2-3-4樹是四階的B樹，它屬於一種多路查找，其具有以下限制：

B樹是一種自平衡的樹，其插入、查找和刪除的時間複雜度都是O(logn)

  • 所有葉子節點都必須具有相同的深度，也就説2-3-4樹是一顆滿樹；

  • 2-3-4樹把數據存儲在元素中，元素組成節點，節點只能是下列之一

    • 2-節點：包含一個元素和2個子節點；
    • 3-節點：包含兩個元素和3個子節點；
    • 4-節點：包含三個元素和4個子節點。

  • 元素使用保持排序順序，整體上保持二叉搜索樹的特質，即左子樹小於根節點，右子樹大於跟節點；

2-3-4樹的節點如下所示：

12_2-3-4樹的節點.drawio_DiOzlOG0Of.png

🍓2-3-4樹的構建過程

現在我們從頭來構建一顆2-3-4樹，往樹中依次插入71, 88, 80, 90, 89, 91, 66, 101, 150, 130, 166：

第一步：由於2-3-4樹必須是滿樹，且可以是2\~4節點，所以前三個元素直接構成一個4節點：

13_2-3-4樹的構建過程1_5_OX2GXCea.png

第二步：插入元素90，過程如下圖：

13_2-3-4樹的構建過程2_-AWOTfzbxj.png

第三步：插入元素89，合併節點後插入元素91，過程如下：

13_2-3-4樹的構建過程3_Ju3VDnOH_K.png

13_2-3-4樹的構建過程4_wt575mQONL.png

第四步：插入元素66，過程如下：

13_2-3-4樹的構建過程5_Yan-YjIe2t.png

第五步：插入元素101，過程如下：

13_2-3-4樹的構建過程6_p5x39Ih_2q.png

第六步：插入元素150，過程如下：

13_2-3-4樹的構建過程7_1wN-tqJkoz.png

13_2-3-4樹的構建過程8_peEpW9t5rc.png

第七步：插入元素166合併節點後，插入元素130，過程如下：

13_2-3-4樹的構建過程9_LM9eUf3FHO.png

13_2-3-4樹的構建過程10_gEhxK4O_ok.png

此時如果我們在插入一個元素，他會尋找自己的位置，並於原節點組成新的節點，例如插入元素35，最終的2-3-4樹如下所示：

13_2-3-4樹的構建過程11_-f3maalN-r.png

由構建過程可以得知，2-3-4的構建是從葉子節點依次到根節點進行構建。

🫐 2-3-4樹與紅黑樹的關係

2-3-4樹的任意一個節點，都至少對應紅黑樹的一種結構，也就是説2-3-4樹至少對應一棵紅黑樹，一棵紅黑樹對應一顆2-3-4樹，如下圖展示了2-3-4樹中的節點與紅黑樹結構的對應關係

14_2-3-4樹與紅黑樹的關係對應_BqoQSfSeO-.png

2-3-4樹還有一個狀態，就是一個4節點插入元素後，這裏將這個狀態稱為裂變狀態，如下圖所示：

15_裂變狀態_0JKPc1INEW.png

根據新插入元素的大小不同分為不同的4個位置。

🍈 2-3-4樹與紅黑樹的轉換

我們瞭解了2-3-4樹與紅黑樹的關係後，現在我們將之前畫的2-3-4樹轉換為紅黑樹，如下圖所示：

16_2-3-4樹轉紅黑樹_pfpcTCC3Rj.png

現在來將一顆紅黑樹轉換為2-3-4樹，如下圖所示：

17_紅黑樹轉2-3-4樹.drawio_JA0yAmOmv-.png

🍊 紅黑樹

前面我們用了很大的篇幅來介紹平衡的二叉搜索樹、AVL樹和2-3-4樹，其目的就是為了更好更快的學習和了解紅黑樹，現在我們正式開始進入紅黑樹的學習。

🍉 紅黑樹的五大特性

紅黑樹除了滿足二叉搜索樹的基本規則外，還滿足以下五個特性：

  • 節點是紅色或者黑色（廢話，要不然咋叫紅黑樹）；

  • 根節點是黑色（這是因為紅黑樹是由2-3-4樹轉換而來，根據2-3-4樹的2節點、3節點或者4節點轉換為紅黑樹的結對應關係，黑色節點總是作為父節點）

  • 每個葉子節點都是黑色的空節點（這裏的葉子節點指的NIL節點，如下圖）

    18_完整的紅黑樹_9US91p-XkG.png

  • 每個紅色節點的兩個子節點都是黑色，也就是説葉子節點到根節點所在的路徑上不會出現兩個連續的紅色節點。

    出現紅色節點的情況主要有兩種情況：

    • 2-3-4樹的3節點會出現一個紅色節點；
    • 2-3-4樹的4節點會出現兩個紅色節點；

    2-3-4樹的3節點肯定會出現3個節點，這三個節點不管是什麼節點都存在黑色節點，最小的那個黑色節點作為紅色節點父級的左子樹，剩餘的兩個節點作為紅色節點的左右子樹，如下圖所示：

    19_驗證紅黑樹規則4_3_KbQ1waDA4_.png

    2-3-4樹的4節點的情況與3節點類似，如下圖所示：

    19_驗證紅黑樹規則4_4_qeWc-Mi629.png

  • 從任意節點到其他葉子節點的所有路徑所包含相同數量的黑色節點；這是因為2-3-4是一顆滿樹，每個節點轉換為紅黑樹只有一個黑節點。

🍒 完整代碼

紅黑樹的源代碼在GitHub中，各位看官可以結合源代碼與文本一起食用，效果更佳。

🍋 紅黑樹的變色操作

本篇文章中關於紅黑樹的操作全部使用JavaScript完成，首先我們定義一個類，用於創建紅黑樹的節點，然後在定義一個類，用於實例化紅黑樹，代碼如下：

javascript const RED = 'RED' const BLACK = 'BLACK' class RBNode { /** * 創建一個新的節點 * @author ywanzhou * @param {number} val 要插入的數值 * @param {RBNode} parent 父節點 * @param {RBNode} left 左子樹 * @param {RBNode} right 右子樹 * @param {string} color 顏色 * @returns 一個新的節點 */ constructor(val, parent, left = null, right = null, color = RED) { if (color !== RED && color !== BLACK) throw new Error('color can only be RED or BLACK') this.val = val this.parent = parent this.left = left this.right = right this.color = color } } class RBTree { constructor() { this.root = null } }

節點的變色操作比較簡單，無非就是黑色變紅色，紅色變黑色，示例代碼如下：

```javascript /* * 給定一個節點，修改節點的顏色 這是一個私有方法 * @author ywanzhou * @param {RBNode} node 需要改變的顏色 * @param {string} color 需要節點改變後的顏色 /

setColor(node, color) {

if (color !== RED && color !== BLACK) throw new Error('color can only be RED or BLACK') if (!node) throw new Error('node is a empty RBNode') node.color = color } ```

🍌 紅黑樹的旋轉操作

旋轉操作分為左旋和右旋，我們依次來看：

  • 左旋轉：又稱逆時針旋轉，旋轉時以某個節點作為旋轉點，其右子節點變成自己的父節點，右子節點的左節點變成旋轉節點的右節點，過程如下圖所示： 21_左旋操作_IR7GOR7yoH.gif

  • 右旋轉：又稱順時針旋轉，旋轉時以某個節點作為旋轉點，其左子節點變成自己的父節點，左子節點的右節點變成旋轉節點的左節點，過程如下圖所示： 20_右旋操作_v1KMXyCpLi.gif

實現左旋右旋的代碼如下 （下列的代碼中每一行均有註釋，兩種旋轉方式一種是對代碼的理解，一種是實現步驟）：

```javascript /* * 圍繞 node 進行左旋 * 效果如下 * node -> pr(r) * / \ -> / \ * pl pr(r) -> node cr * / \ -> / \ * cl cr -> pl cl * @author ywanzhou * @param {Node} node 需要旋轉的節點 /

leftRotate(node) {

if (!node) return // 緩存一下 node 的右節點 const r = node.right // 將 pr 的右節點 pr 重新賦值為 cl node.right = r.left if (r.left !== null) { // 將 cl 的父節點指向 node r.left.parent = node } // 將節點r連接node節點的父節點 r.parent = node.parent if (node.parent === null) { // 如果需要旋轉的節點是根節點，則將根節點從node修改為r this.root = r } else if (node.parent.left === node) { // 説明要旋轉的node是父節點的左節點 node.parent.left = r } else if (node.parent.right === node) { // 説明要旋轉的node是父節點的右節點 node.parent.right = r } // 處理 r 節點的左節點 r.left = node // 處理 node 的父節點 node.parent = r } /* * 圍繞 node 進行右旋 * 效果如下 * node -> pl(l) * / \ -> / \ * pl(l) pr -> cl node * / \ -> / \ * cl cr -> cr pr * @author ywanzhou * @param {Node} node 需要旋轉的節點 /

rightRotate(node) {

if (!node) return // 1. 修改旋轉節點 左節點的右節點 為 旋轉節點的左節點 // 1.1 緩存一下 node 的左節點 const l = node.left // 1.2 修改左節點的右節點為旋轉節點的左節點 node.left = l.right

// 2. 連接旋轉節點的左節點與旋轉節點的引用 if (l.right !== null) { l.right.parent = node }

// 3. 修改 l 節點的父節點 l.parent = node.parent if (node.parent === null) { // 3.1 如果 node 此時是根節點，則將根節點重新指向 l this.root = l } else if (node.parent.left === node) { // 3.2 如果 node 是父節點的左節點，則更換左節點 node.parent.left = l } else if (node.parent.right === node) { // 3.3 如果 node 是父節點的右節點，則更換右節點 node.parent.left = r } // 4. 將旋轉節點作為旋轉節點左節點的右節點 l.right = node // 4.1 重新建立parent引用 node.parent = l } ```

🍍 紅黑樹的新增操作

紅黑樹的新增操作需要分為多種情況討論，這裏我們先拿2-3-4樹在推導出紅黑樹插入插入節點需要哪些操作。

為了保持紅黑樹的黑色平衡，插入節點時需要旋轉和變色操作，情況分為如下幾種：

情況一 ：插入節點時不存在任何節點，插入一個節點（新節點始終都是紅色，為什麼是紅色？就拿下圖二和圖三來説吧，如果直接插入黑色節點，需要做變色處理操作），直接由紅色節點轉換為黑色節點即可，如下圖所示：

20_紅黑樹的插入過程1_041vTHmM-H.png

情況二：插入節點時，存在父級存在一個黑色節點，在2-3-4樹中對應往2節點中插入元素，如下圖所示：

20_紅黑樹的插入過程2_GvGjXzNEwL.png

情況三 ：2-3-4樹種存在一個3節點，插入一個元素時，轉換為紅黑樹可以分為六種情況，如下圖所示：

20_紅黑樹的插入過程3_477wvD-rZ6.png

20_紅黑樹的插入過程4_uxUhiSJX4f.png

20_紅黑樹的插入過程5_U4aYJ_wsnM.png

20_紅黑樹的插入過程6_ogjhwCjpIG.png

20_紅黑樹的插入過程7_ifWR9XoC0Z.png

20_紅黑樹的插入過程8_wxjFWL0iyB.png

情況四：2-3-4樹中已經存在一個4節點，插入元素後的情況如下：

20_紅黑樹的插入過程9_d2xfCgZCrt.png

上面的9個圖已經列舉了紅黑樹中所有的插入情況，我們現在通過JavaScript來實現一下對應的代碼：

```javascript /* * 往紅黑樹中插入一個節點 * @author ywanzhou * @param {number} val 要插入的值 * @return {RBNode} RBTree的根節點 / insert(val) { // 只允許插入數值 if (typeof val !== 'number') throw new TypeError('insert value is not a number') let t = this.root // 情況一：紅黑樹中不存在任何節點，插入收據後直接作為根節點 if (t === null) { this.root = new RBNode(val, null, null, null, BLACK) return this.root }

// 1. 尋找插入位置 // parent 指針用於記錄當前要插入的節點位置 let parent = t.parent do { parent = t // 當前值與根節點的值進行比較，如果當前值大則 cmp 大於 0 let cmp = val - t.val // 判斷 cmp 的值 如果大於 0 則插入右子樹 if (cmp > 0) { t = t.right } // 如果小於0則插入左子樹 else if (cmp < 0) { t = t.left } // 如果等於0則説明已經存在，拋出異常 else { throw new Error('insert value already exists') } /* * 當循環結束，此時已經到達末尾節點，t 的值為null，parent表示最後的末尾節點 / } while (t !== null)

// 2. 將節點插入樹中 // 2.1 創建節點 const newNode = new RBNode(val, parent) // 2.2 根據節點的值來判斷是插入右子樹還是左子樹 if (newNode.val > parent.val) { parent.right = newNode } else { parent.left = newNode }

// 3. 調整節點位置和顏色，維持紅黑樹的特性 this.#fixAfterInsertNode(newNode) return this.root } /* * 給定一個節點，調整在紅黑樹的位置和顏色 * @author ywanzhou * @param {RBNode} node 要調整的節點 /

fixAfterInsertNode(node) {

// * 需要調整的情況由博文中的圖五到圖九 // 新增的節點為紅色 node.color = RED // * 博文中圖二、三、四都是不需要調整的情況，這三個圖都具有一個特點，就是父親節點的顏色為黑色 while (node !== null && node !== this.root && node.parent.color === RED) { // 1. 首先處理圖七和圖九的前兩種情況（先處理圖七和圖五無所謂，只是換個方向） // 1.1 判斷 node 的父節點是爺爺節點的左孩子 if ( this.#getParent(node) === this.#getLeft(this.#getParent(this.#getParent(node))) // 當前節點的父節點的父節點的左節點與當前節點的父節點是否相等 ) { // 如果滿足條件，已經對應圖七和圖九中的前兩種情況 // 1.2 獲取叔叔節點 let uncle = this.#getRight(this.#getParent(this.#getParent(node))) // 1.3 判斷叔叔節點的顏色是否為紅色，如果是則變色 if (this.#getColor(uncle) === RED) { // * 如果進入則説明存在叔叔節點，也就是進入圖九的前兩種情況，按照途中的步驟，通過代碼實現 const grandpa = this.#getParent(this.#getParent(node)) // 1.3.1 將父節點和叔叔節點修改為黑色，將爺爺節點修改為紅色 this.#setColor(this.#getParent(node), BLACK) this.#setColor(uncle, BLACK) this.#setColor(grandpa, RED) // 將爺爺節點賦值給node，這裏對應圖九的最後一句話 node = grandpa } // * 處理圖七和圖八的情況 // 1.4 説明沒有叔叔節點或者叔叔節點是黑色，則不需要操作叔叔節點，只需要操作父節點和爺爺節點 else { // 1.7 處理圖八的情況 // 1.7.1 判斷插入的節點是否為父節點右節點 if (node === this.#getRight(this.#getParent(node))) { // 1.7.2 將節點的父節點賦值給當前節點 node = this.#getParent(node) // 1.7.3 對 node 進行左旋 轉換為圖七的情況 this.#leftRotate(node) // 接下來就可以按照圖七進行操作 } // 1.5 父節點變黑色 爺爺節點變紅色 const grandpa = this.#getParent(this.#getParent(node)) this.#setColor(this.#getParent(node), BLACK) this.#setColor(grandpa, RED) // 1.6 對爺爺節點進行右旋操作 this.#rightRotate(grandpa) } } else { // 如果不滿足條件，已經對應圖五和圖九中的後兩種情況，與上面的代碼基本類似 // 1.2 獲取叔叔節點 let uncle = this.#getLeft(this.#getParent(this.#getParent(node))) // 1.3 判斷叔叔節點的顏色是否為紅色，如果是則變色 if (this.#getColor(uncle) === RED) { // * 如果進入則説明存在叔叔節點，也就是進入圖九的後兩種情況，按照途中的步驟，通過代碼實現 const grandpa = this.#getParent(this.#getParent(node)) // 1.3.1 將父節點和叔叔節點修改為黑色，將爺爺節點修改為紅色 this.#setColor(this.#getParent(node), BLACK) this.#setColor(uncle, BLACK) this.#setColor(grandpa, RED) // 將爺爺節點賦值給node，這裏對應圖九的最後一句話 node = grandpa } // * 處理圖五和圖六的情況 // 1.4 説明沒有叔叔節點或者叔叔節點是黑色，則不需要操作叔叔節點，只需要操作父節點和爺爺節點 else { // 1.7 處理圖六的情況 // 1.7.1 判斷插入的節點是否為父節點右節點 if (node === this.#getLeft(this.#getParent(node))) { // 1.7.2 將節點的父節點賦值給當前節點 node = this.#getParent(node) // 1.7.3 對 node 進行右旋 轉換為圖五的情況 this.#rightRotate(node) // 接下來就可以按照圖五進行操作 } // 1.5 父節點變黑色 爺爺節點變紅色 const grandpa = this.#getParent(this.#getParent(node)) this.#setColor(this.#getParent(node), BLACK) this.#setColor(grandpa, RED) // 1.6 對爺爺節點進行左旋操作 this.#leftRotate(grandpa) } } } // 將根節點變成黑色 this.#setColor(this.root, BLACK) } /* * 獲取指定節點的父節點 * @author ywanzhou * @param {RBNode} node * @returns {RBNode} /

getParent(node) {

return node !== null ? node.parent : null } /* * 獲取指定節點的左節點 * @author ywanzhou * @param {RBNode} node * @returns {RBNode} /

getLeft(node) {

return node !== null ? node.left : null } /* * 獲取指定節點的右節點 * @author ywanzhou * @param {RBNode} node * @returns {RBNode} /

getRight(node) {

return node !== null ? node.right : null } /* * 獲取指定節點的顏色 * @author ywanzhou * @param {RBNode} node * @returns {string} /

getColor(node) {

return node === null ? BLACK : node.color } ```

現在我們來實例化這個樹，看一下創建出的紅黑樹是否符合標準，示例代碼如下：

``javascript /** * 中序遍歷紅黑樹，打印結果，查看插入操作是否正確 * @param {RBNode} root * @param {number} deep * @returns */ function inorder(root, deep = 1) { if (!root) return let tab = '' for (let i = 1; i < deep; i++) { tab += '\t' } root.left && inorder(root.left, deep + 1) console.log( '%c' + tab + root.val, root.color[0] === 'R' ? 'color:red' : 'color:black' ) root.right && inorder(root.right, deep + 1) } const tree = new RBTree() let arr = [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] arr.forEach(v => { console.log(------插入數據${v}------`) tree.insert(v) inorder(tree.root) console.log('--------------------') })

```

最後一次打印在控制枱的輸出如下：

22_插入功能的驗證_ZhjRrTjHmU.png

插入的每一步可以在Red/Black Tree Visualization中進行驗證插入的過程是否正確。

🍎 紅黑樹的刪除操作

🍏 刪除節點之前的準備工作

在開始刪除紅黑樹的節點之前，我們先來前驅節點和後繼節點，簡單的説：

  • 比當前節點小的那一個就是前驅節點；
  • 比當前節點大的那一個就是後繼節點；

如下圖：

23_前驅節點和後繼節點_1CrOe--siY.png

實現代碼如下：

javascript /** * 查找node的前驅節點 * @author ywanzhou * @param {RBNode} node * @returns {RBNode} 前驅節點 */ predecessor(node) { if (!node) return null else if (node.left) { let p = node.left while (p.right) { p = p.right } return p } else { // 如果刪除尋找前驅節點是保證左右子樹都存在的時候才找前驅或者後繼 // 這裏的 else 只是為了尋找節點的前驅節點 let p = node.parent let c = node while (p.left === c && p) { c = p p = p.parent return p } return null } } /** * 查找node的後繼節點 * @author ywanzhou * @param {RBNode} node * @returns {RBNode} 後繼節點 */ sucessor(node) { if (!node) return null else if (node.right) { let p = node.right while (p.left) { p = p.left } return p } else { let p = node.parent let c = node while (p.right === c && p) { c = p p = p.parent return p } return null } }

現在我們編寫一個查找節點的方法，因為我們的刪除是根據值來刪除的，所以需要編寫一個根據val來查找節點的方法：

javascript /** * 根據val查找指定節點 * @author ywanzhou * @param {number} val 要查找的節點的值 * @returns {RBNode} 找到的節點 */ findNode(val) { if (typeof val !== 'number') throw new TypeError('val is not a number') let p = this.root while (p) { if (val < p.val) { p = p.left } else if (val > p.val) { p = p.right } else { break } } return p }

🍑 刪除節點

紅黑樹的刪除節點操作我們可以分為兩步執行，分為刪除節點和調整紅黑樹的平衡。

我們先來完成刪除節點，刪除節點可以分為三種情況，如下圖所示：

24_刪除節點的三種情況_yopRbcvUZJ.png

在上面的圖中，刪除並沒有考慮保持紅黑樹的平衡，現在我們來分別討論一下：

首先是刪除葉子節點的情況：

25_刪除情況的討論1_aZWebbm-7H.png

刪除葉子節點分為兩種情況，一種是不需要調整的，就是刪除紅色節點 ，直接刪除就好，還有一種就是黑色節點，需要調整後在進行刪除 。

然後就是刪除存在一個子樹的節點的情況，如下所示：

25_刪除情況的討論2_uYYK7Fm_M9.png

25_刪除情況的討論3_lp3Jqjj50X.png

上圖中也存在兩種情況，一種就是刪除紅色節點，直接黑色節點代替還是能維護平衡，另一種就是刪除黑色節點，需要刪除後調整紅黑樹的平衡；

情況三就是刪除具有左右子樹的情況，這個時候找到前驅或者後繼進行刪除後，就會變成上面兩種情況。

總之就是刪除黑色節點需要調整平衡，紅色節點可以直接刪除；實現代碼如下：

```javascript / * 根據 val 刪除紅黑樹中的節點 * @author ywanzhou * @param {number} val 要刪除的節點的值 * @returns {number} 刪除的節點中的val值 */ remove(val) { const node = this.findNode(val) if (!node) { return null } const oldVal = node.val // 刪除節點 this.deleteNode(node) return oldVal } / * * @param {RBNode} node 要刪除的節點 */ deleteNode(node) { // 刪除節點 // 1 存在左右子樹的情況 if (node.left && node.right) { // 1.1 找到前驅或者後繼節點 const sucessor = this.sucessor(node) // 1.2 將我們找到節點的值賦值給要被刪除的節點 node.val = sucessor.val // 1.3 將 node 指向後繼節點，刪除 node 即可（也就是刪除前驅或者後繼） node = sucessor } // 1.1 刪除的節點是根節點，直接將 root 置為 null if (node.parent === null) { this.root = null } // 2 找到替換節點 // 如果前面使用前驅節點則存在左子樹，後繼存在右子樹，這裏這麼寫可以兼容前驅或者後繼 let replacement = node.left ? node.left : node.right if (replacement) { // 2.1 説明存在左子樹或者右子樹，則不是葉子節點 // 2.1.1 將 replacement 的 parent 指向 node 的 parent（認爹） replacement.parent = node.parent // 2.1.2 建立 left 或者 right 的引用（認兒子） if (node.parent.left === node) { node.parent.left = replacement } else { node.parent.right = replacement } // 2.1.3 清空node節點的所有指針（拋棄了所有人，等待被垃圾機制回收） node.left = null node.right = null node.parent = null

// 2.1.4 調整紅黑樹的平衡
if (this.#getColor(node) === BLACK) {
  // 只有刪除黑色節點才需要調整平衡
  /**
   * 這裏的replacement節點一定是紅色，原因：
   * 紅黑樹中刪除的節點對應 2-3-4 樹中的葉子節點
   * 葉子節點只存在三種情況，也就是2節點3節點和4節點
   * 如果是2節點，則 replacement 不存在
   * 如果是3或者4節點，則 replacement 一定為紅色節點
   */
  this.#fixAfterDeleteNode(replacement) // 基於前驅或者後繼節點進行調整
}

} // 3 刪除葉子節點 else { // 3.1 説明不存在前驅或者後繼，也就是葉子節點 if (this.#getColor(node) === BLACK) { // 3.2 如果葉子節點是黑色，則需要調整紅黑樹的平衡 this.#fixAfterDeleteNode(node) } // 3.3 刪除葉子節點 // 3.3.1 不認兒子 if (node.parent.left === node) { node.parent.left = null } else if (node.parent.right === node) { node.parent.right = null } // 3.3.2 不認老爹 node.parent = null } } ```

由於紅黑樹是由2-3-4樹演變而來，刪除時肯定是刪除的2-3-4樹中的葉子節點，如果不是葉子節點也需要轉換為葉子節點刪除，2-3-4樹的葉子節點對應的就是紅黑樹的葉子節點以及葉子節點的上一層，所以説在紅黑樹中的刪除永遠只會刪除葉子節點或葉子節點的上一層 ，如下圖所示：

26_刪除的節點_Tffj2F2Hi0.png

現在我們就正式開始分析：

情況一，當要調整的節點為紅色時，直接染黑即可，如下圖所示：

26_刪除後節點調整分析01_SPsdSucIoP.png

情況二，刪除的節點沒有子節點，可以從兄弟節點借一個過來：

這裏的兄弟節點指的時轉換為2-3-4樹中的兄弟節點，如下圖所示：

26_刪除後節點調整分析02_sPcOJB8sVs.png

找到真正兄弟節點過程如下：

26_刪除後節點調整分析03_wnlM6RZav9.png

這裏我們以要調整的節點是左孩子舉例 (右孩子的話直接換個方向，邏輯與左孩子相同)；如果兄弟節點存在右孩子處理過程如下：

26_刪除後節點調整分析04_ymnZSnbTvU.png

如果兄弟節點不存在右孩子處理過程如下：

26_刪除後節點調整分析05_xNHB8KARnd.png

情況三，兄弟節點不存在左右子樹，此時需要從要調整的節點和兄弟節點依次減少一個黑色節點，直至黑色平衡為止，如下圖所示：

26_刪除後節點調整分析06_vAU4bn-qYe.png

實現代碼如下：

代碼中註釋非常清楚，且經常與2-3-4樹對比編寫。

```javascript /* * 刪除時調整樹結構 * @author ywanzhou * @param {RBNode} x /

fixAfterDeleteNode(x) {

// 1. 如果 x 節點不是根節點且顏色時黑色 while (x !== this.root && this.#getColor(x) === BLACK) { // x 是左孩子 if (x === this.#getLeft(this.#getParent(x))) { // 1.1 尋找兄弟節點 對應圖 刪除-02 let rNode = this.#getRight(this.#getParent(x)) // 1.1.1 如果兄弟節點為紅色，則説明它不是真正的兄弟節點 對應圖 刪除-03 if (this.#getColor(rNode) === RED) { // 1.1.2 將該節點染黑 父節點染紅 this.#setColor(rNode, BLACK) this.#setColor(this.#getParent(rNode), RED) // 1.1.3 將x節點的父節點左旋 this.#leftRotate(this.#getParent(x)) // 1.1.4 找到真正的兄弟節點 rNode = this.#getRight(this.#getParent(x)) } // 1.2 x 節點轉換為2-3-4樹，對應的兄弟節點為3節點或者4節點的情況 if (this.#getLeft(rNode) !== null || this.#getRight(rNode) !== null) { // 如果存在左子樹或者右子樹則説明轉換為2-3-4樹為3節點或者4節點 // 1.2.1 判斷是否存在左子樹，如果存在則變色旋轉 // 1.2.1.1 因為進入這個説明左右子樹必須存在一個，如果右子樹不存在則説明左子樹一定存在 if (this.#getRight(rNode) === null) { // 對應圖 刪除-05 // 1.2.1.2 説明存在，先將左子樹變黑 this.#setColor(this.#getLeft(rNode), BLACK) // 1.2.1.3 將原本的黑色節點變紅 this.#setColor(rNode, RED) // 1.2.1.4 右旋 this.#rightRotate(rNode) // 1.2.1.5 調整rNode rNode = this.#getRight(this.#getParent(x)) } // 對應圖 刪除-04 // 1.2.2 將兄弟節點變成父親的顏色 this.#setColor(rNode, this.#getColor(this.#getParent(x))) // 1.2.3 將父節點變成黑色 this.#setColor(this.#getParent(x), BLACK) // 1.2.4 將兄弟節點的右節點變成黑色 this.#setColor(this.#getRight(rNode), BLACK) // 1.2.5 沿着 x 節點的父節點進行左旋 this.#leftRotate(this.#getParent(x)) // 1.2.6 跳出循環 break } // 1.3 x 節點轉換為2-3-4樹，對應的兄弟節點為2節點 // 對應圖 刪除-06 else { // 1.3.1 將兄弟節點變成紅色 this.#setColor(rNode, RED) // 1.3.2 移動x遞歸變色 x = this.#getParent(x) // 1.3.3 如果 x 的節點不為黑色，則不會進入循環，而是執行 2 將其變成黑色，然後黑色繼續保存平衡 } } // x 是右孩子 else { // 代碼與上面一致，只是方向換了一下，為了兼容前驅和後繼節點 let lNode = this.#getLeft(this.#getParent(x)) if (this.#getColor(lNode) === RED) { this.#setColor(lNode, BLACK) this.#setColor(this.#getParent(lNode), RED) this.#rightRotate(this.#getParent(x)) lNode = this.#getLeft(this.#getParent(x)) } if (this.#getLeft(lNode) !== null || this.#getRight(lNode) !== null) { if (this.#getLeft(lNode) === null) { this.#setColor(this.#getRight(lNode), BLACK) this.#setColor(lNode, RED) this.#leftRotate(lNode) lNode = this.#getLeft(this.#getParent(x)) } this.#setColor(lNode, this.#getColor(this.#getParent(x))) this.#setColor(this.#getParent(x), BLACK) this.#setColor(this.#getLeft(lNode), BLACK) this.#rightRotate(this.#getParent(x)) break } else { this.#setColor(lNode, RED) x = this.#getParent(x) } } } // 2. 因為要替換的節點一定是需要轉換成黑色的，因為刪除紅色節點不會違反紅黑樹的平衡，所以不需要調整，凡是要調整的絕對是刪除黑色節點需要補充黑色節點 // 對應圖 刪除-01 this.#setColor(x, BLACK) } ```

{完}

🍓 寫在最後

本篇文章終於到這結束了，從頭到尾肝了一週多，全文一共56張圖片，除了一張是從維基百科上拿的剩下全部都是自己畫了，麻煩看官給點個贊支持一下吧\~

「」
「」