數(shù)據(jù)結(jié)構(gòu)（六）：紅黑樹(shù)

紅黑樹(shù)是一種自平衡二叉查找樹(shù)，與 AVL 樹(shù)類似阎曹，提供 $O(log N)$ 級(jí)別的查詢伪阶、插入和刪除節(jié)點(diǎn)復(fù)雜度。相對(duì)于 AVL 樹(shù)單純的對(duì)每個(gè)節(jié)點(diǎn)的平衡因子進(jìn)行判斷芬膝，紅黑樹(shù)給節(jié)點(diǎn)賦予了顏色屬性，并通過(guò)對(duì)樹(shù)中節(jié)點(diǎn)的顏色進(jìn)行限制形娇，來(lái)保持整棵樹(shù)的平衡锰霜。

之前提到的自平衡二叉查找樹(shù)，即 AVL 樹(shù)桐早，屬于一種高度平衡的二叉查找樹(shù)癣缅，對(duì)每個(gè)節(jié)點(diǎn)的平衡因子進(jìn)行嚴(yán)苛的限制厨剪，所以 AVL 樹(shù)能夠提供 $O(log N)$ 的節(jié)點(diǎn)查詢復(fù)雜度。也因?yàn)閷?duì)每個(gè)節(jié)點(diǎn)的平衡因子限制較大友存，所以插入和刪除節(jié)點(diǎn)時(shí)祷膳，需要進(jìn)行很頻繁的平衡調(diào)節(jié)操作。

紅黑樹(shù)相對(duì)于 AVL 樹(shù)屡立，對(duì)樹(shù)的高度限制較為寬松直晨，所以紅黑樹(shù)的查找復(fù)雜度要略遜于 AVL 樹(shù)。也因?yàn)閷?duì)樹(shù)高度的限制較小膨俐，所以插入和刪除節(jié)點(diǎn)時(shí)需要較少的旋轉(zhuǎn)操作即可達(dá)到平衡狀態(tài)勇皇。

條件限制

紅黑樹(shù)中的節(jié)點(diǎn)存在顏色屬性，通過(guò)對(duì)節(jié)點(diǎn)顏色的限制來(lái)保持樹(shù)的平衡性焚刺。平衡的紅黑樹(shù)要求如下：

節(jié)點(diǎn)是紅色或者黑色敛摘；
根節(jié)點(diǎn)是黑色；
葉子節(jié)點(diǎn)是黑色乳愉；
紅色節(jié)點(diǎn)必須具有兩個(gè)黑色子節(jié)點(diǎn)兄淫；
從任一節(jié)點(diǎn)到其后代的葉子節(jié)點(diǎn)路徑中包含相同個(gè)數(shù)的黑色節(jié)點(diǎn)。

其中 1蔓姚、2 條沒(méi)什么可說(shuō)的捕虽，第 3 條中提到葉子節(jié)點(diǎn)，在紅黑樹(shù)的使用過(guò)程中使用一個(gè)特殊的節(jié)點(diǎn) $Nil$ 來(lái)表示葉子節(jié)點(diǎn)赂乐，該節(jié)點(diǎn)代表著終結(jié)條件薯鳍，在算法導(dǎo)論中稱這種使用方式為哨兵模式。在后續(xù)的 python 代碼中以 $None$ 來(lái)代表該終結(jié)條件挨措。

第四條所要描述的內(nèi)容挖滤，就是兩個(gè)紅色節(jié)點(diǎn)不能以父子關(guān)系相鄰。

因?yàn)楹谏?jié)點(diǎn)之間可以穿插著紅色節(jié)點(diǎn)浅役，所以第五條保證了任一子二叉樹(shù)中斩松，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)路徑不多于最短路徑的二倍。

note：后續(xù)的示例中隱藏葉子節(jié)點(diǎn) $Nil$ 的表示觉既，所以看到紅色葉子節(jié)點(diǎn)屬于正常情況

插入節(jié)點(diǎn)情況

待插入新節(jié)點(diǎn)顏色初始為紅色惧盹，因?yàn)榧t色節(jié)點(diǎn)的插入不一定影響紅黑樹(shù)的平衡性，而黑色節(jié)點(diǎn)的插入一定會(huì)引起紅黑樹(shù)的不平衡瞪讼。

新節(jié)點(diǎn)的插入有如下幾種情形：

1 新節(jié)點(diǎn)為根節(jié)點(diǎn)钧椰。

即當(dāng)前紅黑樹(shù)為空樹(shù)，插入新節(jié)點(diǎn)后符欠，只需要變換節(jié)點(diǎn)顏色為黑色嫡霞，即可滿足紅黑樹(shù)的平衡限制條件；

original	adjusted

2. 新節(jié)點(diǎn)的父節(jié)點(diǎn)為黑色希柿。

