從根源上探究紅黑樹的本質

2020-09-23 22:31:24

前言

本文主要講解下最近一直聽到的紅黑樹，看看究竟是什麼神仙鬼怪。

二叉樹

滿足以下兩個條件的樹就是二叉樹：

本身是有序樹（若將樹中每個結點的各子樹看成是從左到右有次序的(即不能互換)，則稱該樹為有序樹(Ordered Tree)）；
樹中包含的各個節點的度不能超過 2，即只能是 0、1 或者 2；

簡單地理解，二叉樹（Binary tree）是每個節點最多隻有兩個分支（即不存在分支度大於2的節點）的樹結構。通常分支被稱作“左子樹”或“右子樹”。

二叉查詢樹

要了解紅黑樹之前，免不了先看下二叉查詢樹是什麼。

維基百科上的定義

二叉查詢樹（英語：Binary Search Tree），也稱為二叉搜尋樹、有序二叉樹（ordered binary tree）或排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹

若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
若任意節點的右子樹不空，則右子樹上所有節點的值均大於或等於它的根節點的值；
任意節點的左、右子樹也分別為二叉查詢樹；

圖示理解

下圖為查詢值為29的節點，有以下步驟：

檢視根節點41
因為41> 29 ,所以檢視41的左孩子20
因為20 < 29 ,所以檢視20的右孩子29，發現其正好是要檢視的節點。

退化

二叉查詢樹有個非常嚴重的問題，如果資料的插入是從大到小插入的，或者是從小到大插入的話，會導致二叉查詢樹退化成單鏈表的形式，俗稱“瘸子“。

左瘸子：例如，插入資料依次為{5,4,3,2,1}（從大到小），則如下圖所示：
右瘸子：例如，插入資料依次為{1,2,3,4,5}（從小到大），則如下圖所示：

為了解決該問題，出現了一些解決方法，即平衡，能夠使得樹趨向平衡，這種自平衡的樹叫做平衡樹。

平衡樹

平衡樹(Balance Tree，BT) 指的是，任意節點的子樹的高度差都小於等於1。常見的符合平衡樹的有AVL樹（二叉平衡搜尋樹），B樹（多路平衡搜尋樹，2-3樹，2-3-4樹中的一種），紅黑樹等。

AVL樹

AVL樹（由發明者Adelson-Velsky 和 Landis 的首字母縮寫命名），是指任意節點的兩個子樹的高度差不超過1的平衡樹。又稱

自平衡二叉搜尋樹。

AVL樹能解決上文二叉查詢樹中的右瘸子問題，例如，插入資料依次為{1,2,3,4,5}（從小到大），則如下圖所示：

AVL樹會對不符合高度差的結構進行調整，從而使得二叉樹趨向平衡。

2-3樹

基本概念

2-3樹，是指每個具有子節點的節點（內部節點，internal node）要麼有兩個子節點和一個數據元素，要麼有三個子節點和兩個資料元素的自平衡的樹，它的所有葉子節點都具有相同的高度。

簡單點講，2-3樹的非葉子節點都具有兩個分叉或者三個分叉，所以，稱作2叉-3叉樹更容易理解。

另外一種說法，具有兩個子節點和一個數據元素的節點又稱作2節點，具有三個子節點和兩個資料元素的節點又稱作3節點，所以，整顆樹叫做2-3樹。

所有葉子點都在樹的同一層，一樣高。

性質1. 滿足二叉搜尋樹的性質
性質2. 節點可以存放一個或兩個元素
性質3. 每個節點有兩個或三個子節點

創建2-3樹的規則

插入操作

向2-節點中插入元素

向一顆只含有一個3-節點的樹中插入元素

2-3-4樹

含義

2節點：包含兩個子節點和一個數據元素
3節點：包含三個子節點和一個數據元素
4節點：包含四個子節點和一個數據元素

2-3-4樹，它的每個非葉子節點，要麼是2節點，要麼是3節點，要麼是4節點，且可以自平衡，所以稱作2-3-4樹。

規則

規則1. 加入新節點時，不會往空的位置新增節點，而是新增到最後一個葉子節點上
規則2. 四節點可以被分解三個2-節點組成的樹，並且分解後新樹的根節點需要向上和父節點融合

插入操作

原本的2-3-4樹
對於上圖的2-3-4樹，插入一個節點17，由於規則1，節點17不會加入節點[16,18,20]的子樹，而是與該節點融合。
由於規則2，節點[16,17,18,20]是一個4節點，將該節點進行拆解成新的樹，將18作為子樹的根節點進行拆分。
此時樹暫時失去了平衡，我們需要將拆分後的子樹的根節點向上進行融合。
同理可得，由於規則2，節點[6,10,14,18]是一個4節點，將該節點進行拆解成新的樹，將14作為子樹的根節點進行拆分，完成了2-3-4樹的構建。

總結了下插入節點的過程，無非也就為了符合兩條規則，那麼，2-3樹，2-3-4樹都有了，那是不是也有2-3-4-5樹，2-3-4-5--...-n樹的存在呢？事實上是有的，世人把這一類樹稱為一個名字：B樹。

B樹

B樹，表示的是一類樹，它允許一個節點可以有多於兩個子節點，同時，也是自平衡的，葉子節點的高度都是相同的。

所以，為了更好地區分一顆B樹到底屬於哪一類樹，我們給它一個新的屬性：度（Degree）：一個節點能有多少箭頭指向其他節點。

具有度為3的B樹，表示一個節點最多有三個子節點，也就是2-3樹的定義。

具有度為4的B樹，表示一個節點最多有四個子節點，也就是2-3-4樹的定義。

度為4的B樹的示例圖：

紅黑樹

簡介

R-B Tree，全稱是Red-Black Tree，又稱為“紅黑樹”，它一種特殊的二叉查詢樹。紅黑樹的每個節點上都有儲存位表示節點的顏色，可以是紅(Red)或黑(Black)。

如何理解紅黑樹

一個經典的紅黑樹如下圖所示（省略了葉子節點都是黑色的NIL節點）

如圖2所示，將該紅黑樹與上文講到的2-3-4樹對比，是否發現，紅黑樹就是一個2-3-4樹。

每個節點或者是黑色，或者是紅色。
根節點是黑色。
每個葉子節點（NIL）是黑色。[注意：這裡葉子節點，是指為空(NIL或NULL)的葉子節點！]
如果一個節點是紅色的，則它的子節點必須是黑色的。
由於紅黑樹的每個節點都是由2-3-4樹轉化而來的，從而紅色節點不能連續兩個出現，不然會出現4節點的情況，導致違反了規則2。而且紅黑樹的每一個黑節點都是3節點中的最中間的那個值，或者是2節點中其中一個值。
從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。
原因：紅黑樹這些黑色節點在2-3-4樹中代表的是由1節點的一個2-3-4樹，而2-3-4樹是同一個子樹的深度是相同的，平衡的，所以從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。（如下圖所示，藍色代表是黑色節點）

注意：

特性(3)中的葉子節點，是隻為空(NIL或null)的節點。
特性(5)，確保沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。
紅黑樹雖然本質上是一棵二叉查詢樹，但它在二叉查詢樹的基礎上增加了著色和相關的性質使得紅黑樹相對平衡，從而保證了紅黑樹的查詢、插入、刪除的時間複雜度最壞為O(log n)。