Golang紅黑樹

紅黑樹

紅黑樹是每個節(jié)點都帶有顏色屬性（紅色或黑色）的二叉查找樹伍派。紅黑樹也屬于自平衡二叉查找樹。

紅黑樹具有如下性質(zhì)：

1. 每個節(jié)點要么是紅色要么是黑色。

2. 樹的根結(jié)點為黑色節(jié)點。

3. 所有葉子節(jié)點都是黑色節(jié)點（葉子是NIL節(jié)點）赡茸。

4. 每個紅色節(jié)點必須有兩個黑色的子節(jié)點（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點）。

5. 從任意節(jié)點到其每個葉子節(jié)點的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點祝闻。

一個紅黑樹的例子：

紅黑樹與平衡二叉樹(AVL)的區(qū)別

二者雖然都是自平衡二叉樹，但是各自對平衡的定義不同联喘。AVL的平衡是指樹中任意節(jié)點的左右子樹的高度差不超過1华蜒，而在紅黑樹中的平衡則是由上面5點性質(zhì)帶來的: 紅黑樹中的最短子樹h和最高子樹H滿足關(guān)系：H <= 2h。
AVL的平衡只需要通過樹的旋轉(zhuǎn)即可達成平衡豁遭，而紅黑樹除了旋轉(zhuǎn)還需要重繪節(jié)點的顏色叭喜。
AVL中的葉子節(jié)點帶有數(shù)據(jù)，而紅黑樹的葉子節(jié)點則是數(shù)據(jù)域為空的黑色節(jié)點蓖谢，即紅黑樹的所有葉子節(jié)點均為黑色捂蕴。

紅黑樹的查找操作與普通二叉樹相同，但是對于插入和刪除操作闪幽，因為新增或者刪除一個節(jié)點可能會打破紅黑樹的性質(zhì)啥辨，所以需要通過旋轉(zhuǎn)和節(jié)點顏色變更來恢復(fù)紅黑樹的性質(zhì)。紅黑樹的一切操作都是圍繞紅黑樹的5點性質(zhì)進行的盯腌。

紅黑樹插入節(jié)點

因為本質(zhì)也是一棵二叉樹溉知，所以紅黑樹的插入操作與普通二叉樹相同，只是為了維護紅黑樹的性質(zhì)腕够，需要進行節(jié)點顏色變更以及樹旋轉(zhuǎn)（如果需要的話）着倾。

對于新插入的節(jié)點，我們將其標(biāo)記為紅色節(jié)點（如果設(shè)為黑色燕少，就會導(dǎo)致根到葉子節(jié)點的路徑上有一條路多出一個額外的黑節(jié)點。但是設(shè)為紅色節(jié)后蒿囤，沒有多出黑色節(jié)點客们，雖然可能會出現(xiàn)兩個連續(xù)的紅色節(jié)點，但是可以通過顏色調(diào)換和樹旋轉(zhuǎn)來調(diào)整）材诽，對于插入操作需要進行什么操作（顏色變更和樹旋轉(zhuǎn)）底挫，取決于其他臨近節(jié)點的顏色。為了方便閱讀后面的代碼脸侥，下面給出一些基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)以及方法：

type (
    color uint //顏色
    
    //添加的元素
    Element interface {
        Value() interface{}
        Compare(Element) int //相等返回0建邓，小于返回負數(shù)，大于返回正數(shù)
    }

    //紅黑樹節(jié)點
    RedBlackNode struct {
        Color  color         //節(jié)點顏色
        Data   Element       //數(shù)據(jù)
        Parent *RedBlackNode //父節(jié)點
        Left   *RedBlackNode //左孩子
        Right  *RedBlackNode //右孩子
    }
    
    //紅黑樹
    RedBlackTree struct {
        Root *RedBlackNode //根節(jié)點
    }
)

const (
    Black color = iota + 1
    Red
)

//獲取某個節(jié)點的祖父節(jié)點（爺爺節(jié)點）
func (t *RedBlackNode) grandParent() *RedBlackNode {
    //根節(jié)點沒有父節(jié)點和祖父節(jié)點
    if t.Parent == nil {
        return nil
    }
    return t.Parent.Parent
}

//獲取某個節(jié)點的叔父節(jié)點（父節(jié)點的兄弟節(jié)點）
func (t *RedBlackNode) uncleNode() *RedBlackNode {
    if t.grandParent() == nil {
        return nil
    }
    if t.Parent == t.grandParent().Left {
        return t.grandParent().Right
    }
    return t.grandParent().Left
}