若新節(jié)點(diǎn)不為根節(jié)點(diǎn)诊沪，則具有父節(jié)點(diǎn)养筒，父節(jié)點(diǎn)顏色無(wú)外乎黑、紅兩種端姚。當(dāng)父節(jié)點(diǎn)顏色為黑色時(shí)晕粪，此時(shí)插入新節(jié)點(diǎn)不影響紅黑樹(shù)的平衡性，所以不需要調(diào)整操作渐裸；

3. 新節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色巫湘，同時(shí)叔父節(jié)點(diǎn)的顏色也為紅色。

若父節(jié)點(diǎn)和叔父節(jié)點(diǎn)的顏色都為紅色橄仆，則根據(jù)條件 4 剩膘，祖父節(jié)點(diǎn)的顏色為黑色。因?yàn)樾虏迦牍?jié)點(diǎn)顏色為紅色盆顾，違反了條件 4怠褐，此時(shí)只需要變換父節(jié)點(diǎn)和叔父節(jié)點(diǎn)的顏色為黑色，祖父節(jié)點(diǎn)的顏色為紅色即可您宪。變換顏色后奈懒，只需要考慮祖父節(jié)點(diǎn)顏色為紅色，是否違反了條件限制宪巨，將祖父節(jié)點(diǎn)作為“新”節(jié)點(diǎn)磷杏，遞歸進(jìn)行處理即可。

original	adjusted

此時(shí)無(wú)所謂新節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)或右子節(jié)點(diǎn)捏卓。

4. 新節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色极祸，叔父節(jié)點(diǎn)的顏色不為紅色。且新節(jié)點(diǎn) $N$ 是其父節(jié)點(diǎn) $P$ 的左子節(jié)點(diǎn)怠晴，同時(shí)父節(jié)點(diǎn) $P$ 是祖父節(jié)點(diǎn) $G$ 的左子節(jié)點(diǎn)遥金；或者新節(jié)點(diǎn) $N$ 是其父節(jié)點(diǎn) $P$ 的右子節(jié)點(diǎn)，同時(shí)父節(jié)點(diǎn) $P$ 是祖父節(jié)點(diǎn) $G$ 的右子節(jié)點(diǎn)蒜田。

不妨假設(shè)新節(jié)點(diǎn) $N$ 是其父節(jié)點(diǎn) $P$ 的左子節(jié)點(diǎn)稿械，同時(shí)父節(jié)點(diǎn) $P$ 是祖父節(jié)點(diǎn) $G$ 的左子節(jié)點(diǎn)。因?yàn)楦腹?jié)點(diǎn) $P$ 為紅色冲粤，所以祖父節(jié)點(diǎn) $G$ 顏色為黑色美莫。此時(shí)以 $P$ 節(jié)點(diǎn)為軸心執(zhí)行一次右旋操作，并對(duì)父節(jié)點(diǎn) $P$ 和祖父節(jié)點(diǎn) $G$ 進(jìn)行顏色變換梯捕。

original	adjusted

旋轉(zhuǎn)后的變色操作厢呵，保證了通過(guò)每個(gè)節(jié)點(diǎn)到后代葉子節(jié)點(diǎn)的路徑上，包含的黑色節(jié)點(diǎn)個(gè)數(shù)不變傀顾，即滿足了條件約束襟铭。

新節(jié)點(diǎn) $N$ 不一定只是一個(gè)單一的新插入節(jié)點(diǎn)锣尉，也可能是一顆二叉樹(shù)的根節(jié)點(diǎn)充活，例如情形 3 的處理后框产，遞歸處理的“新”節(jié)點(diǎn)就是二叉樹(shù)的根節(jié)點(diǎn)荐吵〈碛ⅲ空白的部分表示此處可能為空樹(shù)或非空樹(shù)入撒，其實(shí)這里的叔父節(jié)點(diǎn) $U$ 也可以是空樹(shù)或非空樹(shù)。

5. 新節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色椭岩，叔父節(jié)點(diǎn)的顏色不為紅色茅逮。且新節(jié)點(diǎn) $N$ 是其父節(jié)點(diǎn) $P$ 的右子節(jié)點(diǎn)，同時(shí)父節(jié)點(diǎn) $P$ 是祖父節(jié)點(diǎn) $G$ 的左子節(jié)點(diǎn)判哥；或者新節(jié)點(diǎn) $N$ 是其父節(jié)點(diǎn) $P$ 的左子節(jié)點(diǎn)献雅，同時(shí)父節(jié)點(diǎn) $P$ 是祖父節(jié)點(diǎn) $G$ 的右子節(jié)點(diǎn)。

不妨假設(shè)新節(jié)點(diǎn) $N$ 是其父節(jié)點(diǎn) $P$ 的右子節(jié)點(diǎn)塌计，同時(shí)父節(jié)點(diǎn) $P$ 是祖父節(jié)點(diǎn) $G$ 的左子節(jié)點(diǎn)挺身。因?yàn)楦腹?jié)點(diǎn) $P$ 為紅色，所以祖父節(jié)點(diǎn) $G$ 顏色為黑色锌仅。此時(shí)以節(jié)點(diǎn) $N$ 為軸心執(zhí)行一次左旋操作章钾。

