數據結構和演算法(Golang實現)(30)查找演算法-2-3-4樹和普通紅黑樹
- 2020 年 4 月 14 日
- 筆記
- 數據結構和演算法(Golang實現)
2-3-4樹和普通紅黑樹
某些教程不區分普通紅黑樹和左傾紅黑樹的區別,直接將左傾紅黑樹拿來教學,並且稱其為紅黑樹,因為左傾紅黑樹與普通的紅黑樹相比,實現起來較為簡單,容易教學。在這裡,我們區分開左傾紅黑樹和普通紅黑樹。
紅黑樹是一種近似平衡的二叉查找樹,從2-3
樹或2-3-4
樹衍生而來。通過對二叉樹節點進行染色,染色為紅或黑節點,來模仿2-3
樹或2-3-4
樹的3節點和4節點,從而讓樹的高度減小。2-3-4
樹對照實現的紅黑樹是普通的紅黑樹,而2-3
樹對照實現的紅黑樹是一種變種,稱為左傾紅黑樹,其更容易實現。
使用平衡樹數據結構,可以提高查找元素的速度,我們在本章介紹2-3-4
樹,再用二叉樹形式來實現2-3-4
樹,也就是普通的紅黑樹。
一、2-3-4 樹
1.1. 2-3-4 樹介紹
2-3-4
樹是一棵嚴格自平衡的多路查找樹,又稱4階的B樹
(註:B
為Balance
平衡的意思)
它不是一棵二叉樹,是一棵四叉樹。具有以下特徵:
- 內部節點要麼有1個數據元素和2個孩子,要麼有2個數據元素和3個孩子,要麼有3個數據元素和4個孩子,葉子節點沒有孩子,但有1,2或3個數據元素。
- 所有葉子節點到根節點的長度一致。這個特徵保證了完全平衡,非常完美的平衡。
- 每個節點的數據元素保持從小到大排序,兩個數據元素之間的子樹的所有值大小介於兩個數據元素之間。
因為2-3-4
樹的第二個特徵,它是一棵完美平衡的樹,非常完美,除了葉子節點,其他的節點都沒有空兒子,所以樹的高度非常的小。
如圖:
如果一個內部節點擁有一個數據元素、兩個子節點,則此節點為2節點。如果一個內部節點擁有兩個數據元素、三個子節點,則此節點為3節點。如果一個內部節點擁有三個數據元素、四個子節點,則此節點為4節點。
可以說,所有平衡樹的核心都在於插入和刪除邏輯,我們主要分析這兩個操作。
1.2. 2-3-4 樹插入元素
在插入元素時,需要先找到插入的位置,使用二分查找從上自下查找樹節點。
找到插入位置時,將元素插入該位置,然後進行調整,使得滿足2-3-4
樹的特徵。主要有三種情況:
- 插入元素到一個2節點或3節點,直接插入即可,這樣節點變成3節點或4節點。
- 插入元素到一個4節點,該4節點的父親不是一個4節點,將4節點的中間元素提到父節點,原4節點變成兩個2節點,再將元素插入到其中一個2節點。
- 插入元素到一個4節點,該4節點的父親是一個4節點,也是將4節點的中間元素提到父節點,原4節點變成兩個2節點,再將元素插入到其中一個2節點。當中間元素提到父節點時,父節點也是4節點,可以遞歸向上操作。
核心在於往4節點插入元素時,需要將4節點中間元素提升,4節點變為兩個2節點後,再插入元素,如圖:
下面演示插入元素到一個4節點:
與其他二叉查找樹由上而下生長不同,2-3-4
樹是從下至上的生長。
2-3-4
樹因為節點元素數量的增加,情況變得更複雜,下面是插入元素到一個4節點,而4節點的父節點是3節點的三種情況:
其他情況可以參考2-3樹和左傾紅黑樹
一章,非常相似,在此不再贅述。
1.3. 2-3-4 樹刪除元素
刪除操作就複雜得多了,請耐心閱讀理解,和2-3
樹刪除元素類似。
2-3-4
樹的特徵註定它是一棵非常完美平衡的四叉樹,其所有子樹也都是完美平衡,所以2-3-4
樹的某節點的兒子,要麼都是空兒子,要麼都不是空兒子。比如2-3-4
樹的某個節點A
有兩個兒子B
和C
,兒子B
和C
要麼都沒有孩子,要麼孩子都是滿的,不然2-3-4
樹所有葉子節點到根節點的長度一致這個特徵就被破壞了。
基於上面的現實,我們來分析刪除的不同情況,刪除中間節點和葉子節點。
情況1:刪除中間節點
刪除的是非葉子節點,該節點一定是有兩棵,三棵或者四棵子樹的,那麼從子樹中找到其最小後繼節點,該節點是葉子節點,用該節點替換被刪除的非葉子節點,然後再刪除這個葉子節點,進入情況2。
如何找到最小後繼節點,當有兩棵子樹時,那麼從右子樹一直往左下方找,如果有三棵子樹,被刪除節點在左邊,那麼從中子樹一直往左下方找,否則從右子樹一直往左下方找。如果有四棵子樹,那麼往被刪除節點右邊的子樹,一直往左下方找。
情況2:刪除葉子節點
刪除的是葉子節點,這時葉子節點如果是4節點,直接變為3節點,如果是3節點,那麼直接變為2節點即可,不影響平衡。但是,如果葉子節點是2節點,那麼刪除後,其父節點將會缺失一個兒子,破壞了滿孩子的2-3-4
樹特徵,需要進行調整後才能刪除。
針對情況2,刪除一個2節點的葉子節點,會導致父節點缺失一個兒子,破壞了2-3-4
樹的特徵,我們可以進行調整變換,主要有兩種調整:
- 重新分布:嘗試從兄弟節點那裡借值,然後重新調整節點。
- 合併:如果兄弟借不到值,合併節點(與父親的元素)。
如果被刪除的葉子節點有兄弟是3節點或4節點,可以向最近的兄弟借值,然後重新分布,這樣葉子節點就不再是2節點了,刪除元素後也不會破壞平衡。如圖:
與兄弟借值,兄弟必須有多餘的元素可以借,借的過程中需要和父節點元素重新分布位置,確保符合元素大小排序的正確。
如果被刪除的葉子節點,兄弟都是2節點,而父親是3節點或4節點,那麼將父親的一個元素拉下來進行合併(當父節點是3節點時,父親元素與被刪除節點合併成3節點,當父節點是4節點時,被刪除節點和其最近的兄弟,以及父親的一個元素合併成一個4節點),父親變為2節點或3節點,這時葉子節點就不再是2節點了,刪除元素後也不會破壞平衡。如圖:
有一種最特殊的情況,也就是被刪除的葉子節點,兄弟都是2節點,父親也是2節點,這種情況沒法向兄弟借,也沒法和父親合併,與父親合併後父親就變空了。幸運的是,這種特殊情況只會發生在根節點是其父節點的情況,如圖:
因為2-3-4
樹的性質,除了根節點,其他節點不可能出現其本身和兒子都是2節點。
2-3-4
樹的實現將會放在B樹
章節,我們將會實現其二叉樹形式的普通紅黑樹結構。
二、 普通紅黑樹
2.1. 普通紅黑樹介紹
普通紅黑樹可以由2-3-4
樹的二叉樹形式來實現。
其定義為:
- 根節點的鏈接是黑色的。
- 每個紅色節點都必須有兩個黑色子節點。
- 任意一個節點到達葉子節點的所有路徑,經過的黑鏈接數量相同,也就是該樹是完美黑色平衡的。比如,某一個節點,它可以到達5個葉子節點,那麼這5條路徑上的黑鏈接數量一樣。
普通紅黑樹與其變種:左傾紅黑樹的區別是,它允許右傾的紅色節點,不再限制左傾,但仍然不能有連續的兩個左傾紅色鏈接。
每一棵2-3-4
樹可以對應多棵普通紅黑樹,如圖:
區別:2-3
樹與左傾紅黑樹則是一一對應,而2-3-4
樹可以對應多棵普通紅黑樹,是因為它允許了紅鏈接右傾。
2.2. 結構定義和節點旋轉
首先,我們要定義樹的結構RBTree
,以及表示普通紅黑樹的節點RBTNode
:
// 定義顏色
const (
RED = true
BLACK = false
)
// 普通紅黑樹
type RBTree struct {
Root *RBTNode // 樹根節點
}
// 新建一棵空樹
func NewRBTree() *RBTree {
return &RBTree{}
}
// 普通紅黑樹節點
type RBTNode struct {
Value int64 // 值
Times int64 // 值出現的次數
Left *RBTNode // 左子樹
Right *RBTNode // 右子樹
Parent *RBTNode // 父節點
Color bool // 父親指向該節點的鏈接顏色
}
// 節點的顏色
func IsRed(node *RBTNode) bool {
if node == nil {
return false
}
return node.Color == RED
}
// 返回節點的父親節點
func ParentOf(node *RBTNode) *RBTNode {
if node == nil {
return nil
}
return node.Parent
}
// 返回節點的左子節點
func LeftOf(node *RBTNode) *RBTNode {
if node == nil {
return nil
}
return node.Left
}
// 返回節點的右子節點
func RightOf(node *RBTNode) *RBTNode {
if node == nil {
return nil
}
return node.Right
}
// 設置節點顏色
func SetColor(node *RBTNode, color bool) {
if node != nil {
node.Color = color
}
}
在節點RBTNode
中,我們存儲的元素欄位為Value
,由於可能有重複的元素插入,所以多了一個Times
欄位,表示該元素出現幾次。
當然,紅黑樹中的紅黑顏色使用Color
定義,表示父親指向該節點的鏈接顏色。我們還多創建了幾個輔助函數。
在元素添加和實現的過程中,需要做調整操作,有兩種旋轉操作,對某節點的右鏈接進行左旋轉,如圖:
程式碼如下:
// 對某節點左旋轉
func (tree *RBTree) RotateLeft(h *RBTNode) {
if h != nil {
// 看圖理解
x := h.Right
h.Right = x.Left
if x.Left != nil {
x.Left.Parent = h
}
x.Parent = h.Parent
if h.Parent == nil {
tree.Root = x
} else if h.Parent.Left == h {
h.Parent.Left = x
} else {
h.Parent.Right = x
}
x.Left = h
h.Parent = x
}
}
或者左鏈接進行右旋轉,如圖:
程式碼如下:
// 對某節點右旋轉
func (tree *RBTree) RotateRight(h *RBTNode) {
if h != nil {
// 看圖理解
x := h.Left
h.Left = x.Right
if x.Right != nil {
x.Right.Parent = h
}
x.Parent = h.Parent
if h.Parent == nil {
tree.Root = x
} else if h.Parent.Right == h {
h.Parent.Right = x
} else {
h.Parent.Left = x
}
x.Right = h
h.Parent = x
}
}
旋轉作為局部調整,並不影響全局。
可以繼續查看下面的內容。
2.3. 添加元素實現
每次添加元素節點時,都將該節點Color
欄位,也就是父親指向它的鏈接設置為RED
紅色。
總結情況如下:
情況1:空樹,那麼插入節點直接變為根節點。
情況2:父節點是黑節點,直接插入即可,不破壞紅黑樹特徵。
情況3:父節點是紅節點,叔叔節點也是紅節點,這時對應2-3-4
樹的4節點,插入後變成了5節點,破壞了平衡,直接將祖父節點變色即可,然後向上遞歸處理,相當於2-3-4
樹的4節點提升,如圖:
情況4:父節點是紅節點,沒有叔叔或者叔叔是黑節點,插入後出現了兩個連續的紅鏈接,需要進行旋轉調整,如圖:
如果是順方向連續紅鏈接,旋轉一次即可,否則需要左右旋轉或者右左旋轉,旋轉兩次。
這次我們使用非遞歸的形式,效率會更高(可及時跳出循環),程式碼實現如下:
// 普通紅黑樹添加元素
func (tree *RBTree) Add(value int64) {
// 根節點為空
if tree.Root == nil {
// 根節點都是黑色
tree.Root = &RBTNode{
Value: value,
Color: BLACK,
}
return
}
// 輔助變數 t,表示新元素要插入到該子樹,t是該子樹的根節點
t := tree.Root
// 插入元素後,插入元素的父親節點
var parent *RBTNode
// 輔助變數,為了知道元素最後要插到左邊還是右邊
var cmp int64 = 0
for {
parent = t
cmp = value - t.Value
if cmp < 0 {
// 比當前節點小,往左子樹插入
t = t.Left
} else if cmp > 0 {
// 比當前節點節點大,往右子樹插入
t = t.Right
} else {
// 已經存在值了,更新出現的次數
t.Times = t.Times + 1
return
}
// 終於找到要插入的位置了
if t == nil {
break // 這時葉子節點是 parent,要插入到 parent 的下面,跳到外層去
}
}
// 新節點,它要插入到 parent下面
newNode := &RBTNode{
Value: value,
Parent: parent,
}
if cmp < 0 {
// 知道要從左邊插進去
parent.Left = newNode
} else {
// 知道要從右邊插進去
parent.Right = newNode
}
// 插入新節點後,可能破壞了紅黑樹特徵,需要修復,核心函數
tree.fixAfterInsertion(newNode)
}
// 調整新插入的節點,自底而上
// 可以看圖理解
func (tree *RBTree) fixAfterInsertion(node *RBTNode) {
// 插入的新節點一定要是紅色
node.Color = RED
// 節點不能是空,不能是根節點,父親的顏色必須為紅色(如果是黑色,那麼直接插入不破壞平衡,不需要調整了)
for node != nil && node != tree.Root && node.Parent.Color == RED {
// 父親在祖父的左邊
if ParentOf(node) == LeftOf(ParentOf(ParentOf(node))) {
// 叔叔節點
uncle := RightOf(ParentOf(ParentOf(node)))
// 圖例3左邊部分,叔叔是紅節點,祖父變色,也就是父親和叔叔變黑,祖父變紅
if IsRed(uncle) {
SetColor(ParentOf(node), BLACK)
SetColor(uncle, BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
// 還要向上遞歸
node = ParentOf(ParentOf(node))
} else {
// 圖例4左邊部分,叔叔是黑節點,並且插入的節點在父親的右邊,需要對父親左旋
if node == RightOf(ParentOf(node)) {
node = ParentOf(node)
tree.RotateLeft(node)
}
// 變色,並對祖父進行右旋
SetColor(ParentOf(node), BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
tree.RotateRight(ParentOf(ParentOf(node)))
}
} else {
// 父親在祖父的右邊,與父親在祖父的左邊相似
// 叔叔節點
uncle := LeftOf(ParentOf(ParentOf(node)))
// 圖例3右邊部分,叔叔是紅節點,祖父變色,也就是父親和叔叔變黑,祖父變紅
if IsRed(uncle) {
SetColor(ParentOf(node), BLACK)
SetColor(uncle, BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
// 還要向上遞歸
node = ParentOf(ParentOf(node))
} else {
// 圖例4右邊部分,叔叔是黑節點,並且插入的節點在父親的左邊,需要對父親右旋
if node == LeftOf(ParentOf(node)) {
node = ParentOf(node)
tree.RotateLeft(node)
}
// 變色,並對祖父進行左旋
SetColor(ParentOf(node), BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
tree.RotateLeft(ParentOf(ParentOf(node)))
}
}
}
// 根節點永遠為黑
tree.Root.Color = BLACK
}
首先,如果是空樹,那麼新建根節點:
// 根節點為空
if tree.Root == nil {
// 根節點都是黑色
tree.Root = &RBTNode{
Value: value,
Color: BLACK,
}
return
}
否則,需要找到葉子節點,方便新節點插進去:
// 輔助變數 t,表示新元素要插入到該子樹,t是該子樹的根節點
t := tree.Root
// 插入元素後,插入元素的父親節點
var parent *RBTNode
// 輔助變數,為了知道元素最後要插到左邊還是右邊
var cmp int64 = 0
for {
parent = t
cmp = value - t.Value
if cmp < 0 {
// 比當前節點小,往左子樹插入
t = t.Left
} else if cmp > 0 {
// 比當前節點節點大,往右子樹插入
t = t.Right
} else {
// 已經存在值了,更新出現的次數
t.Times = t.Times + 1
return
}
// 終於找到要插入的位置了
if t == nil {
break // 這時葉子節點是 parent,要插入到 parent 的下面,跳到外層去
}
}
找到了要插入的位置,該位置是parent
,將新元素插入:
// 新節點,它要插入到 parent下面
newNode := &RBTNode{
Value: value,
Parent: parent,
}
if cmp < 0 {
// 知道要從左邊插進去
parent.Left = newNode
} else {
// 知道要從右邊插進去
parent.Right = newNode
}
插入節點後,就需要進行調整操作了,這是核心:tree.fixAfterInsertion(newNode)
。
參照圖例對比一下,就可以理解調整操作的邏輯了:
// 調整新插入的節點,自底而上
// 可以看圖理解
func (tree *RBTree) fixAfterInsertion(node *RBTNode) {
// 插入的新節點一定要是紅色
node.Color = RED
// 節點不能是空,不能是根節點,父親的顏色必須為紅色(如果是黑色,那麼直接插入不破壞平衡,不需要調整了)
for node != nil && node != tree.Root && node.Parent.Color == RED {
// 父親在祖父的左邊
if ParentOf(node) == LeftOf(ParentOf(ParentOf(node))) {
// 叔叔節點
uncle := RightOf(ParentOf(ParentOf(node)))
// 圖例3左邊部分,叔叔是紅節點,祖父變色,也就是父親和叔叔變黑,祖父變紅
if IsRed(uncle) {
SetColor(ParentOf(node), BLACK)
SetColor(uncle, BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
// 還要向上遞歸
node = ParentOf(ParentOf(node))
} else {
// 圖例4左邊部分,叔叔是黑節點,並且插入的節點在父親的右邊,需要對父親左旋
if node == RightOf(ParentOf(node)) {
node = ParentOf(node)
tree.RotateLeft(node)
}
// 變色,並對祖父進行右旋
SetColor(ParentOf(node), BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
tree.RotateRight(ParentOf(ParentOf(node)))
}
} else {
// 父親在祖父的右邊,與父親在祖父的左邊相似
// 叔叔節點
uncle := LeftOf(ParentOf(ParentOf(node)))
// 圖例3右邊部分,叔叔是紅節點,祖父變色,也就是父親和叔叔變黑,祖父變紅
if IsRed(uncle) {
SetColor(ParentOf(node), BLACK)
SetColor(uncle, BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
// 還要向上遞歸
node = ParentOf(ParentOf(node))
} else {
// 圖例4右邊部分,叔叔是黑節點,並且插入的節點在父親的左邊,需要對父親右旋
if node == LeftOf(ParentOf(node)) {
node = ParentOf(node)
tree.RotateLeft(node)
}
// 變色,並對祖父進行左旋
SetColor(ParentOf(node), BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
tree.RotateLeft(ParentOf(ParentOf(node)))
}
}
}
// 根節點永遠為黑
tree.Root.Color = BLACK
}
可以知道,每次新插入的節點一定是紅色:node.Color = RED
。
接著判斷:node != nil && node != tree.Root && node.Parent.Color == RED
,發現節點非空,且非根節點,並且其父親是紅色,那麼插入新元素到父親下面就連續兩個紅鏈接了,需要調整,否則不需要調整。
調整時要區分父親是在祖父的左邊:ParentOf(node) == LeftOf(ParentOf(ParentOf(node)))
還是在右邊,接著判斷叔叔節點uncle := RightOf(ParentOf(ParentOf(node)))
的顏色。
如果叔叔是紅色,對應圖例3,如圖:
叔叔是紅節點,那麼祖父變色,也就是父親和叔叔變黑,祖父變紅,然後繼續往上遞歸:
// 圖例3右邊部分,叔叔是紅節點,祖父變色,也就是父親和叔叔變黑,祖父變紅
if IsRed(uncle) {
SetColor(ParentOf(node), BLACK)
SetColor(uncle, BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
// 還要向上遞歸
node = ParentOf(ParentOf(node))
}
如果叔叔不是紅色,對應圖例4,如圖:
在圖例4左邊部分,父親在祖父左邊,叔叔是黑節點,如果插入的節點在父親的右邊,需要對父親左旋,接著對祖父變色即可:
// 圖例4左邊部分,叔叔是黑節點,並且插入的節點在父親的右邊,需要對父親左旋
if node == RightOf(ParentOf(node)) {
node = ParentOf(node)
tree.RotateLeft(node)
}
// 變色,並對祖父進行右旋
SetColor(ParentOf(node), BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
tree.RotateRight(ParentOf(ParentOf(node)))
在圖例4右邊部分,父親在祖父右邊,叔叔是黑節點,如果插入的節點在父親的左邊,需要對父親右旋,接著對祖父變色即可:
// 圖例4右邊部分,叔叔是黑節點,並且插入的節點在父親的左邊,需要對父親右旋
if node == LeftOf(ParentOf(node)) {
node = ParentOf(node)
tree.RotateLeft(node)
}
// 變色,並對祖父進行左旋
SetColor(ParentOf(node), BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
tree.RotateLeft(ParentOf(ParentOf(node)))
最後,調整完後,根節點永遠為黑:
// 根節點永遠為黑
tree.Root.Color = BLACK
2.4. 添加元素演算法分析
當父親是紅節點,叔叔為空或是黑節點時,不需要向上遞歸,插入最多旋轉兩次就恢復了平衡。而如果父親和叔叔都是紅節點,那麼祖父變色之後可能需要一直遞歸向上處理,直到根節點,但是只要中途出現了旋轉,仍然是旋轉兩次就不需要繼續向上遞歸,樹就平衡了。
最壞情況的紅黑樹高度為2log(n)
(證明略),查找到插入的位置最壞情況查找2log(n)
次,然後進行調整,最壞情況遞歸到根節點,遞歸2log(n)
次(構造最壞情況的樹很難),去掉常數,添加元素的平均時間複雜度仍然為log(n)
,而旋轉最多不超過兩次。
2.5. 刪除元素實現
刪除操作就複雜得多了。對照一下2-3-4
樹。
- 情況1:如果刪除的是非葉子節點,找到其最小後驅節點,也就是在其右子樹中一直向左找,找到的該葉子節點替換被刪除的節點,然後刪除該葉子節點,變成情況2。
- 情況2:如果刪除的是葉子節點,如果它是紅節點,也就是父親指向它的鏈接為紅色,那麼直接刪除即可。否則,我們需要進行調整,使它變為紅節點,再刪除。
針對情況2,如果刪除的葉子節點是紅節點,那它對應2-3-4
樹的3節點或4節點,直接刪除即可,刪除後變為了2節點或3節點。否則,它是一個2節點,刪除後破壞了平衡,要麼向兄弟借值,要麼和父親的一個元素合併。
刪除的葉子節點是黑色的,才需要向兄弟借值,或與父親合併,有以下幾種情況:
刪除的葉子節點在父親的左邊:
圖例中21
,22
相當於向兄弟借值,而1
和24
相當於向父親的一個值合併後調整。
我們仔細分析一下:
圖例1
,當刪除的葉子節點在父親左邊,而兄弟是紅色節點,我們可以知道父親和兄弟的兒子絕對都是黑節點,將兄弟變黑,父親變紅,然後對父親右鏈接左旋。如圖:
這時調整後變為了圖例24
,這種情況實際上是在2-3-4
樹中和父親的值合併,只不過將父親的值轉了一個方向,變為圖例24
好分析。
圖例24
,當刪除的葉子節點在父親左邊,兄弟節點是黑色,兄弟的兒子們也都是黑色,相當於2-3-4
樹和兄弟借不到值了,需要將兄弟變為紅色,然後將父親作為一個整體來刪除,向上遞歸處理(相當於拉了父親的一個值和兄弟合併)。如圖:
圖例21
和21
就簡單了,相當2-3-4
樹與兄弟借值。
圖例21
,當刪除的葉子節點在父親左邊,且兄弟是黑色,而兄弟的右兒子是紅色,那麼兄弟設置成父親的顏色,兄弟的右兒子和父親變黑,接著對父親進行左旋,旋轉後可以直接刪除元素。如圖:
圖例22
,當刪除的葉子節點在父親左邊,且兄弟是黑色,而兄弟的右兒子是黑色,左兒子是紅色,將兄弟設置為紅色,兄弟的左兒子設置為黑色,對兄弟進行右旋,變為圖例21
。如圖:
當然,刪除的葉子節點可以在父親的右邊(與上述的圖反方向):
類似於刪除的葉子節點在父親的左邊,在此不再分析。
上面的圖例,我們其實可以將其畫出2-3-4
樹的形式,會更容易理解,在此就不畫出了。
這次我們使用非遞歸的形式,效率會更高(可及時跳出循環),程式碼實現如下:
// 普通紅黑樹刪除元素
func (tree *RBTree) Delete(value int64) {
// 查找元素是否存在,不存在則退出
p := tree.Find(value)
if p == nil {
return
}
// 刪除該節點
tree.delete(p)
}
// 刪除節點核心函數
// 找最小後驅節點來補位,刪除內部節點轉為刪除葉子節點
func (tree *RBTree) delete(node *RBTNode) {
// 如果左右子樹都存在,那麼從右子樹的左邊一直找一直找,就找能到最小後驅節點
if node.Left != nil && node.Right != nil {
s := node.Right
for s.Left != nil {
s = s.Left
}
// 刪除的葉子節點找到了,刪除內部節點轉為刪除葉子節點
node.Value = s.Value
node.Times = s.Times
node = s
} else if node.Left == nil && node.Right == nil {
// 沒有子樹,要刪除的節點就是葉子節點。
} else {
// 只有一棵子樹,因為紅黑樹的特徵,該子樹就只有一個節點
// 找到該唯一節點
replacement := node.Left
if node.Left == nil {
replacement = node.Right
}
// 替換開始,子樹的唯一節點替代被刪除的內部節點
replacement.Parent = node.Parent
if node.Parent == nil {
// 要刪除的節點的父親為空,表示要刪除的節點為根節點,唯一子節點成為樹根
tree.Root = replacement
// 根節點永遠都是黑色
tree.Root.Color = BLACK
} else if node == node.Parent.Left {
// 子樹的唯一節點替代被刪除的內部節點
node.Parent.Left = replacement
} else {
// 子樹的唯一節點替代被刪除的內部節點
node.Parent.Right = replacement
}
// 子樹的該唯一節點一定是一個紅節點,不然破壞紅黑樹特徵,所以替換後可以直接返回
return
}
// 要刪除的葉子節點沒有父親,那麼它是根節點,直接置空,返回
if node.Parent == nil {
tree.Root = nil
return
}
// 要刪除的葉子節點,是一個黑節點,刪除後會破壞平衡,需要進行調整,調整成可以刪除的狀態
if !IsRed(node) {
// 核心函數
tree.fixAfterDeletion(node)
}
// 現在可以刪除葉子節點了
if node == node.Parent.Left {
node.Parent.Left = nil
} else if node == node.Parent.Right {
node.Parent.Right = nil
}
}
// 調整刪除的葉子節點,自底向上
// 可以看圖理解
func (tree *RBTree) fixAfterDeletion(node *RBTNode) {
// 如果不是遞歸到根節點,且節點是黑節點,那麼繼續遞歸
for tree.Root != node && !IsRed(node) {
// 要刪除的節點在父親左邊,對應圖例1,2
if node == LeftOf(ParentOf(node)) {
// 找出兄弟
brother := RightOf(ParentOf(node))
// 兄弟是紅色的,對應圖例1,那麼兄弟變黑,父親變紅,然後對父親左旋,進入圖例23
if IsRed(brother) {
SetColor(brother, BLACK)
SetColor(ParentOf(node), RED)
tree.RotateLeft(ParentOf(node))
brother = RightOf(ParentOf(node)) // 圖例1調整後進入圖例23,兄弟此時變了
}
// 兄弟是黑色的,對應圖例21,22,23
// 兄弟的左右兒子都是黑色,進入圖例23,將兄弟設為紅色,父親所在的子樹作為整體,當作刪除的節點,繼續向上遞歸
if !IsRed(LeftOf(brother)) && !IsRed(RightOf(brother)) {
SetColor(brother, RED)
node = ParentOf(node)
} else {
// 兄弟的右兒子是黑色,進入圖例22,將兄弟設為紅色,兄弟的左兒子設為黑色,對兄弟右旋,進入圖例21
if !IsRed(RightOf(brother)) {
SetColor(LeftOf(brother), BLACK)
SetColor(brother, RED)
tree.RotateRight(brother)
brother = RightOf(ParentOf(node)) // 圖例22調整後進入圖例21,兄弟此時變了
}
// 兄弟的右兒子是紅色,進入圖例21,將兄弟設置為父親的顏色,兄弟的右兒子以及父親變黑,對父親左旋
SetColor(brother, IsRed(ParentOf(node)))
SetColor(ParentOf(node), BLACK)
SetColor(RightOf(brother), BLACK)
tree.RotateLeft(ParentOf(node))
// 可以返回刪除葉子節點了
return
}
} else {
// 要刪除的節點在父親右邊,對應圖例3,4
// 找出兄弟
brother := RightOf(ParentOf(node))
// 兄弟是紅色的,對應圖例3,那麼兄弟變黑,父親變紅,然後對父親右旋,進入圖例43
if IsRed(brother) {
SetColor(brother, BLACK)
SetColor(ParentOf(node), RED)
tree.RotateRight(ParentOf(node))
brother = LeftOf(ParentOf(node)) // 圖例3調整後進入圖例43,兄弟此時變了
}
// 兄弟是黑色的,對應圖例41,42,43
// 兄弟的左右兒子都是黑色,進入圖例43,將兄弟設為紅色,父親所在的子樹作為整體,當作刪除的節點,繼續向上遞歸
if !IsRed(LeftOf(brother)) && !IsRed(RightOf(brother)) {
SetColor(brother, RED)
node = ParentOf(node)
} else {
// 兄弟的左兒子是黑色,進入圖例42,將兄弟設為紅色,兄弟的右兒子設為黑色,對兄弟左旋,進入圖例41
if !IsRed(LeftOf(brother)) {
SetColor(RightOf(brother), BLACK)
SetColor(brother, RED)
tree.RotateLeft(brother)
brother = LeftOf(ParentOf(node)) // 圖例42調整後進入圖例41,兄弟此時變了
}
// 兄弟的左兒子是紅色,進入圖例41,將兄弟設置為父親的顏色,兄弟的左兒子以及父親變黑,對父親右旋
SetColor(brother, IsRed(ParentOf(node)))
SetColor(ParentOf(node), BLACK)
SetColor(LeftOf(brother), BLACK)
tree.RotateRight(ParentOf(node))
// 可以返回刪除葉子節點了
return
}
}
}
// 樹根節點永遠為黑
tree.Root.Color = BLACK
}
首先需要查找刪除的值是否存在,不存在則不必要調用刪除操作了:
// 普通紅黑樹刪除元素
func (tree *RBTree) Delete(value int64) {
// 查找元素是否存在,不存在則退出
p := tree.Find(value)
if p == nil {
return
}
// 刪除該節點
tree.delete(p)
}
存在刪除的節點,那麼進入刪除操作:tree.delete(p)
。
刪除操作無非就是找最小後驅節點來補位,刪除內部節點轉為刪除葉子節點,然後針對葉子節點的鏈接是不是黑色,是的話那麼需要調整:
// 刪除節點核心函數
// 找最小後驅節點來補位,刪除內部節點轉為刪除葉子節點
func (tree *RBTree) delete(node *RBTNode) {
// 如果左右子樹都存在,那麼從右子樹的左邊一直找一直找,就找能到最小後驅節點
if node.Left != nil && node.Right != nil {
s := node.Right
for s.Left != nil {
s = s.Left
}
// 刪除的葉子節點找到了,刪除內部節點轉為刪除葉子節點
node.Value = s.Value
node.Times = s.Times
node = s
} else if node.Left == nil && node.Right == nil {
// 沒有子樹,要刪除的節點就是葉子節點。
} else {
// 只有一棵子樹,因為紅黑樹的特徵,該子樹就只有一個節點
// 找到該唯一節點
replacement := node.Left
if node.Left == nil {
replacement = node.Right
}
// 替換開始,子樹的唯一節點替代被刪除的內部節點
replacement.Parent = node.Parent
if node.Parent == nil {
// 要刪除的節點的父親為空,表示要刪除的節點為根節點,唯一子節點成為樹根
tree.Root = replacement
// 根節點永遠都是黑色
tree.Root.Color = BLACK
} else if node == node.Parent.Left {
// 子樹的唯一節點替代被刪除的內部節點
node.Parent.Left = replacement
} else {
// 子樹的唯一節點替代被刪除的內部節點
node.Parent.Right = replacement
}
// 子樹的該唯一節點一定是一個紅節點,不然破壞紅黑樹特徵,所以替換後可以直接返回
return
}
// 要刪除的葉子節點沒有父親,那麼它是根節點,直接置空,返回
if node.Parent == nil {
tree.Root = nil
return
}
// 要刪除的葉子節點,是一個黑節點,刪除後會破壞平衡,需要進行調整,調整成可以刪除的狀態
if !IsRed(node) {
// 核心函數
tree.fixAfterDeletion(node)
}
// 現在可以刪除葉子節點了
if node == node.Parent.Left {
node.Parent.Left = nil
} else if node == node.Parent.Right {
node.Parent.Right = nil
}
}
當刪除的節點有兩棵子樹,那麼它是內部節點,找到其最小後驅節點來替換它,也就是其右子樹一直往左邊找:
// 如果左右子樹都存在,那麼從右子樹的左邊一直找一直找,就找能到最小後驅節點
if node.Left != nil && node.Right != nil {
s := node.Right
for s.Left != nil {
s = s.Left
}
// 刪除的葉子節點找到了,刪除內部節點轉為刪除葉子節點
node.Value = s.Value
node.Times = s.Times
node = s
}
如果沒有子樹,那麼刪除的節點就是葉子節點了:
else if node.Left == nil && node.Right == nil {
// 沒有子樹,要刪除的節點就是葉子節點。
}
如果只有一棵子樹,那麼根據紅黑樹的特徵,該子樹只有一個節點,其該節點是紅節點,那麼直接用該唯一子節點替代被刪除的節點即可:
} else {
// 只有一棵子樹,因為紅黑樹的特徵,該子樹就只有一個節點
// 找到該唯一節點
replacement := node.Left
if node.Left == nil {
replacement = node.Right
}
// 替換開始,子樹的唯一節點替代被刪除的內部節點
replacement.Parent = node.Parent
if node.Parent == nil {
// 要刪除的節點的父親為空,表示要刪除的節點為根節點,唯一子節點成為樹根
tree.Root = replacement
// 根節點永遠都是黑色
tree.Root.Color = BLACK
} else if node == node.Parent.Left {
// 子樹的唯一節點替代被刪除的內部節點
node.Parent.Left = replacement
} else {
// 子樹的唯一節點替代被刪除的內部節點
node.Parent.Right = replacement
}
// 子樹的該唯一節點一定是一個紅節點,不然破壞紅黑樹特徵,所以替換後可以直接返回
return
}
刪除葉子節點,如何刪除呢,首先如果它是根節點,那麼樹就空了:
// 要刪除的葉子節點沒有父親,那麼它是根節點,直接置空,返回
if node.Parent == nil {
tree.Root = nil
return
}
否則需要判斷該葉子節點是不是紅節點,如果不是紅節點,不能直接刪除,需要調整:
// 要刪除的葉子節點,是一個黑節點,刪除後會破壞平衡,需要進行調整,調整成可以刪除的狀態
if !IsRed(node) {
// 核心函數
tree.fixAfterDeletion(node)
}
最後,就可以刪除葉子節點了:
// 現在可以刪除葉子節點了
if node == node.Parent.Left {
node.Parent.Left = nil
} else if node == node.Parent.Right {
node.Parent.Right = nil
}
核心刪除調整函數fixAfterDeletion
非常重要,可以看圖理解:
// 調整刪除的葉子節點,自底向上
// 可以看圖理解
func (tree *RBTree) fixAfterDeletion(node *RBTNode) {
// 如果不是遞歸到根節點,且節點是黑節點,那麼繼續遞歸
for tree.Root != node && !IsRed(node) {
// 要刪除的節點在父親左邊,對應圖例1,2
if node == LeftOf(ParentOf(node)) {
// 找出兄弟
brother := RightOf(ParentOf(node))
// 兄弟是紅色的,對應圖例1,那麼兄弟變黑,父親變紅,然後對父親左旋,進入圖例23
if IsRed(brother) {
SetColor(brother, BLACK)
SetColor(ParentOf(node), RED)
tree.RotateLeft(ParentOf(node))
brother = RightOf(ParentOf(node)) // 圖例1調整後進入圖例23,兄弟此時變了
}
// 兄弟是黑色的,對應圖例21,22,23
// 兄弟的左右兒子都是黑色,進入圖例23,將兄弟設為紅色,父親所在的子樹作為整體,當作刪除的節點,繼續向上遞歸
if !IsRed(LeftOf(brother)) && !IsRed(RightOf(brother)) {
SetColor(brother, RED)
node = ParentOf(node)
} else {
// 兄弟的右兒子是黑色,進入圖例22,將兄弟設為紅色,兄弟的左兒子設為黑色,對兄弟右旋,進入圖例21
if !IsRed(RightOf(brother)) {
SetColor(LeftOf(brother), BLACK)
SetColor(brother, RED)
tree.RotateRight(brother)
brother = RightOf(ParentOf(node)) // 圖例22調整後進入圖例21,兄弟此時變了
}
// 兄弟的右兒子是紅色,進入圖例21,將兄弟設置為父親的顏色,兄弟的右兒子以及父親變黑,對父親左旋
SetColor(brother, IsRed(ParentOf(node)))
SetColor(ParentOf(node), BLACK)
SetColor(RightOf(brother), BLACK)
tree.RotateLeft(ParentOf(node))
// 可以返回刪除葉子節點了
return
}
} else {
// 要刪除的節點在父親右邊,對應圖例3,4
// 找出兄弟
brother := RightOf(ParentOf(node))
// 兄弟是紅色的,對應圖例3,那麼兄弟變黑,父親變紅,然後對父親右旋,進入圖例43
if IsRed(brother) {
SetColor(brother, BLACK)
SetColor(ParentOf(node), RED)
tree.RotateRight(ParentOf(node))
brother = LeftOf(ParentOf(node)) // 圖例3調整後進入圖例43,兄弟此時變了
}
// 兄弟是黑色的,對應圖例41,42,43
// 兄弟的左右兒子都是黑色,進入圖例43,將兄弟設為紅色,父親所在的子樹作為整體,當作刪除的節點,繼續向上遞歸
if !IsRed(LeftOf(brother)) && !IsRed(RightOf(brother)) {
SetColor(brother, RED)
node = ParentOf(node)
} else {
// 兄弟的左兒子是黑色,進入圖例42,將兄弟設為紅色,兄弟的右兒子設為黑色,對兄弟左旋,進入圖例41
if !IsRed(LeftOf(brother)) {
SetColor(RightOf(brother), BLACK)
SetColor(brother, RED)
tree.RotateLeft(brother)
brother = LeftOf(ParentOf(node)) // 圖例42調整後進入圖例41,兄弟此時變了
}
// 兄弟的左兒子是紅色,進入圖例41,將兄弟設置為父親的顏色,兄弟的左兒子以及父親變黑,對父親右旋
SetColor(brother, IsRed(ParentOf(node)))
SetColor(ParentOf(node), BLACK)
SetColor(LeftOf(brother), BLACK)
tree.RotateRight(ParentOf(node))
// 可以返回刪除葉子節點了
return
}
}
}
// 樹根節點永遠為黑
tree.Root.Color = BLACK
}
只有符合tree.Root != node && !IsRed(node)
才能繼續進入遞歸。
要刪除的節點在父親左邊:node == LeftOf(ParentOf(node))
,對應圖例1,2:
否則對應圖例3,4:
可以參考圖理解程式碼,程式碼注釋很清晰地對照了示例圖。
2.6. 刪除元素演算法分析
刪除元素比左傾紅黑樹的情況還要多,但是平均時間複雜度仍然是log(n)
,出現在和兄弟借不到值的情況下向上遞歸。和 AVL樹 區別是,普通紅黑樹刪除元素最多旋轉兩次,而 AVL樹 可能旋轉很多次,甚至自底向上一直旋轉到根節點。
2.7. 查找元素等實現
略。與左傾紅黑樹,AVL樹都一樣。
2.8. 驗證是否是一棵普通紅黑樹
如何確保我們的程式碼實現的就是一棵普通紅黑樹呢,可以進行驗證:
// 驗證是不是棵紅黑樹
func (tree *RBTree) IsRBTree() bool {
if tree == nil || tree.Root == nil {
return true
}
// 判斷樹是否是一棵二分查找樹
if !tree.Root.IsBST() {
return false
}
// 判斷樹是否遵循2-3-4樹,也就是不能有連續的兩個紅鏈接
if !tree.Root.Is234() {
return false
}
// 判斷樹是否平衡,也就是任意一個節點到葉子節點,經過的黑色鏈接數量相同
// 先計算根節點到最左邊葉子節點的黑鏈接數量
blackNum := 0
x := tree.Root
for x != nil {
if !IsRed(x) { // 是黑色鏈接
blackNum = blackNum + 1
}
x = x.Left
}
if !tree.Root.IsBalanced(blackNum) {
return false
}
return true
}
// 節點所在的子樹是否是一棵二分查找樹
func (node *RBTNode) IsBST() bool {
if node == nil {
return true
}
// 左子樹非空,那麼根節點必須大於左兒子節點
if node.Left != nil {
if node.Value > node.Left.Value {
} else {
fmt.Printf("father:%#v,lchild:%#v,rchild:%#v\n", node, node.Left, node.Right)
return false
}
}
// 右子樹非空,那麼根節點必須小於右兒子節點
if node.Right != nil {
if node.Value < node.Right.Value {
} else {
fmt.Printf("father:%#v,lchild:%#v,rchild:%#v\n", node, node.Left, node.Right)
return false
}
}
// 左子樹也要判斷是否是平衡查找樹
if !node.Left.IsBST() {
return false
}
// 右子樹也要判斷是否是平衡查找樹
if !node.Right.IsBST() {
return false
}
return true
}
// 節點所在的子樹是否遵循2-3-4樹
func (node *RBTNode) Is234() bool {
if node == nil {
return true
}
// 不允許連續兩個左紅鏈接
if IsRed(node) && IsRed(node.Left) {
fmt.Printf("father:%#v,lchild:%#v\n", node, node.Left)
return false
}
if IsRed(node) && IsRed(node.Right) {
fmt.Printf("father:%#v,rchild:%#v\n", node, node.Right)
return false
}
// 左子樹也要判斷是否遵循2-3-4樹
if !node.Left.Is234() {
return false
}
// 右子樹也要判斷是否是遵循2-3-4樹
if !node.Right.Is234() {
return false
}
return true
}
// 節點所在的子樹是否平衡,是否有 blackNum 個黑鏈接
func (node *RBTNode) IsBalanced(blackNum int) bool {
if node == nil {
return blackNum == 0
}
if !IsRed(node) {
blackNum = blackNum - 1
}
if !node.Left.IsBalanced(blackNum) {
fmt.Println("node.Left to leaf black link is not ", blackNum)
return false
}
if !node.Right.IsBalanced(blackNum) {
fmt.Println("node.Right to leaf black link is not ", blackNum)
return false
}
return true
}
運行請看完整程式碼。
2.9. 完整程式
package main
import "fmt"
// 普通紅黑樹實現,參考 Java TreeMap,更強壯。
// red-black tree
// 定義顏色
const (
RED = true
BLACK = false
)
// 普通紅黑樹
type RBTree struct {
Root *RBTNode // 樹根節點
}
// 新建一棵空樹
func NewRBTree() *RBTree {
return &RBTree{}
}
// 普通紅黑樹節點
type RBTNode struct {
Value int64 // 值
Times int64 // 值出現的次數
Left *RBTNode // 左子樹
Right *RBTNode // 右子樹
Parent *RBTNode // 父節點
Color bool // 父親指向該節點的鏈接顏色
}
// 節點的顏色
func IsRed(node *RBTNode) bool {
if node == nil {
return false
}
return node.Color == RED
}
// 返回節點的父親節點
func ParentOf(node *RBTNode) *RBTNode {
if node == nil {
return nil
}
return node.Parent
}
// 返回節點的左子節點
func LeftOf(node *RBTNode) *RBTNode {
if node == nil {
return nil
}
return node.Left
}
// 返回節點的右子節點
func RightOf(node *RBTNode) *RBTNode {
if node == nil {
return nil
}
return node.Right
}
// 設置節點顏色
func SetColor(node *RBTNode, color bool) {
if node != nil {
node.Color = color
}
}
// 對某節點左旋轉
func (tree *RBTree) RotateLeft(h *RBTNode) {
if h != nil {
// 看圖理解
x := h.Right
h.Right = x.Left
if x.Left != nil {
x.Left.Parent = h
}
x.Parent = h.Parent
if h.Parent == nil {
tree.Root = x
} else if h.Parent.Left == h {
h.Parent.Left = x
} else {
h.Parent.Right = x
}
x.Left = h
h.Parent = x
}
}
// 對某節點右旋轉
func (tree *RBTree) RotateRight(h *RBTNode) {
if h != nil {
// 看圖理解
x := h.Left
h.Left = x.Right
if x.Right != nil {
x.Right.Parent = h
}
x.Parent = h.Parent
if h.Parent == nil {
tree.Root = x
} else if h.Parent.Right == h {
h.Parent.Right = x
} else {
h.Parent.Left = x
}
x.Right = h
h.Parent = x
}
}
// 普通紅黑樹添加元素
func (tree *RBTree) Add(value int64) {
// 根節點為空
if tree.Root == nil {
// 根節點都是黑色
tree.Root = &RBTNode{
Value: value,
Color: BLACK,
}
return
}
// 輔助變數 t,表示新元素要插入到該子樹,t是該子樹的根節點
t := tree.Root
// 插入元素後,插入元素的父親節點
var parent *RBTNode
// 輔助變數,為了知道元素最後要插到左邊還是右邊
var cmp int64 = 0
for {
parent = t
cmp = value - t.Value
if cmp < 0 {
// 比當前節點小,往左子樹插入
t = t.Left
} else if cmp > 0 {
// 比當前節點節點大,往右子樹插入
t = t.Right
} else {
// 已經存在值了,更新出現的次數
t.Times = t.Times + 1
return
}
// 終於找到要插入的位置了
if t == nil {
break // 這時葉子節點是 parent,要插入到 parent 的下面,跳到外層去
}
}
// 新節點,它要插入到 parent下面
newNode := &RBTNode{
Value: value,
Parent: parent,
}
if cmp < 0 {
// 知道要從左邊插進去
parent.Left = newNode
} else {
// 知道要從右邊插進去
parent.Right = newNode
}
// 插入新節點後,可能破壞了紅黑樹特徵,需要修復,核心函數
tree.fixAfterInsertion(newNode)
}
// 調整新插入的節點,自底而上
// 可以看圖理解
func (tree *RBTree) fixAfterInsertion(node *RBTNode) {
// 插入的新節點一定要是紅色
node.Color = RED
// 節點不能是空,不能是根節點,父親的顏色必須為紅色(如果是黑色,那麼直接插入不破壞平衡,不需要調整了)
for node != nil && node != tree.Root && node.Parent.Color == RED {
// 父親在祖父的左邊
if ParentOf(node) == LeftOf(ParentOf(ParentOf(node))) {
// 叔叔節點
uncle := RightOf(ParentOf(ParentOf(node)))
// 圖例3左邊部分,叔叔是紅節點,祖父變色,也就是父親和叔叔變黑,祖父變紅
if IsRed(uncle) {
SetColor(ParentOf(node), BLACK)
SetColor(uncle, BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
// 還要向上遞歸
node = ParentOf(ParentOf(node))
} else {
// 圖例4左邊部分,叔叔是黑節點,並且插入的節點在父親的右邊,需要對父親左旋
if node == RightOf(ParentOf(node)) {
node = ParentOf(node)
tree.RotateLeft(node)
}
// 變色,並對祖父進行右旋
SetColor(ParentOf(node), BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
tree.RotateRight(ParentOf(ParentOf(node)))
}
} else {
// 父親在祖父的右邊,與父親在祖父的左邊相似
// 叔叔節點
uncle := LeftOf(ParentOf(ParentOf(node)))
// 圖例3右邊部分,叔叔是紅節點,祖父變色,也就是父親和叔叔變黑,祖父變紅
if IsRed(uncle) {
SetColor(ParentOf(node), BLACK)
SetColor(uncle, BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
// 還要向上遞歸
node = ParentOf(ParentOf(node))
} else {
// 圖例4右邊部分,叔叔是黑節點,並且插入的節點在父親的左邊,需要對父親右旋
if node == LeftOf(ParentOf(node)) {
node = ParentOf(node)
tree.RotateLeft(node)
}
// 變色,並對祖父進行左旋
SetColor(ParentOf(node), BLACK)
SetColor(ParentOf(ParentOf(node)), RED)
tree.RotateLeft(ParentOf(ParentOf(node)))
}
}
}
// 根節點永遠為黑
tree.Root.Color = BLACK
}
// 普通紅黑樹刪除元素
func (tree *RBTree) Delete(value int64) {
// 查找元素是否存在,不存在則退出
p := tree.Find(value)
if p == nil {
return
}
// 刪除該節點
tree.delete(p)
}
// 刪除節點核心函數
// 找最小後驅節點來補位,刪除內部節點轉為刪除葉子節點
func (tree *RBTree) delete(node *RBTNode) {
// 如果左右子樹都存在,那麼從右子樹的左邊一直找一直找,就找能到最小後驅節點
if node.Left != nil && node.Right != nil {
s := node.Right
for s.Left != nil {
s = s.Left
}
// 刪除的葉子節點找到了,刪除內部節點轉為刪除葉子節點
node.Value = s.Value
node.Times = s.Times
node = s
} else if node.Left == nil && node.Right == nil {
// 沒有子樹,要刪除的節點就是葉子節點。
} else {
// 只有一棵子樹,因為紅黑樹的特徵,該子樹就只有一個節點
// 找到該唯一節點
replacement := node.Left
if node.Left == nil {
replacement = node.Right
}
// 替換開始,子樹的唯一節點替代被刪除的內部節點
replacement.Parent = node.Parent
if node.Parent == nil {
// 要刪除的節點的父親為空,表示要刪除的節點為根節點,唯一子節點成為樹根
tree.Root = replacement
// 根節點永遠都是黑色
tree.Root.Color = BLACK
} else if node == node.Parent.Left {
// 子樹的唯一節點替代被刪除的內部節點
node.Parent.Left = replacement
} else {
// 子樹的唯一節點替代被刪除的內部節點
node.Parent.Right = replacement
}
// 子樹的該唯一節點一定是一個紅節點,不然破壞紅黑樹特徵,所以替換後可以直接返回
return
}
// 要刪除的葉子節點沒有父親,那麼它是根節點,直接置空,返回
if node.Parent == nil {
tree.Root = nil
return
}
// 要刪除的葉子節點,是一個黑節點,刪除後會破壞平衡,需要進行調整,調整成可以刪除的狀態
if !IsRed(node) {
// 核心函數
tree.fixAfterDeletion(node)
}
// 現在可以刪除葉子節點了
if node == node.Parent.Left {
node.Parent.Left = nil
} else if node == node.Parent.Right {
node.Parent.Right = nil
}
}
// 調整刪除的葉子節點,自底向上
// 可以看圖理解
func (tree *RBTree) fixAfterDeletion(node *RBTNode) {
// 如果不是遞歸到根節點,且節點是黑節點,那麼繼續遞歸
for tree.Root != node && !IsRed(node) {
// 要刪除的節點在父親左邊,對應圖例1,2
if node == LeftOf(ParentOf(node)) {
// 找出兄弟
brother := RightOf(ParentOf(node))
// 兄弟是紅色的,對應圖例1,那麼兄弟變黑,父親變紅,然後對父親左旋,進入圖例23
if IsRed(brother) {
SetColor(brother, BLACK)
SetColor(ParentOf(node), RED)
tree.RotateLeft(ParentOf(node))
brother = RightOf(ParentOf(node)) // 圖例1調整後進入圖例23,兄弟此時變了
}
// 兄弟是黑色的,對應圖例21,22,23
// 兄弟的左右兒子都是黑色,進入圖例23,將兄弟設為紅色,父親所在的子樹作為整體,當作刪除的節點,繼續向上遞歸
if !IsRed(LeftOf(brother)) && !IsRed(RightOf(brother)) {
SetColor(brother, RED)
node = ParentOf(node)
} else {
// 兄弟的右兒子是黑色,進入圖例22,將兄弟設為紅色,兄弟的左兒子設為黑色,對兄弟右旋,進入圖例21
if !IsRed(RightOf(brother)) {
SetColor(LeftOf(brother), BLACK)
SetColor(brother, RED)
tree.RotateRight(brother)
brother = RightOf(ParentOf(node)) // 圖例22調整後進入圖例21,兄弟此時變了
}
// 兄弟的右兒子是紅色,進入圖例21,將兄弟設置為父親的顏色,兄弟的右兒子以及父親變黑,對父親左旋
SetColor(brother, IsRed(ParentOf(node)))
SetColor(ParentOf(node), BLACK)
SetColor(RightOf(brother), BLACK)
tree.RotateLeft(ParentOf(node))
// 可以返回刪除葉子節點了
return
}
} else {
// 要刪除的節點在父親右邊,對應圖例3,4
// 找出兄弟
brother := RightOf(ParentOf(node))
// 兄弟是紅色的,對應圖例3,那麼兄弟變黑,父親變紅,然後對父親右旋,進入圖例43
if IsRed(brother) {
SetColor(brother, BLACK)
SetColor(ParentOf(node), RED)
tree.RotateRight(ParentOf(node))
brother = LeftOf(ParentOf(node)) // 圖例3調整後進入圖例43,兄弟此時變了
}
// 兄弟是黑色的,對應圖例41,42,43
// 兄弟的左右兒子都是黑色,進入圖例43,將兄弟設為紅色,父親所在的子樹作為整體,當作刪除的節點,繼續向上遞歸
if !IsRed(LeftOf(brother)) && !IsRed(RightOf(brother)) {
SetColor(brother, RED)
node = ParentOf(node)
} else {
// 兄弟的左兒子是黑色,進入圖例42,將兄弟設為紅色,兄弟的右兒子設為黑色,對兄弟左旋,進入圖例41
if !IsRed(LeftOf(brother)) {
SetColor(RightOf(brother), BLACK)
SetColor(brother, RED)
tree.RotateLeft(brother)
brother = LeftOf(ParentOf(node)) // 圖例42調整後進入圖例41,兄弟此時變了
}
// 兄弟的左兒子是紅色,進入圖例41,將兄弟設置為父親的顏色,兄弟的左兒子以及父親變黑,對父親右旋
SetColor(brother, IsRed(ParentOf(node)))
SetColor(ParentOf(node), BLACK)
SetColor(LeftOf(brother), BLACK)
tree.RotateRight(ParentOf(node))
// 可以返回刪除葉子節點了
return
}
}
}
// 樹根節點永遠為黑
tree.Root.Color = BLACK
}
// 找出最小值的節點
func (tree *RBTree) FindMinValue() *RBTNode {
if tree.Root == nil {
// 如果是空樹,返回空
return nil
}
return tree.Root.FindMinValue()
}
func (node *RBTNode) FindMinValue() *RBTNode {
// 左子樹為空,表面已經是最左的節點了,該值就是最小值
if node.Left == nil {
return node
}
// 一直左子樹遞歸
return node.Left.FindMinValue()
}
// 找出最大值的節點
func (tree *RBTree) FindMaxValue() *RBTNode {
if tree.Root == nil {
// 如果是空樹,返回空
return nil
}
return tree.Root.FindMaxValue()
}
func (node *RBTNode) FindMaxValue() *RBTNode {
// 右子樹為空,表面已經是最右的節點了,該值就是最大值
if node.Right == nil {
return node
}
// 一直右子樹遞歸
return node.Right.FindMaxValue()
}
// 查找指定節點
func (tree *RBTree) Find(value int64) *RBTNode {
if tree.Root == nil {
// 如果是空樹,返回空
return nil
}
return tree.Root.Find(value)
}
func (node *RBTNode) Find(value int64) *RBTNode {
if value == node.Value {
// 如果該節點剛剛等於該值,那麼返回該節點
return node
} else if value < node.Value {
// 如果查找的值小於節點值,從節點的左子樹開始找
if node.Left == nil {
// 左子樹為空,表示找不到該值了,返回nil
return nil
}
return node.Left.Find(value)
} else {
// 如果查找的值大於節點值,從節點的右子樹開始找
if node.Right == nil {
// 右子樹為空,表示找不到該值了,返回nil
return nil
}
return node.Right.Find(value)
}
}
// 中序遍歷
func (tree *RBTree) MidOrder() {
tree.Root.MidOrder()
}
func (node *RBTNode) MidOrder() {
if node == nil {
return
}
// 先列印左子樹
node.Left.MidOrder()
// 按照次數列印根節點
for i := 0; i <= int(node.Times); i++ {
fmt.Println(node.Value)
}
// 列印右子樹
node.Right.MidOrder()
}
// 驗證是不是棵紅黑樹
func (tree *RBTree) IsRBTree() bool {
if tree == nil || tree.Root == nil {
return true
}
// 判斷樹是否是一棵二分查找樹
if !tree.Root.IsBST() {
return false
}
// 判斷樹是否遵循2-3-4樹,也就是不能有連續的兩個紅鏈接
if !tree.Root.Is234() {
return false
}
// 判斷樹是否平衡,也就是任意一個節點到葉子節點,經過的黑色鏈接數量相同
// 先計算根節點到最左邊葉子節點的黑鏈接數量
blackNum := 0
x := tree.Root
for x != nil {
if !IsRed(x) { // 是黑色鏈接
blackNum = blackNum + 1
}
x = x.Left
}
if !tree.Root.IsBalanced(blackNum) {
return false
}
return true
}
// 節點所在的子樹是否是一棵二分查找樹
func (node *RBTNode) IsBST() bool {
if node == nil {
return true
}
// 左子樹非空,那麼根節點必須大於左兒子節點
if node.Left != nil {
if node.Value > node.Left.Value {
} else {
fmt.Printf("father:%#v,lchild:%#v,rchild:%#v\n", node, node.Left, node.Right)
return false
}
}
// 右子樹非空,那麼根節點必須小於右兒子節點
if node.Right != nil {
if node.Value < node.Right.Value {
} else {
fmt.Printf("father:%#v,lchild:%#v,rchild:%#v\n", node, node.Left, node.Right)
return false
}
}
// 左子樹也要判斷是否是平衡查找樹
if !node.Left.IsBST() {
return false
}
// 右子樹也要判斷是否是平衡查找樹
if !node.Right.IsBST() {
return false
}
return true
}
// 節點所在的子樹是否遵循2-3-4樹
func (node *RBTNode) Is234() bool {
if node == nil {
return true
}
// 不允許連續兩個左紅鏈接
if IsRed(node) && IsRed(node.Left) {
fmt.Printf("father:%#v,lchild:%#v\n", node, node.Left)
return false
}
if IsRed(node) && IsRed(node.Right) {
fmt.Printf("father:%#v,rchild:%#v\n", node, node.Right)
return false
}
// 左子樹也要判斷是否遵循2-3-4樹
if !node.Left.Is234() {
return false
}
// 右子樹也要判斷是否是遵循2-3-4樹
if !node.Right.Is234() {
return false
}
return true
}
// 節點所在的子樹是否平衡,是否有 blackNum 個黑鏈接
func (node *RBTNode) IsBalanced(blackNum int) bool {
if node == nil {
return blackNum == 0
}
if !IsRed(node) {
blackNum = blackNum - 1
}
if !node.Left.IsBalanced(blackNum) {
fmt.Println("node.Left to leaf black link is not ", blackNum)
return false
}
if !node.Right.IsBalanced(blackNum) {
fmt.Println("node.Right to leaf black link is not ", blackNum)
return false
}
return true
}
func main() {
tree := NewRBTree()
values := []int64{2, 3, 7, 10, 10, 10, 10, 23, 9, 102, 109, 111, 112, 113}
for _, v := range values {
tree.Add(v)
}
// 找到最大值或最小值的節點
fmt.Println("find min value:", tree.FindMinValue())
fmt.Println("find max value:", tree.FindMaxValue())
// 查找不存在的99
node := tree.Find(99)
if node != nil {
fmt.Println("find it 99!")
} else {
fmt.Println("not find it 99!")
}
// 查找存在的9
node = tree.Find(9)
if node != nil {
fmt.Println("find it 9!")
} else {
fmt.Println("not find it 9!")
}
tree.MidOrder()
// 刪除存在的9後,再查找9
tree.Delete(9)
tree.Delete(10)
tree.Delete(2)
tree.Delete(3)
tree.Add(4)
tree.Add(3)
tree.Add(10)
tree.Delete(111)
node = tree.Find(9)
if node != nil {
fmt.Println("find it 9!")
} else {
fmt.Println("not find it 9!")
}
if tree.IsRBTree() {
fmt.Println("is a rb tree")
} else {
fmt.Println("is not rb tree")
}
tree.Delete(3)
tree.Delete(4)
tree.Delete(7)
tree.Delete(10)
tree.Delete(23)
tree.Delete(102)
tree.Delete(109)
tree.Delete(112)
tree.Delete(112)
tree.MidOrder()
}
運行:
find min value: &{2 0 <nil> <nil> 0xc000092060 false}
find max value: &{113 0 <nil> <nil> 0xc0000921e0 true}
not find it 99!
find it 9!
2
3
7
9
10
10
10
10
23
102
109
111
112
113
not find it 9!
is a rb tree
紅黑樹,無論是左偏還是普通的紅黑樹,理解都可以直接理解2-3或2-3-4樹,添加操作比較簡單,刪除則是向兄弟借值或和父親合併,然後如果父親空了,把父親的子樹當成刪除的一個整體,繼續遞歸向上,至於二叉化的調整實現,則是將3或4節點畫成紅鏈接,可以多畫下圖就理解了。
三、應用場景
紅黑樹可以用來作為字典Map
的基礎數據結構,可以存儲鍵值對,然後通過一個鍵,可以快速找到鍵對應的值,相比哈希表查找,不需要佔用額外的空間。我們以上的程式碼實現只有value
,沒有key:value
,可以簡單改造實現字典。
Java
語言基礎類庫中的HashMap
,TreeSet
,TreeMap
都有使用到,C++
語言的STL
標準模板庫中,map
和set
類也有使用到。很多中間件也有使用到,比如Nginx
,但Golang
語言標準庫並沒有它。
系列文章入口
我是陳星星,歡迎閱讀我親自寫的 數據結構和演算法(Golang實現),文章首發於 閱讀更友好的GitBook。