久久成人久久鬼色,青青青青青2019,婷婷色色五月天

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

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

紅黑樹相對于 AVL 樹，對樹的高度限制較為寬松，所以紅黑樹的查找復(fù)雜度要略遜于 AVL 樹。也因?yàn)閷涓叨鹊南拗戚^小，所以插入和刪除節(jié)點(diǎn)時需要較少的旋轉(zhuǎn)操作即可達(dá)到平衡狀態(tài)。

條件限制

紅黑樹中的節(jié)點(diǎn)存在顏色屬性，通過對節(jié)點(diǎn)顏色的限制來保持樹的平衡性。平衡的紅黑樹要求如下：

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

其中 1、2 條沒什么可說的，第 3 條中提到葉子節(jié)點(diǎn)，在紅黑樹的使用過程中使用一個特殊的節(jié)點(diǎn) $Nil$ 來表示葉子節(jié)點(diǎn)，該節(jié)點(diǎn)代表著終結(jié)條件，在算法導(dǎo)論中稱這種使用方式為哨兵模式。在后續(xù)的 python 代碼中以 $None$ 來代表該終結(jié)條件。

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

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

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

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

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

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

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

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

original	adjusted

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

若新節(jié)點(diǎn)不為根節(jié)點(diǎn)，則具有父節(jié)點(diǎn)，父節(jié)點(diǎn)顏色無外乎黑、紅兩種。當(dāng)父節(jié)點(diǎn)顏色為黑色時，此時插入新節(jié)點(diǎn)不影響紅黑樹的平衡性，所以不需要調(diào)整操作；

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

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

original	adjusted

此時無所謂新節(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)，同時父節(jié)點(diǎn) $P$ 是祖父節(jié)點(diǎn) $G$ 的左子節(jié)點(diǎn)；或者新節(jié)點(diǎn) $N$ 是其父節(jié)點(diǎn) $P$ 的右子節(jié)點(diǎn)，同時父節(jié)點(diǎn) $P$ 是祖父節(jié)點(diǎn) $G$ 的右子節(jié)點(diǎn)。

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

original	adjusted

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

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

5. 新節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色，叔父節(jié)點(diǎn)的顏色不為紅色。且新節(jié)點(diǎn) $N$ 是其父節(jié)點(diǎn) $P$ 的右子節(jié)點(diǎn)，同時父節(jié)點(diǎn) $P$ 是祖父節(jié)點(diǎn) $G$ 的左子節(jié)點(diǎn)；或者新節(jié)點(diǎn) $N$ 是其父節(jié)點(diǎn) $P$ 的左子節(jié)點(diǎn)，同時父節(jié)點(diǎn) $P$ 是祖父節(jié)點(diǎn) $G$ 的右子節(jié)點(diǎn)。

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

d1.png	d1.png

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

由插入節(jié)點(diǎn)的情形分析可知，插入節(jié)點(diǎn)時最多只會進(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)情況

二叉查找樹在進(jìn)行節(jié)點(diǎn)刪除時，若待刪除節(jié)點(diǎn)的度為 2 時，則可以將刪除操作“轉(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)并不影響二叉樹的平衡性。

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

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

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

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

簡單場景下節(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)行討論，對稱的情況下處理過程類似。

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$ 顏色不確定。此時以節(jié)點(diǎn) $S$ 為軸心執(zhí)行左旋操作，并對部分節(jié)點(diǎn)執(zhí)行顏色變換操作。

original	adjusted

左旋操作后，變換 $S_r$ 節(jié)點(diǎn)顏色。若 $P$ 節(jié)點(diǎn)為紅色，則左旋操作后，對 $P$ 節(jié)點(diǎn)和 $S$ 節(jié)點(diǎn)進(jìn)行顏色變換。此時刪除節(jié)點(diǎn) $N$ 之后，通過其他節(jié)點(diǎn)的路徑上黑色節(jié)點(diǎn)個數(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)不存在或存在為黑色。此時以節(jié)點(diǎn) $S_l$ 為軸心執(zhí)行右旋操作，并對 $S$ 和 $S_l$ 節(jié)點(diǎn)執(zhí)行顏色變換操作。

original	adjusted

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

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

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

original	adjusted

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

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

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

original	adjusted

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

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

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

original	adjusted

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

節(jié)點(diǎn)刪除的所有情況如上，由各個情形描述可知，節(jié)點(diǎn)刪除最多經(jīng)過三次旋轉(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é)

紅黑樹的非嚴(yán)格平衡結(jié)構(gòu)使得其查詢性能要略高于 AVL 樹，同樣因?yàn)閷Ω叨绕胶獾囊筝^低，所以刪除和插入節(jié)點(diǎn)性能要高于 AVL 樹。其中插入節(jié)點(diǎn)和刪除節(jié)點(diǎn)需要分為多個情況進(jìn)行討論，插入新節(jié)點(diǎn)最多需要兩次旋轉(zhuǎn)操作即可達(dá)到平衡狀態(tài)，刪除節(jié)點(diǎn)最多三次旋轉(zhuǎn)即可恢復(fù)平衡。

附上一個數(shù)據(jù)結(jié)構(gòu)可視化網(wǎng)站，可以更直觀的觀察各種數(shù)據(jù)結(jié)構(gòu)的調(diào)整過程：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

測試代碼及輸出

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 鏈接：紅黑樹

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

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

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

條件限制

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

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

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

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

預(yù)平衡代碼

總結(jié)

代碼附錄

測試代碼及輸出

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

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

條件限制

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

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

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

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

預(yù)平衡代碼

總結(jié)

代碼附錄

測試代碼及輸出

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av