d1.png	d1.png

旋轉(zhuǎn)操作前后，通過(guò)每個(gè)節(jié)點(diǎn)到后代葉子節(jié)點(diǎn)的路徑上热芹，所經(jīng)過(guò)的黑色節(jié)點(diǎn)個(gè)數(shù)不發(fā)生變化贱傀。此時(shí)情形轉(zhuǎn)變?yōu)榍樾?4，所以按照情形 4 進(jìn)行處理即可伊脓。

由插入節(jié)點(diǎn)的情形分析可知府寒，插入節(jié)點(diǎn)時(shí)最多只會(huì)進(jìn)行兩次旋轉(zhuǎn)操作，即情形 5 旋轉(zhuǎn)后變?yōu)榍樾?4报腔，情形 4 旋轉(zhuǎn)變色后滿足平衡條件株搔。變色操作則可能遞歸進(jìn)行到根節(jié)點(diǎn)。

節(jié)點(diǎn)插入后調(diào)整代碼

def adjustment(tree, node):
    if not node.parent:                        # case 1 : the node is the root node
        node.color = 'black'
    elif node.parent.color == 'black':         # case 2 : parent node is black
        pass
    else:  # parent node's color is red
        uncle = uncleNode(node)
        if uncle and uncle.color == 'red':      # case 3 : uncle node is red
            uncle.color, node.parent.color, uncle.parent.color = 'black', 'black', 'red'
            adjustment(tree, uncle.parent)
        else:  # uncle node does not exists or color is black
            rotationType, colorChange = rotationDetection(node)
            parent, grantParent = node.parent, node.parent.parent
            if colorChange:                       # case 4 : rotate and change color
                if rotationType == 'L2R':
                    node = rotateL2R(node.parent)
                elif rotationType == 'R2L':
                    node = rotateR2L(node.parent)
                parent.color,grantParent.color = 'black','red'
                if not node.parent:
                    tree.root = node
            else:                                   # case 5 : just rotate
                if rotationType == 'L2R':
                    node = rotateL2R(node).rchild
                elif rotationType == 'R2L':
                    node = rotateR2L(node).lchild
                adjustment(tree,node)

刪除節(jié)點(diǎn)情況

二叉查找樹(shù)在進(jìn)行節(jié)點(diǎn)刪除時(shí)榄笙，若待刪除節(jié)點(diǎn)的度為 2 時(shí)邪狞，則可以將刪除操作“轉(zhuǎn)移”到其后代度不為 2 的子節(jié)點(diǎn)上，所以后續(xù)討論的待刪除節(jié)點(diǎn)的度都不為 2茅撞。

節(jié)點(diǎn)刪除有如下幾種情形：

1. 待刪除節(jié)點(diǎn)顏色為紅色帆卓。

因?yàn)榇齽h除節(jié)點(diǎn)的度為 0 或 1，根據(jù)條件 5 可知米丘，該待刪除節(jié)點(diǎn)為葉子節(jié)點(diǎn)剑令，所以直接刪除該節(jié)點(diǎn)并不影響二叉樹(shù)的平衡性。

2. 待刪除節(jié)點(diǎn)為黑色拄查，度為 1吁津。

根據(jù)條件 5 可知，若待刪除節(jié)點(diǎn)度為 1，則子節(jié)點(diǎn)顏色為紅色碍脏。此時(shí)可以直接刪除該節(jié)點(diǎn)梭依，用子節(jié)點(diǎn)來(lái)填充該節(jié)點(diǎn)位置，對(duì)子節(jié)點(diǎn)進(jìn)行顏色變換即可典尾。

3. 待刪除節(jié)點(diǎn)為黑色役拴，度為 0。

情形 1, 2 中的節(jié)點(diǎn)刪除場(chǎng)景較為簡(jiǎn)單钾埂，可以直接進(jìn)行節(jié)點(diǎn)刪除操作河闰，最多只需要通過(guò)節(jié)點(diǎn)顏色變換即可保持二叉樹(shù)的平衡性（注意根節(jié)點(diǎn)的變化）。若待刪除節(jié)點(diǎn)度為 0褥紫，此時(shí)不妨對(duì)二叉樹(shù)先進(jìn)行一番預(yù)平衡操作姜性，然后再進(jìn)行節(jié)點(diǎn)刪除，以此保證刪除節(jié)點(diǎn)后二叉樹(shù)處于平衡狀態(tài)髓考。

簡(jiǎn)單場(chǎng)景下節(jié)點(diǎn)刪除代碼