在添加節(jié)點的過程中：

性質(zhì)1和性質(zhì)3總是保持著睁枕。
性質(zhì)4只在增加紅色節(jié)點官边、重繪黑色節(jié)點為紅色沸手，或做旋轉(zhuǎn)時收到威脅。
性質(zhì)5只在增加黑色節(jié)點注簿、重繪紅色節(jié)點為黑色契吉，或做旋轉(zhuǎn)時收到威脅。

為了方便描述诡渴，在添加節(jié)點操作中捐晶，我們將要插入的節(jié)點標(biāo)為N，N的父節(jié)點標(biāo)為P妄辩，N的祖父節(jié)點標(biāo)為G惑灵，N的叔父節(jié)點標(biāo)為U，下面分情形討論插入節(jié)點的情況：

節(jié)點N位于樹的根上眼耀，沒有父節(jié)點英支。在這種情形下，我們把N重繪為黑色以滿足性質(zhì)2畔塔，因為它在每個路徑上對黑節(jié)點數(shù)量加1潭辈，符合性質(zhì)5。所以這種情況我們只需要將節(jié)點N重繪為黑色即可澈吨，如果N不位于根上把敢，則進入情形2。

func insertCase1(node *RedBlackNode) (root *RedBlackNode) {
     if node.Parent == nil {
          node.Color = Black
          root = node
          return     
      }
      return insertCase2(node)
}

N的父節(jié)點P是黑色谅辣，因為新節(jié)點是紅色修赞，所以性質(zhì)4沒有失效。因為沒有黑色節(jié)點的增加桑阶，所以在這種情形下性質(zhì)5仍然保持柏副，雖然N有可能有兩個黑色葉子節(jié)點，但是仔細想一想蚣录，如果N有兩個葉子節(jié)點割择，那么在添加節(jié)點前N的位置一定是黑色葉子節(jié)點，所以在添加前后萎河，通過該位置的到達任意葉子節(jié)點的黑色節(jié)點數(shù)目始終未變荔泳，所以性質(zhì)5始終保持著。如果N的父節(jié)點為紅色虐杯，則進入情形3玛歌。

    func insertCase2(node *RedBlackNode) (root *RedBlackNode) {
        if node.Parent.Color == Black {
            return 
        }
        return insertCase3(node)
    }

除了上面兩種情形，在接下來的情形中擎椰，N的父節(jié)點均為紅色支子，所以N一定有祖父節(jié)點（如果沒有祖父節(jié)點，那么父節(jié)點即為根結(jié)點达舒，這與父節(jié)點為紅色節(jié)點不相符）值朋，并且N一定有叔父節(jié)點（叔父節(jié)點可能是沒有數(shù)據(jù)的黑色葉子節(jié)點）叹侄。

如果父節(jié)點P和叔父節(jié)點U二者均為紅色，則我們可以將P和U重繪為黑色并將祖父節(jié)點G重繪為紅色（為了保持性質(zhì)5）⊥碳撸現(xiàn)在N有了一個黑色的父節(jié)點P圈膏，因為通過父節(jié)點P或者叔父節(jié)點U的任何路徑都必定通過祖父節(jié)點G，所以總的來說這些路徑上的黑色節(jié)點數(shù)量沒有變篙骡。但如果祖父節(jié)點G為根結(jié)點稽坤，那么就違背了性質(zhì)2，也有可能祖父節(jié)點G的父節(jié)點也是紅色糯俗，那么就違背了性質(zhì)4尿褪，為了解決這兩個隱患，我們在祖父節(jié)點G上遞歸的進行情形1整個過程（即把祖父節(jié)點G當(dāng)成新加入的節(jié)點進行各種情形的檢查）得湘。

注意：在情形3中杖玲，無論N作為P的左孩子還是右孩子出現(xiàn)，處理過程都一樣

    func insertCase3(node *RedBlackNode) (root *RedBlackNode) {
        if uncle := node.uncleNode(); uncle != nil && uncle.Color == Red {
            grandParent := node.grandParent()
            node.Parent.Color = Black
            uncle.Color = Black
            grandParent.Color = Red
            return insertCase1(grandParent)
        }
        return insertCase4(node)
    }

