誰說前端不能搞紅黑樹,用這55張圖拿JS一起手撕紅黑樹
theme: fancy highlight: atom-one-light
持續創作,加速成長!這是我參與「掘金日新計劃 · 6 月更文挑戰」的第26天,點選檢視活動詳情
Hi~,我是一碗周,如果寫的文章有幸可以得到你的青睞,萬分有幸~
🍎 寫在前面
紅黑樹是資料結構與演算法中比較難理解的一個樹狀結構了,在前端開發中,如果僅僅是業務開發的話,幾乎是用不到紅黑樹的;那為什麼還有學習紅黑樹呢?紅黑樹可以說是現在應用的最複雜的二叉樹之一,如果紅黑樹都能掌握還會怕其他的樹狀結構嘛?
通過本篇文章你將會掌握下面這些內容,我大概說明了內容以及難度:
上面的難度劃分僅僅是我按照文中的內容進行劃分,如果大佬非說紅黑樹的操作簡單,大佬,請收下我的膝蓋。
🥭 平衡樹和不平衡樹
二叉搜尋樹又分為平衡樹和不平衡樹,如下圖所示:
上圖的兩棵樹都是二叉搜尋樹,左邊這顆平衡的二叉搜尋樹查詢一個節點的時間複雜度是,假如有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
,二叉搜尋樹是下面這個樣子的:
根據這個圖我們可以看出這棵二叉樹已經退化成了一個有序連結串列,現在我們用AVL樹來優化一下。
第一步:插入10和9,這個沒有什麼可說的直接插入就好;
第二步,插入8,發現10的左子樹的高度為2,右子樹的高度為0,需要進行旋轉,如下圖:
第三步:插入資料7,插入後任意一個節點都滿足左右子樹的高度差不大於1,所以不用進行旋轉。
第四步:插入資料6,插入後發現節點8和節點9的左右子樹高度差都是大於1的,需要進行旋轉,當出現多個節點不滿足左右子樹高度差都是大於1時,旋轉距離插入節點最近的祖先節點 ,如下圖所示:
第五步:插入資料5後,對於根節點9來說,左子樹的高度為3,右子樹的高度為1,需要進行旋轉,過程如下:
第六步,插入資料4,對於節點6來說,左子樹的高度為2,右子樹的高度為0,需要進行旋轉,過程如下:
第七步:插入資料3,插入後插入後任意一個節點都滿足左右子樹的高度差不大於1,所以不用進行旋轉。
第八步:插入資料2,對於節點4來說,左子樹的高度為2,右子樹的高度為0,需要進行旋轉,過程如下:
最後一步,插入資料1,插入資料1後需要
AVL樹為每個節點都維護一個平衡因子,平衡因子的值是左子樹的高度減去右子樹的高度或者右子樹的高度減去左子樹的高度;當節點的平衡因子的值為1、0、-1,則說明它是平衡的,當節點的平衡因子的絕對值大於2時,則說明這棵樹是不平衡的,需要進行旋轉。
上圖出自為維基百科
🍑 AVL樹和紅黑樹優缺點對比
首先我們先來看一下如果上面那些資料依次插入紅黑樹是什麼樣子的,先不用管紅黑樹是怎麼構建的,這裡主要分析一下AVL樹和紅黑樹的優缺點。
從上圖中我們可以看到:
- 紅黑樹並沒有追求完全平衡,它只是黑色節點平衡(即根節點到葉子節點的黑色節點數量一致,例如節點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樹的節點如下所示:
🍓2-3-4樹的構建過程
現在我們從頭來構建一顆2-3-4樹,往樹中依次插入71, 88, 80, 90, 89, 91, 66, 101, 150, 130, 166
:
第一步:由於2-3-4樹必須是滿樹,且可以是2\~4節點,所以前三個元素直接構成一個4節點:
第二步:插入元素90,過程如下圖:
第三步:插入元素89,合併節點後插入元素91,過程如下:
第四步:插入元素66,過程如下:
第五步:插入元素101,過程如下:
第六步:插入元素150,過程如下:
第七步:插入元素166合併節點後,插入元素130,過程如下:
此時如果我們在插入一個元素,他會尋找自己的位置,並於原節點組成新的節點,例如插入元素35
,最終的2-3-4樹如下所示:
由構建過程可以得知,2-3-4的構建是從葉子節點依次到根節點進行構建。
🫐 2-3-4樹與紅黑樹的關係
2-3-4樹的任意一個節點,都至少對應紅黑樹的一種結構,也就是說2-3-4樹至少對應一棵紅黑樹,一棵紅黑樹對應一顆2-3-4樹,如下圖展示了2-3-4樹中的節點與紅黑樹結構的對應關係
2-3-4樹還有一個狀態,就是一個4節點插入元素後,這裡將這個狀態稱為裂變狀態,如下圖所示:
根據新插入元素的大小不同分為不同的4個位置。
🍈 2-3-4樹與紅黑樹的轉換
我們瞭解了2-3-4樹與紅黑樹的關係後,現在我們將之前畫的2-3-4樹轉換為紅黑樹,如下圖所示:
現在來將一顆紅黑樹轉換為2-3-4樹,如下圖所示:
🍊 紅黑樹
前面我們用了很大的篇幅來介紹平衡的二叉搜尋樹、AVL樹和2-3-4樹,其目的就是為了更好更快的學習和了解紅黑樹,現在我們正式開始進入紅黑樹的學習。
🍉 紅黑樹的五大特性
紅黑樹除了滿足二叉搜尋樹的基本規則外,還滿足以下五個特性:
-
節點是紅色或者黑色(廢話,要不然咋叫紅黑樹);
-
根節點是黑色(這是因為紅黑樹是由2-3-4樹轉換而來,根據2-3-4樹的2節點、3節點或者4節點轉換為紅黑樹的結對應關係,黑色節點總是作為父節點)
-
每個葉子節點都是黑色的空節點(這裡的葉子節點指的NIL節點,如下圖)
-
每個紅色節點的兩個子節點都是黑色,也就是說葉子節點到根節點所在的路徑上不會出現兩個連續的紅色節點。
出現紅色節點的情況主要有兩種情況:
- 2-3-4樹的3節點會出現一個紅色節點;
- 2-3-4樹的4節點會出現兩個紅色節點;
2-3-4樹的3節點肯定會出現3個節點,這三個節點不管是什麼節點都存在黑色節點,最小的那個黑色節點作為紅色節點父級的左子樹,剩餘的兩個節點作為紅色節點的左右子樹,如下圖所示:
2-3-4樹的4節點的情況與3節點類似,如下圖所示:
-
從任意節點到其他葉子節點的所有路徑所包含相同數量的黑色節點;這是因為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 } ```
🍌 紅黑樹的旋轉操作
旋轉操作分為左旋和右旋,我們依次來看:
-
左旋轉:又稱逆時針旋轉,旋轉時以某個節點作為旋轉點,其右子節點變成自己的父節點,右子節點的左節點變成旋轉節點的右節點,過程如下圖所示:
-
右旋轉:又稱順時針旋轉,旋轉時以某個節點作為旋轉點,其左子節點變成自己的父節點,左子節點的右節點變成旋轉節點的左節點,過程如下圖所示:
實現左旋右旋的程式碼如下 (下列的程式碼中每一行均有註釋,兩種旋轉方式一種是對程式碼的理解,一種是實現步驟):
```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樹在推匯出紅黑樹插入插入節點需要哪些操作。
為了保持紅黑樹的黑色平衡,插入節點時需要旋轉和變色操作,情況分為如下幾種:
情況一 :插入節點時不存在任何節點,插入一個節點(新節點始終都是紅色,為什麼是紅色?就拿下圖二和圖三來說吧,如果直接插入黑色節點,需要做變色處理操作),直接由紅色節點轉換為黑色節點即可,如下圖所示:
情況二:插入節點時,存在父級存在一個黑色節點,在2-3-4樹中對應往2節點中插入元素,如下圖所示:
情況三 :2-3-4樹種存在一個3節點,插入一個元素時,轉換為紅黑樹可以分為六種情況,如下圖所示:
情況四:2-3-4樹中已經存在一個4節點,插入元素後的情況如下:
上面的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('--------------------')
})
```
最後一次列印在控制檯的輸出如下:
插入的每一步可以在Red/Black Tree Visualization中進行驗證插入的過程是否正確。
🍎 紅黑樹的刪除操作
🍏 刪除節點之前的準備工作
在開始刪除紅黑樹的節點之前,我們先來前驅節點和後繼節點,簡單的說:
- 比當前節點小的那一個就是前驅節點;
- 比當前節點大的那一個就是後繼節點;
如下圖:
實現程式碼如下:
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
}
🍑 刪除節點
紅黑樹的刪除節點操作我們可以分為兩步執行,分為刪除節點和調整紅黑樹的平衡。
我們先來完成刪除節點,刪除節點可以分為三種情況,如下圖所示:
在上面的圖中,刪除並沒有考慮保持紅黑樹的平衡,現在我們來分別討論一下:
首先是刪除葉子節點的情況:
刪除葉子節點分為兩種情況,一種是不需要調整的,就是刪除紅色節點 ,直接刪除就好,還有一種就是黑色節點,需要調整後在進行刪除 。
然後就是刪除存在一個子樹的節點的情況,如下所示:
上圖中也存在兩種情況,一種就是刪除紅色節點,直接黑色節點代替還是能維護平衡,另一種就是刪除黑色節點,需要刪除後調整紅黑樹的平衡;
情況三就是刪除具有左右子樹的情況,這個時候找到前驅或者後繼進行刪除後,就會變成上面兩種情況。
總之就是刪除黑色節點需要調整平衡,紅色節點可以直接刪除;實現程式碼如下:
```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樹的葉子節點對應的就是紅黑樹的葉子節點以及葉子節點的上一層,所以說在紅黑樹中的刪除永遠只會刪除葉子節點或葉子節點的上一層 ,如下圖所示:
現在我們就正式開始分析:
情況一,當要調整的節點為紅色時,直接染黑即可,如下圖所示:
情況二,刪除的節點沒有子節點,可以從兄弟節點借一個過來:
這裡的兄弟節點指的時轉換為2-3-4樹中的兄弟節點,如下圖所示:
找到真正兄弟節點過程如下:
這裡我們以要調整的節點是左孩子舉例 (右孩子的話直接換個方向,邏輯與左孩子相同);如果兄弟節點存在右孩子處理過程如下:
如果兄弟節點不存在右孩子處理過程如下:
情況三,兄弟節點不存在左右子樹,此時需要從要調整的節點和兄弟節點依次減少一個黑色節點,直至黑色平衡為止,如下圖所示:
實現程式碼如下:
程式碼中註釋非常清楚,且經常與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張圖片,除了一張是從維基百科上拿的剩下全部都是自己畫了,麻煩看官給點個贊支援一下吧\~
- 用ChatGPT學Nginx是一種什麼體驗
- 【好物分享】分享給前端開發的28個資源(網站、軟體、外掛),簡直是提高效率必備
- Vite3.0都來了,你還捲動嗎?(Vite3.0新特性一覽)
- 【好物分享】在命令列讀Markdown,這個感覺太舒服了
- 從0開始使用pnpm構建一個Monorepo方式管理的demo
- 我畫了5張腦圖可以讓你快速入門TypeScript
- 我看著MDN文件,手寫了幾個陣列例項方法
- 淺談JavaScript中的特殊函式
- 如何通過SSH配合VSCode收穫超舒適的遠端開發體驗
- CSS的calc函式不會還有人沒有用吧
- 【戲玩演算法】12-圖
- 誰說前端不能搞紅黑樹,用這55張圖拿JS一起手撕紅黑樹
- 簡單總結了10個JavaScript程式碼優化小tips
- NaiveUI中看起來沒啥用的元件(文字漸變)實現原來這麼簡單
- 面試官讓我用Flex寫色子佈局,我直接給寫了6個
- Vue3 TS Vite NaiveUI搭建一個專案骨架
- 用一萬多字從頭到尾介紹【函數語言程式設計】
- 這8張腦圖幾乎概括了所有的佈局方案,確定不看看嗎?
- 【戲玩演算法】07-字典
- 還在console.log一把梭嗎?console還有其他騷操作