def delete(tree, node):
    if node.color == 'red':               # case 1 : the node color is red
        if node == node.parent.lchild:
            node.parent.lchild = None
        else:
            node.parent.rchild = None
    else:
        parent, child = node.parent, node.lchild if node.lchild else node.rchild
        if not parent:   # the node is the root node
            tree.root = child
        if child:                        # case 2 : the node is black with one red child
            if parent: # the node is not the root node
                if node == parent.lchild:
                    parent.lchild = child
                else:
                    parent.rchild = child
            child.color, child.parent = 'black', parent
        else:                          # case 3 : the node is black with no child
            if parent: # the node is not the root node
                balanceBeforeDelete(tree, node, parent)
                if node == parent.lchild:
                    parent.lchild = None
                else:
                    parent.rchild = None

下面以 $N$ 表示待刪除節(jié)點(diǎn)部念，以 $P$ 表示待刪除節(jié)點(diǎn)的父節(jié)點(diǎn)，以 $S$ 表示待刪除節(jié)點(diǎn)的兄弟節(jié)點(diǎn)氨菇，以 $S_l$ 表示兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)印机，以 $S_r$ 表示兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)。不妨以 $N$ 節(jié)點(diǎn)作為 $P$ 節(jié)點(diǎn)的左子節(jié)點(diǎn)進(jìn)行討論门驾，對(duì)稱的情況下處理過(guò)程類似射赛。

3.1 兄弟節(jié)點(diǎn) $S$ 為黑色， $S_r$ 節(jié)點(diǎn)為紅色奶是。

兄弟節(jié)點(diǎn) $S$ 的右子節(jié)點(diǎn) $S_r$ 為紅色楣责，則兄弟節(jié)點(diǎn) $S$ 為黑色，父節(jié)點(diǎn) $P$ 顏色不確定聂沙。此時(shí)以節(jié)點(diǎn) $S$ 為軸心執(zhí)行左旋操作秆麸，并對(duì)部分節(jié)點(diǎn)執(zhí)行顏色變換操作。

original	adjusted

左旋操作后及汉，變換 $S_r$ 節(jié)點(diǎn)顏色沮趣。若 $P$ 節(jié)點(diǎn)為紅色，則左旋操作后坷随，對(duì) $P$ 節(jié)點(diǎn)和 $S$ 節(jié)點(diǎn)進(jìn)行顏色變換房铭。此時(shí)刪除節(jié)點(diǎn) $N$ 之后，通過(guò)其他節(jié)點(diǎn)的路徑上黑色節(jié)點(diǎn)個(gè)數(shù)不變温眉，滿足平衡條件缸匪。

3.2 兄弟節(jié)點(diǎn) $S$ 為黑色， $S_l$ 節(jié)點(diǎn)為紅色类溢， $S_r$ 節(jié)點(diǎn)不為紅色凌蔬。

兄弟節(jié)點(diǎn) $S$ 的左子節(jié)點(diǎn) $S_r$ 為紅色，則兄弟節(jié)點(diǎn) $S$ 為黑色，父節(jié)點(diǎn) $P$ 顏色不確定砂心， $S_r$ 節(jié)點(diǎn)不存在或存在為黑色懈词。此時(shí)以節(jié)點(diǎn) $S_l$ 為軸心執(zhí)行右旋操作，并對(duì) $S$ 和 $S_l$ 節(jié)點(diǎn)執(zhí)行顏色變換操作辩诞。

original	adjusted

執(zhí)行右旋操作后可以發(fā)現(xiàn)钦睡，此時(shí)情形演變?yōu)榍樾?3.1，所以此時(shí)再次對(duì)待刪除節(jié)點(diǎn) $N$ 進(jìn)行平衡操作即可躁倒。

3.3 兄弟節(jié)點(diǎn) $S$ 為黑色， $S$ 節(jié)點(diǎn)沒(méi)有紅色子節(jié)點(diǎn)洒琢，且父節(jié)點(diǎn) $P$ 為黑色秧秉。

兄弟節(jié)點(diǎn) $S$ 和父節(jié)點(diǎn) $P$ 為黑色，且兄弟節(jié)點(diǎn) $S$ 沒(méi)有紅色子節(jié)點(diǎn)衰抑，此時(shí)對(duì) $S$ 進(jìn)行顏色變換象迎。

original	adjusted

對(duì)兄弟節(jié)點(diǎn) $S$ 進(jìn)行顏色變換后，可以發(fā)現(xiàn)呛踊，忽略待刪除節(jié)點(diǎn) $N$ 砾淌，此時(shí)父節(jié)點(diǎn) $P$ 處于和待刪除節(jié)點(diǎn) $N$ 同樣的處境，即通過(guò)該節(jié)點(diǎn)的路徑上黑色節(jié)點(diǎn)個(gè)數(shù)減一谭网。所以此時(shí)將父節(jié)點(diǎn) $P$ 作為新的節(jié)點(diǎn) $N$ 進(jìn)行同樣的預(yù)平衡操作汪厨。

3.4 兄弟節(jié)點(diǎn) $S$ 為黑色， $S$ 節(jié)點(diǎn)沒(méi)有紅色子節(jié)點(diǎn)愉择，且父節(jié)點(diǎn) $P$ 為紅色劫乱。