父節(jié)點P是紅色而叔父節(jié)點U是黑色或者缺少淘正，并且N是P的右孩子而P又是G的左孩子摆马，在這種情況下，我們進行一次左旋轉(zhuǎn)調(diào)節(jié)N和P的角色鸿吆，接著我們按情形5處理P以解決仍然失效的性質(zhì)4囤采。

    func insertCase4(node *RedBlackNode) (root *RedBlackNode) {
        grandParent := node.grandParent()
        if node == node.Parent.Right && node.Parent == grandParent.Left {
            leftRotate(node.Parent)
            node = node.Left
        } else if node == node.Parent.Left && node.Parent == grandParent.Right {
            rightRotate(node.Parent)
            node = node.Right
        }
        return insertCase5(node)
    }

父節(jié)點P是紅色而叔父節(jié)點U是黑色或者缺少，N是P的左孩子惩淳，而P也是G的左孩子蕉毯，這種情形下，我們針對G進行一次右旋轉(zhuǎn)思犁，在旋轉(zhuǎn)產(chǎn)生的樹中代虾，以前的父節(jié)點P現(xiàn)在是N和G的父節(jié)點，因為G肯定是黑色激蹲，所以我們交換P和G的顏色棉磨，交換后的樹滿足性質(zhì)4和性質(zhì)5，因為通過這三個節(jié)點中任何一個的所有路徑以前都通過G学辱，現(xiàn)在它們都通過P含蓉，無論哪種情形下，P現(xiàn)在都是三個節(jié)點中的唯一一個黑色節(jié)點项郊。

    func insertCase5(node *RedBlackNode) (root *RedBlackNode) {
        grandParent := node.grandParent()
        node.Parent.Color = Black
        grandParent.Color = Red
        if node == node.Parent.Left && node.Parent == grandParent.Left {
            root = rightRotate(grandParent)
        } else {
            root = leftRotate(grandParent)
        }
        return
    }

紅黑樹刪除節(jié)點

刪除節(jié)點時，我們需要先找到需要被刪除的節(jié)點斟赚。對于左右孩子均為葉子節(jié)點的着降，如果被刪除的節(jié)點為紅色，則直接將節(jié)點刪除即可拗军，但如果被刪除的節(jié)點是黑色任洞，因為路徑上的黑色節(jié)點數(shù)量少了一個蓄喇，所以需要對樹做調(diào)整以維持各性質(zhì)不變。如果被刪除節(jié)點存在一個葉子節(jié)點和一個子樹交掏，那么從子樹中找到最大或者最小值的節(jié)點妆偏，并將其值復(fù)制到被刪除的節(jié)點，最終將被復(fù)制的節(jié)點刪除即可盅弛，被刪除的節(jié)點最多只有一個非葉子節(jié)點的孩子節(jié)點钱骂。如果被刪除節(jié)點存在左右子樹，我們同樣可以從子樹中找到最大或者最小的值挪鹏，并將其復(fù)制到需要刪除的節(jié)點见秽，并將被復(fù)制的節(jié)點刪除即可，綜上讨盒，刪除問題最終都可以轉(zhuǎn)換成刪除只有一個非葉子節(jié)點的孩子節(jié)點的問題解取。（注意：上面說的復(fù)制只是復(fù)制值而不復(fù)制節(jié)點顏色）。

所以返顺，我們只需要討論刪除只有一個兒子（非葉子）的節(jié)點：

如果被刪除節(jié)點為紅色禀苦，此時該節(jié)點只有葉子節(jié)點，因為它的父親和孩子節(jié)點都為黑色遂鹊，所以只需要用它的孩子節(jié)點替換它即可振乏。
如果被刪除節(jié)點是黑色，而它的孩子節(jié)點為紅色的時候稿辙，如果用它的孩子節(jié)點頂替上來的話昆码，會破壞性質(zhì)5，但是如果重繪它的兒子節(jié)點為黑色邻储，則曾經(jīng)通過它的所有路徑將通過它的黑色兒子赋咽，這樣可以繼續(xù)保持性質(zhì)5。
如果被刪除節(jié)點和它的孩子節(jié)點均為黑色的時候（這種情況下吨娜，該節(jié)點的兩個孩子節(jié)點均為葉子節(jié)點脓匿，因為如果其中一個不為葉子節(jié)點，則從該節(jié)點通過其非葉子節(jié)點的路徑上的黑色節(jié)點數(shù)最少為2宦赠，而從該節(jié)點到另一個葉子節(jié)點的黑色節(jié)點數(shù)量為1陪毡，違反了性質(zhì)5，所以不成立勾扭，即這種情況下該節(jié)點的兩個孩子節(jié)點一定是葉子節(jié)點毡琉。）我們首先把要刪除的節(jié)點替換為它的兒子，出于方便妙色，稱呼這個兒子為N桅滋，稱呼它的兄弟（它父親的另一個兒子）為S。在后面的示意圖中P為N的父親， $S_L$ 為S的左兒子, $S_R$ 為S的右兒子丐谋，其中P才是需要刪除的節(jié)點芍碧，下面為獲取某個節(jié)點兄弟節(jié)點的函數(shù)以及刪除節(jié)點函數(shù)的入口:

