數據結構和算法(Golang實現)(30)查找算法-2-3-4樹和普通紅黑樹

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樹(註:BBalance平衡的意思)

它不是一棵二叉樹,是一棵四叉樹。具有以下特徵:

  1. 內部節點要麼有1個數據元素和2個孩子,要麼有2個數據元素和3個孩子,要麼有3個數據元素和4個孩子,葉子節點沒有孩子,但有1,2或3個數據元素。
  2. 所有葉子節點到根節點的長度一致。這個特徵保證了完全平衡,非常完美的平衡。
  3. 每個節點的數據元素保持從小到大排序,兩個數據元素之間的子樹的所有值大小介於兩個數據元素之間。

因為2-3-4樹的第二個特徵,它是一棵完美平衡的樹,非常完美,除了葉子節點,其他的節點都沒有空兒子,所以樹的高度非常的小。

如圖:

如果一個內部節點擁有一個數據元素、兩個子節點,則此節點為2節點。如果一個內部節點擁有兩個數據元素、三個子節點,則此節點為3節點。如果一個內部節點擁有三個數據元素、四個子節點,則此節點為4節點。

可以說,所有平衡樹的核心都在於插入和刪除邏輯,我們主要分析這兩個操作。

1.2. 2-3-4 樹插入元素

在插入元素時,需要先找到插入的位置,使用二分查找從上自下查找樹節點。

找到插入位置時,將元素插入該位置,然後進行調整,使得滿足2-3-4樹的特徵。主要有三種情況:

  1. 插入元素到一個2節點或3節點,直接插入即可,這樣節點變成3節點或4節點。
  2. 插入元素到一個4節點,該4節點的父親不是一個4節點,將4節點的中間元素提到父節點,原4節點變成兩個2節點,再將元素插入到其中一個2節點。
  3. 插入元素到一個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有兩個兒子BC,兒子BC要麼都沒有孩子,要麼孩子都是滿的,不然2-3-4樹所有葉子節點到根節點的長度一致這個特徵就被破壞了。

基於上面的現實,我們來分析刪除的不同情況,刪除中間節點和葉子節點。

情況1:刪除中間節點

刪除的是非葉子節點,該節點一定是有兩棵,三棵或者四棵子樹的,那麼從子樹中找到其最小後繼節點,該節點是葉子節點,用該節點替換被刪除的非葉子節點,然後再刪除這個葉子節點,進入情況2。

如何找到最小後繼節點,當有兩棵子樹時,那麼從右子樹一直往左下方找,如果有三棵子樹,被刪除節點在左邊,那麼從中子樹一直往左下方找,否則從右子樹一直往左下方找。如果有四棵子樹,那麼往被刪除節點右邊的子樹,一直往左下方找。

情況2:刪除葉子節點

刪除的是葉子節點,這時葉子節點如果是4節點,直接變為3節點,如果是3節點,那麼直接變為2節點即可,不影響平衡。但是,如果葉子節點是2節點,那麼刪除後,其父節點將會缺失一個兒子,破壞了滿孩子的2-3-4樹特徵,需要進行調整後才能刪除。

針對情況2,刪除一個2節點的葉子節點,會導致父節點缺失一個兒子,破壞了2-3-4樹的特徵,我們可以進行調整變換,主要有兩種調整:

  1. 重新分佈:嘗試從兄弟節點那裡借值,然後重新調整節點。
  2. 合併:如果兄弟借不到值,合併節點(與父親的元素)。

如果被刪除的葉子節點有兄弟是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樹的二叉樹形式來實現。

其定義為:

  1. 根節點的鏈接是黑色的。
  2. 每個紅色節點都必須有兩個黑色子節點。
  3. 任意一個節點到達葉子節點的所有路徑,經過的黑鏈接數量相同,也就是該樹是完美黑色平衡的。比如,某一個節點,它可以到達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. 情況1:如果刪除的是非葉子節點,找到其最小後驅節點,也就是在其右子樹中一直向左找,找到的該葉子節點替換被刪除的節點,然後刪除該葉子節點,變成情況2。
  2. 情況2:如果刪除的是葉子節點,如果它是紅節點,也就是父親指向它的鏈接為紅色,那麼直接刪除即可。否則,我們需要進行調整,使它變為紅節點,再刪除。

針對情況2,如果刪除的葉子節點是紅節點,那它對應2-3-4樹的3節點或4節點,直接刪除即可,刪除後變為了2節點或3節點。否則,它是一個2節點,刪除後破壞了平衡,要麼向兄弟借值,要麼和父親的一個元素合併。

刪除的葉子節點是黑色的,才需要向兄弟借值,或與父親合併,有以下幾種情況:

刪除的葉子節點在父親的左邊:

圖例中2122相當於向兄弟借值,而124相當於向父親的一個值合併後調整。

我們仔細分析一下:

圖例1,當刪除的葉子節點在父親左邊,而兄弟是紅色節點,我們可以知道父親和兄弟的兒子絕對都是黑節點,將兄弟變黑,父親變紅,然後對父親右鏈接左旋。如圖:

這時調整後變為了圖例24,這種情況實際上是在2-3-4樹中和父親的值合併,只不過將父親的值轉了一個方向,變為圖例24好分析。

圖例24,當刪除的葉子節點在父親左邊,兄弟節點是黑色,兄弟的兒子們也都是黑色,相當於2-3-4樹和兄弟借不到值了,需要將兄弟變為紅色,然後將父親作為一個整體來刪除,向上遞歸處理(相當於拉了父親的一個值和兄弟合併)。如圖:

圖例2121就簡單了,相當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語言基礎類庫中的HashMapTreeSetTreeMap都有使用到,C++語言的STL標準模板庫中,mapset類也有使用到。很多中間件也有使用到,比如Nginx,但Golang語言標準庫並沒有它。

系列文章入口

我是陳星星,歡迎閱讀我親自寫的 數據結構和算法(Golang實現),文章首發於 閱讀更友好的GitBook