兄弟節(jié)點(diǎn) $S$ 為黑色，且沒(méi)有紅色子節(jié)點(diǎn)锥涕，父節(jié)點(diǎn) $P$ 為紅色衷戈，此時(shí)只需要對(duì)節(jié)點(diǎn) $S$ 和 $P$ 進(jìn)行顏色變換即可。

original	adjusted

對(duì)兄弟節(jié)點(diǎn) $S$ 和父節(jié)點(diǎn) $P$ 進(jìn)行顏色變換后层坠，可以發(fā)現(xiàn)殖妇，忽略待刪除節(jié)點(diǎn) $N$ ，此時(shí)通過(guò)各節(jié)點(diǎn)的路徑上黑色節(jié)點(diǎn)個(gè)數(shù)不變破花，即二叉樹(shù)處于平衡狀態(tài)谦趣。

3.5 兄弟節(jié)點(diǎn) $S$ 為紅色。

兄弟節(jié)點(diǎn) $S$ 為紅色座每，則此時(shí)父節(jié)點(diǎn) $P$ 為黑色蔚润。此時(shí)以 $S$ 節(jié)點(diǎn)為軸心進(jìn)行左旋操作，并對(duì)節(jié)點(diǎn) $S$ 和 $P$ 進(jìn)行變色操作尺栖。

original	adjusted

旋轉(zhuǎn)并進(jìn)行節(jié)點(diǎn)顏色變換后嫡纠，可以發(fā)現(xiàn)，此時(shí)的二叉樹(shù)同樣處于平衡狀態(tài)，所以這一步的旋轉(zhuǎn)與顏色變換操作只是一個(gè)過(guò)渡處理除盏，并沒(méi)有起到預(yù)平衡的作用叉橱，即刪除節(jié)點(diǎn) $N$ 之后，二叉樹(shù)仍然是不平衡的者蠕。但是經(jīng)過(guò)該步的處理之后窃祝，二叉樹(shù)的狀態(tài)演變?yōu)榍樾?3.1，3.2 或者 3.4 中的一種踱侣，所以可以對(duì)待刪除節(jié)點(diǎn) $N$ 再次進(jìn)行預(yù)平衡處理粪小。

節(jié)點(diǎn)刪除的所有情況如上，由各個(gè)情形描述可知抡句，節(jié)點(diǎn)刪除最多經(jīng)過(guò)三次旋轉(zhuǎn)即可達(dá)到平衡狀態(tài)探膊，即情形 3.5 旋轉(zhuǎn)后變?yōu)榍樾?3.2，情形 3.2 旋轉(zhuǎn)后變?yōu)榍樾?3.1待榔，情形 3.1 旋轉(zhuǎn)后滿足平衡條件逞壁。變色操作則可能遞歸進(jìn)行到根節(jié)點(diǎn)。

預(yù)平衡代碼

def balanceBeforeDelete(tree, node, parent):
    sibling = parent.rchild if node == parent.lchild else parent.lchild
    if sibling.color == 'black':
        siblingLeftChild, siblingRightChild = sibling.lchild, sibling.rchild
        if siblingRightChild and siblingRightChild.color == 'red':
            if node == parent.lchild:   # case 3.1 : right nephew is red
                newSubRoot, siblingRightChild.color = rotateR2L(sibling), 'black'
                if not newSubRoot.parent:
                    tree.root = newSubRoot
                elif parent.color == 'red':
                    parent.color, sibling.color = 'black', 'red'
            elif not siblingLeftChild or siblingLeftChild.color == 'black':   # case 3.2 : left nephew is red
                rotateR2L(siblingRightChild)
                siblingRightChild.color, sibling.color = 'black', 'red'
                balanceBeforeDelete(tree, node, parent)
        elif siblingLeftChild and siblingLeftChild.color == 'red':
            if node == parent.rchild:  # same as case 3.1
                newSubRoot, siblingLeftChild.color = rotateL2R(sibling), 'black'
                if not newSubRoot.parent:
                    tree.root = newSubRoot
                elif parent.color == 'red':
                    parent.color, sibling.color = 'black', 'red'
            elif not siblingRightChild or siblingRightChild.color == 'black': # same as case 3.2
                rotateL2R(siblingLeftChild)
                siblingLeftChild.color, sibling.color = 'black', 'red'
                balanceBeforeDelete(tree, node, parent)
        elif parent.color == 'black':             # case 3.3 : parent is black
            sibling.color = 'red'
            if parent.parent:  # parent is not the root node
                balanceBeforeDelete(tree, parent, parent.parent)
        else:                                    # case 3.4 : parent is red
            parent.color, sibling.color = 'black', 'red'
    else:                                 # case 3.5 : sibling is red
        if node == parent.lchild:
            newSubRoot, parent.color, sibling.color = rotateR2L(sibling), 'red', 'black'
        else:
            newSubRoot, parent.color, sibling.color = rotateL2R(sibling), 'red', 'black'
        if not newSubRoot.parent:
            tree.root = newSubRoot
        balanceBeforeDelete(tree, node, parent)