//找到某個節(jié)點的兄弟節(jié)點
func (t *RedBlackNode) siblingNode() *RedBlackNode {
    if t.Parent == nil {
        return nil
    }
    if t == t.Parent.Left {
        return t.Parent.Right
    }
    return t.Parent.Left
}

//刪除node節(jié)點, 這里被刪除的節(jié)點一定最多只有一個非葉子節(jié)點的孩子節(jié)點，
func deleteNode(node *RedBlackNode) (root *RedBlackNode) {
    var child *RedBlackNode
    if node.Left.Data == nil {
        child = node.Right
    } else {
        child = node.Left
    }
    //如果刪除的是沒有子樹的根節(jié)點
    if node.Parent == nil && node.Left.Data == nil && node.Right.Data == nil {
        node.Data = nil
        node.Color = Black
        root = node
        return
    }
    //將孩子節(jié)點提升, 這里已經(jīng)將node刪除
    if node.Parent.Left == node {
        node.Parent.Left = child
    } else {
        node.Parent.Right = child
    }
    child.Parent = node.Parent

    //如果node為紅色号俐，刪除紅色節(jié)點不會影響紅黑樹的性質(zhì)泌豆，不需要調(diào)整
    //如果node是黑色，但孩子節(jié)點是紅色吏饿，此時只需要將孩子節(jié)點改為黑色即可
    //如果node是黑色叠蝇，孩子節(jié)點也是黑色狞贱，則少了一個黑色節(jié)點，需要對樹進行調(diào)整，以達到平衡
    if node.Color == Black {
        if child.Color == Red { //如果刪除的是黑色節(jié)點并且提升的孩子節(jié)點為紅色谢床，則只需要將孩子節(jié)點調(diào)色為黑色即可
            child.Color = Black
        } else { //否則需要其他操作
            root = deleteCase1(child)
        }
    }
    return
}

N是新的根烦味，此時樹的所有性質(zhì)都沒有被改變礁鲁，所以不需要操作箍铭，否則進入情形2。

    //被刪除的是根蜜唾，孩子節(jié)點作為新的根杂曲，否則進入case2
    func deleteCase1(node *RedBlackNode) (root *RedBlackNode) {
        if node.Parent == nil {
            return node
        }
        return deleteCase2(node)
    }

N的兄弟節(jié)點S是紅色，這種情形下我們在N的父親節(jié)點P上做左旋轉(zhuǎn)袁余，把兄弟節(jié)點S轉(zhuǎn)換為N的祖父節(jié)點擎勘，接著我們對調(diào)P和祖父的顏色，之后雖然所有路徑上的黑色節(jié)點數(shù)量沒有改變颖榜，但現(xiàn)在N有了一個黑色的兄弟和一個紅色的父親棚饵，我們接著按照情形4、5掩完、6來處理噪漾。

    func deleteCase2(node *RedBlackNode) (root *RedBlackNode) {
        var siblingNode = node.siblingNode()
        if siblingNode == nil {
            return
        }
    
        if siblingNode.Color == Red {
            node.Parent.Color = Red
            siblingNode.Color = Black
            if node == node.Parent.Left {
                leftRotate(node.Parent)
            } else {
                rightRotate(node.Parent)
            }
        }
        return deleteCase3(node)
    }

N的父親，S和S的兒子都是黑色的且蓬。在這種情況下欣硼，我們簡單的重繪S為紅色，結(jié)果是通過S的所有路徑（就是之前不通過N的那些路徑）恶阴，都少了一個黑色節(jié)點诈胜，因為刪除N的初始父親已經(jīng)使通過N的所有路徑少了一個黑色節(jié)點來，所以二者平衡冯事。但是所有通過P的路徑比不通過P的路徑少了一個黑色節(jié)點焦匈，我們可以重復(fù)情形1來重新恢復(fù)平衡。

    func deleteCase3(node *RedBlackNode) (root *RedBlackNode) {
        var siblingNode = node.siblingNode()
    
        if (node.Parent.Color == Black) &&
            (siblingNode.Color == Black) &&
            (siblingNode.Left.Color == Black) &&
            (siblingNode.Right.Color) == Black {
            siblingNode.Color = Red
            return deleteCase1(node.Parent)
        } else {
            return deleteCase4(node)
        }
    }

