資料結構之2-3樹和紅黑樹剖析
文章目錄
- 資料結構之2-3樹和紅黑樹剖析
-
- 概述
- 2-3樹
- 2-3樹與紅黑樹的等價性
- 紅黑樹
-
- 紅黑樹添加新元素
- 實作
- 相關連結
- 公衆号
- 參考
概述
紅黑樹（英語：Red–black tree）是一種自平衡二叉查找樹，它在1972年由魯道夫·貝爾發明，被稱為"對稱二叉B樹"，它現代的名字源于Leo J. Guibas和Robert Sedgewick于1978年寫的一篇論文。
紅黑樹和AVL樹一樣都對插入時間、删除時間和查找時間提供了最好可能的最壞情況擔保。
《算法導論》中的紅黑樹：
- 1.每個節點或者是紅色的，或者是黑色的
- 2.根節點是黑色的
- 3.每一個葉子節點（最後的空節點）是黑色的
- 4.如果一個節點是紅色的，那麼他的孩子節點都是黑色的
- 5.從任意一個節點到葉子節點，經過的黑色節點是一樣的。
這些限制確定了紅黑樹的關鍵特性：
- 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。
- 結果是這個樹大緻上是平衡的。
- 因為操作比如插入、删除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。
- 性質4導緻了路徑不能有兩個毗連的紅色節點。最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點。因為根據性質5所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。
要學習紅黑樹，我們需要先學習2-3樹，任一棵2-3樹都可以按照特定規則轉換為一棵紅黑樹。
2-3樹
2-3樹：
- 滿足二分搜尋樹的基本性質
- 節點可以存放一個元素或者兩個元素
- 2-3樹是一棵絕對平衡的樹；絕對平衡的樹：對任意一個子樹，它的左、中、右子樹的高度是相等的。
2-3樹示例：
2-3樹如何維持絕對的平衡：
- 在2-3樹中添加新節點永遠不會添加到一個空的位置，隻會和最後找到的葉子節點做融合；
- 在2-3樹中隻會存在兩種節點：2節點和3節點；
- 如果是一個2節點添加一個新節點，直接融合變成一個3節點即可；
- 如果一個3節點添加一個新節點變成一個臨時的4節點，要對其進行拆解；
- 拆解：
- 對于2-3樹來說，如果一個葉子節點本身是一個3節點，添加一個新節點變成一個臨時的4節點，
- 拆解之後的根節點要和其父節點進行融合，融合之後的父節點也要為2節點或3節點否則也要進行拆解，
- 依此遞歸向上，直到父節點為2節點與其融合或為整棵樹的根節點結束；
插入情況一：插入3節點，父親節點為2節點
- 新添加的節點與3節點進行融合，進行拆分，拆分後根節點的父節點為2節點，與父節點融合即可；
插入情況二：插入3節點，父新節點為3節點
- 如果一個葉子節點本身是一個3節點，添加一個新節點變成一個臨時的4節點，
- 拆解之後的根節點要和其父節點進行融合，融合之後的父節點也要為2節點或3節點否則也要進行拆解，
- 依此遞歸向上，直到父節點為2節點與其融合或為整棵樹的根節點結束；
2-3樹插入示例：
2-3樹插入示例：
2-3樹與紅黑樹的等價性
2-3樹與紅黑樹的節點對應關系：
- 2-3樹中的 2節點 對應紅黑樹中的 黑節點 ；
- 為便于了解紅黑樹，采用左傾紅黑樹，定義：2-3樹中的3節點，都對應紅黑樹中的黑節點和左孩子節點為紅節點的兩個節點；
2-3樹與紅黑樹轉換示例：
- 依據上述節點轉換規則，任何一棵2-3樹都可以轉換為相應的紅黑樹；
2-3樹 轉換的紅黑樹 與《算法導論》中的紅黑樹 驗證 ：
- 1.每個節點或者是紅色的，或者是黑色的；
- 驗證：2-3樹的2節點 與 3節點轉換成紅黑樹的節點 要麼是黑色節點，要麼是一個黑節點和一個左傾的紅節點；
- 滿足；
- 2.根節點是黑色的
- 驗證：2-3樹的2節點 與 3節點轉換成紅黑樹的節點，新的節點的根節點都為黑節點；
- 滿足；
- 3.每一個葉子節點（最後的空節點）是黑色的
- 相當于定義空節點為黑節點，相當于一個空樹也是一個紅黑樹；與第2條性質相關聯；
- 滿足；
- 4.如果一個節點是紅色的，那麼他的孩子節點都是黑色的
- 在2-3樹轉換的紅黑樹中，隻有一種情況會出現紅節點，即 3節點 轉換成 一個黑節點和一個左傾的紅節點；
- 在2-3樹3節點隻會連接配接2節點或3節點，轉換後的紅節點的孩子節點隻會是黑節點；
- 滿足；
- 5.從任意一個節點到葉子節點，經過的黑色節點是一樣的。
- 在2-3樹中對應的是：從任意一個節點出發到葉子節點，所經過的節點數是一樣的；
- 2-3樹是一棵絕對平衡的樹，所有的葉子節點都是在同一層的，它的深度是相同的，這樣從任意一個節點出發，向下到葉子節點，其深度都是相同的，即所經過的節點數量是一樣的；
- 2-3樹中隻有2節點和3節點，轉換成紅黑樹後，每一個2節點或3節點都隻會對應一個黑節點；是以，在紅黑樹中，每經過一個黑節點，即相應的在2-3樹中經過了一個節點，即得出在紅黑樹中從任意一個節點到葉子節點，經過的黑色節點是一樣的；
- 紅黑樹是一棵保持黑平衡的二叉搜尋樹；其并不是平衡二叉樹；
- 紅黑樹最大的高度為： 2logn ， 時間複雜度為： O(logn)
- 滿足；
紅黑樹
紅黑樹中添加新元素與2-3樹中添加元素對應關系：
- 2-3樹中添加一個新元素：
- 或者添加進一個2節點，形成一個3節點；
- 或者添加進一個3節點，暫時形成一個4節點，再對4節點進行拆分；
- 在紅黑樹中添加新節點，永遠添加紅色節點
- 在2-3樹中添加新節點，永遠不會添加到空的位置，隻會和最後找到的葉子節點進行融合；
- 在2-3樹轉換成左傾紅黑樹中，其中紅節點對應2-3樹中的3節點轉換成一個黑節點和紅色的左孩子節點；
- 是以，我們在紅黑樹中添加新的元素時，我們讓新的元素節點永遠是紅色節點；等價于在2-3樹中添加新一進制素節點永遠是先融合進一個已有的節點中；
- 在紅黑樹中添加一個新元素紅節點後，可能會破壞紅黑樹的性質，需要再進行相應的處理，維持紅黑樹的性質；
紅黑樹添加新元素
紅黑樹添加新元素分析：
- 在紅黑樹中新添加元素都是紅節點；
- 因為2-3樹都可轉換成為一棵紅黑樹，采用與2-3樹中添加元素類比的方式，完成向紅黑樹中添加元素分析；
紅黑樹添加新元素類比向2-3樹中添加元素情況分析：
- 添加元素情況一：向空樹中添加元素
- 添加元素情況1：向空樹中添加元素，在紅黑樹中保持根節點為黑節點；
- 添加元素情況二：類似向2-3樹中的2節點添加元素，變成3節點
- 添加元素情況2：類似2-3樹中向2節點添加比其小的元素，無需任何處理
- 添加元素情況3：類似2-3樹中向2節點添加比其大的元素，需要進行：左旋轉
- 添加元素情況三：類似向2-3樹中的3節點添加元素，變成臨時4節點，再進行拆分
- 添加元素情況4：類似向2-3樹中的3節點添加比該節點值都大的元素，在紅黑樹中需要進行 顔色翻轉
- 添加元素情況5：類似向2-3樹中的3節點添加比該節點值都小的元素**，在紅黑樹中需要進行： 右旋轉 和 顔色翻轉：
- 添加元素情況6：類似向2-3樹中的3節點添加元素值大小處于中間位置的元素**，在紅黑樹中需要進行：左旋轉、右旋轉 和 顔色翻轉
添加元素情況1：向空樹中添加元素：
- 保持根節點為黑節點；
添加元素情況2：類似2-3樹中向2節點添加比其小的元素，無需任何處理：
添加元素情況3：類似2-3樹中向2節點添加比其大的元素，需要進行：左旋轉
左旋轉處理：
添加元素情況4：類似向2-3樹中的3節點添加比該節點值都大的元素，在紅黑樹中需要進行 顔色翻轉：
- 向2-3樹中的3節點添加比該節點值都大的元素，2-3樹變成臨時4節點，需要進行拆分，拆分後新的根節點需要其上一級父節點進行融合；
- 在紅黑樹中使用紅節點代表，保持左傾紅黑樹特性，對節點進行顔色翻轉。
添加元素情況5：類似向2-3樹中的3節點添加比該節點值都小的元素，在紅黑樹中需要進行： 右旋轉 和 顔色翻轉：
- 向2-3樹中的3節點添加比該節點值都大的元素，2-3樹變成臨時4節點，需要進行拆分，拆分後新的根節點需要其上一級父節點進行融合；
- 對應紅黑樹中添加元素後，需要進行右旋轉再進行顔色翻轉處理；
- 右旋轉：
- 與平衡二叉樹中進行右旋轉一緻，右旋轉後需要維護紅黑樹的節點的顔色；
- 原先的根節點的顔色要指派給新的根節點；
- 右旋轉後在2-3樹中仍代表臨時4節點，需要将新的左右孩子顔色變為紅色，代表其是與其父節點融合在一起的；
- 顔色翻轉
- 經過右旋轉之後，新的子樹形狀便與上一種情況一緻了，按上述顔色翻轉處理即可完成元素插入；
添加元素情況6：類似向2-3樹中的3節點添加元素值大小處于中間位置的元素，在紅黑樹中需要進行：左旋轉、右旋轉 和 顔色翻轉：
紅黑樹中添加元素處理操作彙總：
- 通過下述添加元素的鍊條示意圖，将類似向2-3樹中的3節點添加元素的所有情況全部覆寫；
- 該邏輯鍊條同樣适用于類似向2-3樹中的2節點添加元素的所有情況；
- 基于下述處理鍊條，可以完成向紅黑樹中添加元素後，維護紅黑樹特性所需要處理的所有情況。
添加元素後紅黑樹性質維護處理步驟：
- 檢驗目前節點是否需要左旋轉，條件：目前節點右孩子為紅節點且其左孩子不能為紅節點；
- 檢驗目前節點是否需要右旋轉，條件：目前節點左孩子為紅節點且目前節點左孩子的左孩子為紅節點；
- 檢驗目前節點是否需要顔色翻轉，條件：目前節點左孩子為紅節點且目前節點右孩子為紅節點；
- 依上述規則處理，遞歸向上，直到根節點傳回，遞歸結束；
- 遞歸結束後，保持紅黑樹的根節點為黑節點；
- 注意：如果是一個空節點，其為黑節點；
更多和紅黑樹相關的話題：
- 紅黑樹中删除一個節點，相應的邏輯過程比添加元素還要複雜；
- 紅黑樹的統計性能更優，即增、删、改、查操作綜合起來評估比AVL性能更優；
- 本次講述的紅黑樹，采用左傾紅黑樹，在紅黑樹中，對應2-3樹中的3節點為一個黑節點和一個其左孩子紅節點；但這并不是紅黑樹惟一的實作方式，同理也可以采用右傾紅黑樹實作；
- 另一種統計性能優秀的樹結構-Splay Tree(伸展樹)，局部性原理：剛被通路的内容下次高機率被再次通路；
實作
基于二叉搜尋樹實作紅黑樹中添加元素
參考代碼： com.chen.data.struct.redblack.RBTree
相關連結
gitee位址：https://gitee.com/chentian114/chen_datastruct_study
github位址：https://github.com/chentian114/chen_datastruct_study
CSDN位址：https://blog.csdn.net/chentian114/category_9997109.html
公衆号
參考
劉宇波《玩轉資料結構》課程
https://www.wiki-wiki.top/wiki/紅黑樹