總結(jié)

紅黑樹(shù)的非嚴(yán)格平衡結(jié)構(gòu)使得其查詢性能要略高于 AVL 樹(shù)锐锣，同樣因?yàn)閷?duì)高度平衡的要求較低腌闯，所以刪除和插入節(jié)點(diǎn)性能要高于 AVL 樹(shù)。其中插入節(jié)點(diǎn)和刪除節(jié)點(diǎn)需要分為多個(gè)情況進(jìn)行討論雕憔，插入新節(jié)點(diǎn)最多需要兩次旋轉(zhuǎn)操作即可達(dá)到平衡狀態(tài)姿骏，刪除節(jié)點(diǎn)最多三次旋轉(zhuǎn)即可恢復(fù)平衡。

附上一個(gè)數(shù)據(jù)結(jié)構(gòu)可視化網(wǎng)站斤彼，可以更直觀的觀察各種數(shù)據(jù)結(jié)構(gòu)的調(diào)整過(guò)程：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

代碼附錄

# tree node definition
class Node(object):
    def __init__(self, value, color = 'red', lchild = None, rchild = None, parent = None):
        self.lchild = lchild
        self.rchild = rchild
        self.parent = parent
        self.color = color
        self.value = value


# tree definition
class Tree(object):
    def __init__(self, root = None):
        self.root = root

    # node in-order traversal(LDR)
    def traversal(self):
        traversal(self.root)

    # insert node
    def insert(self, value):
        targetNode = findTargetNode(self.root, value)  # find the position
        if not targetNode:  # means the tree is none, case 1
            self.root = Node(value, color = 'black')
        else:
            node = insert(targetNode, value)  # insert the node
            adjustment(self, node) if node else None  # adjust the tree

    # delete node
    def delete(self, value):
        targetNode = findTargetNode(self.root, value)  # find the position
        if not targetNode:  # the value does not exist
            return
        if targetNode.lchild and targetNode.rchild:  # the node has two child nodes
            targetNode = transferDeleteNode(targetNode)
        delete(self, targetNode)


# node in-order traversal(LDR)
def traversal(node):
    if not node:
        return
    traversal(node.lchild)
    print(node.value, node.color, end = ' , ')
    traversal(node.rchild)


# find the right position according to value
def findTargetNode(node, value):
    target = node
    while node:
        if value < node.value:
            target, node = node, node.lchild
        elif value > node.value:
            target, node = node, node.rchild
        else:
            return node
    return target


# insert the child node
def insert(targetNode, value):
    if value < targetNode.value:
        targetNode.lchild = Node(value, parent = targetNode)
        return targetNode.lchild
    if value > targetNode.value:
        targetNode.rchild = Node(value, parent = targetNode)
        return targetNode.rchild


# change node color or rotate the subtree
def adjustment(tree, node):
    if not node.parent:  # case 1 : the node is the root node
        node.color = 'black'
    elif node.parent.color == 'black':  # case 2 : parent node is black
        pass
    else:  # parent node's color is red
        uncle = uncleNode(node)
        if uncle and uncle.color == 'red':  # case 3 : uncle node is red
            uncle.color, node.parent.color, uncle.parent.color = 'black', 'black', 'red'
            adjustment(tree, uncle.parent)
        else:  # uncle node does not exists or color is black
            rotationType, colorChange = rotationDetection(node)
            parent, grantParent = node.parent, node.parent.parent
            if colorChange: # case 4 : rotate and change color
                if rotationType == 'L2R':
                    node = rotateL2R(node.parent)
                elif rotationType == 'R2L':
                    node = rotateR2L(node.parent)
                parent.color,grantParent.color = 'black','red'
                if not node.parent:
                    tree.root = node
            else:  # case 5 : just rotate
                if rotationType == 'L2R':
                    node = rotateL2R(node).rchild
                elif rotationType == 'R2L':
                    node = rotateR2L(node).lchild
                adjustment(tree,node)



# get the uncle node
def uncleNode(node):
    grandParent = node.parent.parent
    return grandParent.rchild if node.parent == grandParent.lchild else grandParent.lchild


# confirm the rotation type is L2R or R2L, and whether needs to change the node color
def rotationDetection(node):
    parent, grandParent = node.parent, node.parent.parent
    if node == parent.lchild and parent == grandParent.lchild:
        return 'L2R', True
    if node == parent.rchild and parent == grandParent.rchild:
        return 'R2L', True
    if node == parent.lchild and parent == grandParent.rchild:
        return 'L2R', False
    if node == parent.rchild and parent == grandParent.lchild:
        return 'R2L', False