S和S的兒子都是黑色昵仅，但是N的父親是紅色缓熟。這種情形下，我們簡單的交換N的兄弟和父親的顏色。這不影響不通過N的路徑上的黑色節(jié)點的數(shù)量荚虚。但是通過N的路徑上的黑色節(jié)點數(shù)量增加了1，填補了已經(jīng)被刪除了的黑色節(jié)點籍茧。

    func deleteCase4(node *RedBlackNode) (root *RedBlackNode) {
        var siblingNode = node.siblingNode()
    
        if (node.Parent.Color == Red) &&
            (siblingNode.Color == Black) &&
            (siblingNode.Left.Color == Black) &&
            (siblingNode.Right.Color == Black) {
            siblingNode.Color = Red
            node.Parent.Color = Black
        } else {
            root = deleteCase5(node)
        }
        return
    }

S是黑色版述，S的左孩子是紅色，S的右孩子是黑色寞冯，而N是它父親的左兒子渴析，在這種情形下，我們在S上做右旋轉(zhuǎn)吮龄，這樣S的左兒子將成為S的父親和N的親兄弟俭茧。我們接著交換S和它的新父親的顏色，這樣所有路徑上仍有同樣數(shù)目的黑色節(jié)點漓帚，但是現(xiàn)在N有了一個黑色兄弟母债，它的右孩子是紅色的，接著進入情形6尝抖。

    func deleteCase5(node *RedBlackNode) (root *RedBlackNode) {
        var siblingNode = node.siblingNode()
    
        if siblingNode.Color == Black {
            if (node == node.Parent.Left) &&
                (siblingNode.Right.Color == Black) &&
                (siblingNode.Left.Color == Red) {
                siblingNode.Color = Red
                siblingNode.Left.Color = Black
                rightRotate(siblingNode)
            } else if (node == node.Parent.Right) &&
                (siblingNode.Left.Color == Black) &&
                (siblingNode.Right.Color == Red) {
                siblingNode.Color = Red
                siblingNode.Right.Color = Black
                leftRotate(siblingNode)
            }
        }
        return deleteCase6(node)
    }

S是黑色毡们，S的右孩子是紅色，而N是它父親的左孩子昧辽，在這種情形下衙熔，我們在N的父親上做左旋轉(zhuǎn)，這樣S成為N的祖父節(jié)點搅荞，我們接著交換N的父親和S的顏色红氯，并使S的右孩子為黑色。子樹在它的跟上仍然是同樣的顏色咕痛，所以性質(zhì)3沒有打破痢甘，但是N現(xiàn)在增加了一個黑色祖先：要么N的父親變成黑色，要么它是黑色而S被增加為一個黑色祖父暇检。所以通過N的路徑上都增加了一個黑色節(jié)點产阱。此時，如果一個路徑不通過N块仆，則有兩種可能性：

*. 它通過N的新兄弟构蹬。那么它以前和現(xiàn)在都必定通過S和N的福清，而它們只是交換了顏色悔据，所以路徑保持了同樣數(shù)目的黑色節(jié)點庄敛。
*. 它通過N的新叔父，S的右孩子科汗，那么它以前通過S藻烤、S的父親和S的右孩子，但是現(xiàn)在只通過S，它被假定為它以前的父親的顏色怖亭，和S的右孩子涎显，它從紅色變?yōu)榱撕谏罱K效果是這個路徑通過了同樣數(shù)目的黑色節(jié)點兴猩。

在任何情況下期吓，這些路徑上的黑色節(jié)點數(shù)目都沒有改變。在圖中的白色節(jié)點可以是紅色或黑色倾芝。

 func deleteCase6(node *RedBlackNode) (root *RedBlackNode) {
        var siblingNode = node.siblingNode()
    
        siblingNode.Color = node.Parent.Color
        node.Parent.Color = Black
    
        if node == node.Parent.Left {
            siblingNode.Right.Color = Black
            root = leftRotate(node.Parent)
        } else {
            siblingNode.Left.Color = Black
            root = rightRotate(node.Parent)
        }
        return
    }

不論插入還是刪除節(jié)點讨勤，最終都返回了一個root，因為在旋轉(zhuǎn)過程中樹的根結(jié)點有可能發(fā)生改變晨另，所以需要將每次旋轉(zhuǎn)后的最頂層的節(jié)點返回潭千，并最終與原來的root節(jié)點比較，如果不同則做替換借尿。

參考文獻

《Wiki》

最后

原文鏈接

謝謝閱讀刨晴，此處為源碼。