# rotate from left to right
def rotateL2R(node):
    parent, rchild = node.parent, node.rchild
    node.rchild, node.parent = parent, parent.parent  # regulate the node
    parent.parent, parent.lchild = node, rchild  # regulate the parent node
    if rchild:  # regulate the right child if not null
        rchild.parent = parent
    afterRotate(node, parent) # adjust the relationship between the node and it's new parent
    return node


# rotate from right to left
def rotateR2L(node):
    parent, lchild = node.parent, node.lchild
    node.lchild, node.parent = parent, parent.parent  # regulate the node
    parent.parent, parent.rchild = node, lchild  # regulate the parent node
    if lchild:  # regulate the left child if not null
        lchild.parent = parent
    afterRotate(node, parent) # adjust the relationship between the node and it's new parent
    return node

def afterRotate(node, parent):
    grantParent = node.parent
    if grantParent and parent == grantParent.lchild:
        grantParent.lchild = node
    elif grantParent and parent == grantParent.rchild:
        grantParent.rchild = node

# find the biggest node in the left subtree
def transferDeleteNode(node):
    target = node.lchild
    while target.rchild:
        target = target.rchild
    node.value, target.value = target.value, node.value
    return target


# balance the tree before delete the node
def balanceBeforeDelete(tree, node, parent):
    sibling = parent.rchild if node == parent.lchild else parent.lchild
    if sibling.color == 'black':
        siblingLeftChild, siblingRightChild = sibling.lchild, sibling.rchild
        if siblingRightChild and siblingRightChild.color == 'red':
            if node == parent.lchild:   # case 3.1 : right nephew is red
                newSubRoot, siblingRightChild.color = rotateR2L(sibling), 'black'
                if not newSubRoot.parent:
                    tree.root = newSubRoot
                elif parent.color == 'red':
                    parent.color, sibling.color = 'black', 'red'
            elif not siblingLeftChild or siblingLeftChild.color == 'black':   # case 3.2 : left nephew is red
                rotateR2L(siblingRightChild)
                siblingRightChild.color, sibling.color = 'black', 'red'
                balanceBeforeDelete(tree, node, parent)
        elif siblingLeftChild and siblingLeftChild.color == 'red':
            if node == parent.rchild:  # same as case 3.1
                newSubRoot, siblingLeftChild.color = rotateL2R(sibling), 'black'
                if not newSubRoot.parent:
                    tree.root = newSubRoot
                elif parent.color == 'red':
                    parent.color, sibling.color = 'black', 'red'
            elif not siblingRightChild or siblingRightChild.color == 'black': # same as case 3.2
                rotateL2R(siblingLeftChild)
                siblingLeftChild.color, sibling.color = 'black', 'red'
                balanceBeforeDelete(tree, node, parent)
        elif parent.color == 'black':             # case 3.3 : parent is black
            sibling.color = 'red'
            if parent.parent:  # parent is not the root node
                balanceBeforeDelete(tree, parent, parent.parent)
        else:                                    # case 3.4 : parent is red
            parent.color, sibling.color = 'black', 'red'
    else:                                 # case 3.5 : sibling is red
        if node == parent.lchild:
            newSubRoot, parent.color, sibling.color = rotateR2L(sibling), 'red', 'black'
        else:
            newSubRoot, parent.color, sibling.color = rotateL2R(sibling), 'red', 'black'
        if not newSubRoot.parent:
            tree.root = newSubRoot
        balanceBeforeDelete(tree, node, parent)


# delete node
def delete(tree, node):
    if node.color == 'red':  # case 1 : the node color is red
        if node == node.parent.lchild:
            node.parent.lchild = None
        else:
            node.parent.rchild = None
    else:
        parent, child = node.parent, node.lchild if node.lchild else node.rchild
        if not parent:  # the node is the root node
            tree.root = child
        if child:   # case 2 : the node is black with one red child
            if parent: # the node is not the root node
                if node == parent.lchild:
                    parent.lchild = child
                else:
                    parent.rchild = child
            child.color, child.parent = 'black', parent
        else: # case 3 : the node is black with no child
            if parent: # the node is not the root node
                balanceBeforeDelete(tree, node, parent)
                if node == parent.lchild:
                    parent.lchild = None
                else:
                    parent.rchild = None

測(cè)試代碼及輸出

if __name__ == '__main__':
    arr = [5, 3, 4, 0, 2, 1, 8, 6, 9, 7]
    T = Tree()
    print('\ninsert test------------------')
    for i in arr:
        print('after insert', i, end = ',BST in-order is = ')
        T.insert(i)
        T.traversal()
        print()

    print('\ndelete test------------------')
    for i in arr:
        print('after delete', i, end = ',BST in-order is = ')
        T.delete(i)
        T.traversal()
        print()

輸出為：

insert test------------------
after insert 5,BST in-order is = 5 black , 
after insert 3,BST in-order is = 3 red , 5 black , 
after insert 4,BST in-order is = 3 red , 4 black , 5 red , 
after insert 0,BST in-order is = 0 red , 3 black , 4 black , 5 black , 
after insert 2,BST in-order is = 0 red , 2 black , 3 red , 4 black , 5 black , 
after insert 1,BST in-order is = 0 black , 1 red , 2 red , 3 black , 4 black , 5 black , 
after insert 8,BST in-order is = 0 black , 1 red , 2 red , 3 black , 4 black , 5 black , 8 red , 
after insert 6,BST in-order is = 0 black , 1 red , 2 red , 3 black , 4 black , 5 red , 6 black , 8 red , 
after insert 9,BST in-order is = 0 black , 1 red , 2 red , 3 black , 4 black , 5 black , 6 red , 8 black , 9 red , 
after insert 7,BST in-order is = 0 black , 1 red , 2 red , 3 black , 4 black , 5 black , 6 red , 7 red , 8 black , 9 red , 

delete test------------------
after delete 5,BST in-order is = 0 black , 1 red , 2 red , 3 black , 4 black , 6 black , 7 red , 8 red , 9 black , 
after delete 3,BST in-order is = 0 black , 1 red , 2 black , 4 black , 6 black , 7 red , 8 red , 9 black , 
after delete 4,BST in-order is = 0 red , 1 black , 2 black , 6 black , 7 red , 8 red , 9 black , 
after delete 0,BST in-order is = 1 black , 2 black , 6 black , 7 red , 8 red , 9 black , 
after delete 2,BST in-order is = 1 black , 6 red , 7 black , 8 black , 9 black , 
after delete 1,BST in-order is = 6 black , 7 red , 8 black , 9 black , 
after delete 8,BST in-order is = 6 black , 7 black , 9 black , 
after delete 6,BST in-order is = 7 black , 9 red , 
after delete 9,BST in-order is = 7 black , 
after delete 7,BST in-order is =

github 鏈接：紅黑樹(shù)

最后編輯于：2018.10.29 09:56:37

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末工腋，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子畅卓，更是在濱河造成了極大的恐慌擅腰，老刑警劉巖，帶你破解...
沈念sama閱讀 206,126評(píng)論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件翁潘，死亡現(xiàn)場(chǎng)離奇詭異趁冈，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)拜马，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,254評(píng)論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)渗勘，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人俩莽，你說(shuō)我怎么就攤上這事旺坠。” “怎么了扮超？”我有些...
開(kāi)封第一講書(shū)人閱讀 152,445評(píng)論 0贊 341
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵取刃，是天一觀的道長(zhǎng)蹋肮。經(jīng)常有香客問(wèn)我，道長(zhǎng)璧疗，這世上最難降的妖魔是什么坯辩？我笑而不...
開(kāi)封第一講書(shū)人閱讀 55,185評(píng)論 1贊 278
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮崩侠，結(jié)果婚禮上漆魔，老公的妹妹穿的比我還像新娘。我一直安慰自己却音，他們只是感情好改抡，可當(dāng)我...
茶點(diǎn)故事閱讀 64,178評(píng)論 5贊 371
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布。她就那樣靜靜地躺著系瓢，像睡著了一般阿纤。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上八拱，一...
開(kāi)封第一講書(shū)人閱讀 48,970評(píng)論 1贊 284
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音涯塔，去河邊找鬼肌稻。笑死，一個(gè)胖子當(dāng)著我的面吹牛匕荸，可吹牛的內(nèi)容都是我干的爹谭。我是一名探鬼主播，決...
沈念sama閱讀 38,276評(píng)論 3贊 399
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼榛搔，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼诺凡！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起践惑，我...
開(kāi)封第一講書(shū)人閱讀 36,927評(píng)論 0贊 259
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤腹泌，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后尔觉，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體凉袱，經(jīng)...
沈念sama閱讀 43,400評(píng)論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 35,883評(píng)論 2贊 323
?白月光啟示錄
正文我和宋清朗相戀三年侦铜，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了专甩。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 37,997評(píng)論 1贊 333
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡涤躲，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出贡未，到底是詐尸還是另有隱情，我是刑警寧澤矫限，帶...
沈念sama閱讀 33,646評(píng)論 4贊 322
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布无宿，位于F島的核電站奥洼，受9級(jí)特大地震影響骡尽，放射性物質(zhì)發(fā)生泄漏沙咏。R本人自食惡果不足惜辨图，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,213評(píng)論 3贊 307
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望肢藐。院中可真熱鬧故河，春花似錦、人聲如沸吆豹。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 30,204評(píng)論 0贊 19
一樁弒父案理盆，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至凑阶，卻和暖如春猿规，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背宙橱。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 31,423評(píng)論 1贊 260
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工姨俩，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人师郑。一個(gè)月前我還...
沈念sama閱讀 45,423評(píng)論 2贊 352
代替公主和親
正文我出身青樓环葵，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親宝冕。傳聞我的和親對(duì)象是個(gè)殘疾皇子张遭，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,722評(píng)論 2贊 345