红黑树(Red-Black-Tree) 是一种比较常用的树形数据结构, 它的综合性能比较优秀, 因此在业界有广泛的应用, 在 Linux Kernel 中有多处使用了 RbTree, Kernel 对于 RbTree 的实现代码位于 linux/lib/rbtree.c, 红黑树相比于 AVL 树, 它对平衡的要求并不严苛, 尽管查找性能可能略逊色于 AVL 树, 但相比 AVL 树, 红黑树在插入/删除结点时不需要做太多次调整, 因此如果应用场景不是以查询为主的话, 使用红黑树将比 AVL 树获得更好的性能, 本文完整讨论红黑树的实现, 并给出详细的 Go 代码, 使用 Go 的简易之处在于结点内存的释放可以全部丢给 GC 去做, 而将我们的精力更集中地放在实现红黑树自身的逻辑上

6.1 红黑树的定义

红黑树是一种自平衡的二叉查找树, 类似于 AVL 树, 但移除了 AVL 树对任意结点的左右子树高度之差不能超过 1 这个严苛的限制, 具体来说, 红黑树需要满足如下 5 条规则:

1. 树中的任何一个结点都带有颜色, 每个结点的颜色要么是红色, 要么是黑色
2. 根结点是黑色
3. 所有叶子结点是黑色(在红黑树中, 我们将底层叶结点看做有两个值为 NULL 的孩子结点, 以 NULL 结点作为红黑树的叶结点)
4. 每个红色结点的孩子结点一定是黑色
5. 对于树中的任意一个结点, 从该结点到所有叶结点的路径上一定包含相同数量的黑结点(我们将红黑树任意结点到叶子结点的路径上的黑色结点的个数称为该结点的 「黑高」)

分析上面的规则, 我们可以知道, 在红黑树中, 一定不会出现两个红色结点连在一起的情况(规则 4), 结合规则 5, 可以知道对于任意红黑树来说, 在最坏情况下, 其左右子树的高度差正好差一倍, 这时其一半子树正好是红黑相间的状态, 基于以上 5 条基本规则, 我们可以推理演绎出更多的推论, 这些结论在我们真正实现红黑树时会用到:

1. 如果一个结点是红色, 那么可以它的父结点一定是黑色(规则 4 的逆否命题)
2. 如果一个结点存在黑色子结点, 那么它一定有两个孩子结点(规则 5 的逆否命题)

6.2 红黑树的搜索与更新

红黑树隶属于二叉搜索树, 因此搜索红黑树与搜索普通的二叉查找树并无任何差别, 对于查找与更新操作, 这里不再赘述

6.3 数据结构定义

为了能具体地讨论红黑树的实现, 我们不单纯地用自然语言表述整个过程, 而是结合具体的代码来展现红黑树的操作, 首先给出红黑树的结构定义, 因为这里只是为了讨论红黑树的数据结构与算法, 所以我们不将代码写的特别通用, 我们假定所有结点的值都是整型的

// 红黑树结点结构定义
typedef Node struct {
    Left *Node // 左孩子结点
    Right *Node // 右孩子结点
    Parent *Node // 父结点
    Color color // 结点的颜色
    Value int // 结点值
}

// 红黑树定义
typedef RbTree struct {
    Root *Node // 根结点
    Leaf *Node // 叶结点, 叶结点没有值, 按照规则 2, 它的颜色是黑色
}

6.4 左旋与右旋

同 AVL 树一样, 红黑树在调整的时候也是采用旋转的方式, 根据旋转方式的不同的, 可以分为左旋和右旋, 以右旋为例, 右旋实际上是将结点的左孩子作为新的根结点, 将左孩子结点的右孩子结点作为原根结点的左孩子结点, 这样既完成了旋转, 也不会破坏二叉排序树的性质(二叉搜索树一定是二叉排序树, 所谓二叉排序树是若左孩子结点不为空, 则左子树的所有值均小于父结点, 若右子树不为空, 则右子树的所有结点值均大于父结点, 当然倒过来也可以, 对排序树做先序遍历则正好得到一个从小到大的序列), 右旋的算法用自然语言描述是(我们说 A 成为 B 的孩子结点, 意味着需要改两处指针, B 的孩子指针指向 A, A 的父亲指针指向 B)

1. 如果结点没有左孩子结点, 算法结束
2. 如果结点没有父结点(说明其原先就是红黑树的根结点), 则其左孩子结点为新的根结点; 否则, 判断结点是其父结点的左孩子还是右孩子, 若是左孩子, 则结点的左孩子结点成为其父亲的左孩子结点, 否则, 结点的左孩子结点成为其父亲的右孩子结点
3. 结点的左孩子结点的右孩子结点成为结点的左孩子结点

代码实现如下:

 // 以红黑树的结点 n 为支点进行右旋
 func (r *RbTree) RightRotate(n *Node) {
     // 如果结点没有左孩子, 那么直接退出
     if n.Left == r.Leaf {
         return
     }
     // Step I. 处理结点 n 的父结点
     if n.Parent == r.Leaf {
        r.Root = n.Left
     } else if n.Parent.Left == n { // n 是其父结点的左孩子
        n.Parent.Left = n.Left
        n.Left.Parent = n.Parent
     } else if n.Parent.Right == n { // n 是其父结点的右孩子
        n.Parent.Right = n.Left
        n.Left.Parent = n.Parent
     }

     // Step II. 将结点 n 的左孩子的右孩子移动为自己的左孩子
     newParent := n.Left
     n.Left = n.Left.Right
     if n.Left != r.Leaf {
        n.Left.Parent = n
     }

     // Step III. 将结点 n 移动为其左孩子的右孩子结点
     newParent.Right = n
     n.Parent = newParent
 }

图示如下:

左旋与右旋逻辑完全相同, 只是方向不同, 这里不再赘述

6.5 红黑树的插入

红黑树插入的第一阶段与普通的二叉搜索树插入过程完全相同, 都是根据新插入结点的值遍历二叉搜索树找到所要插入的位置, 然后将新结点挂到父结点上, 代码实现如下所示

func(r *RbTree) Insert(n *Node) {
    // current 为遍历指针, 指向当前遍历到的结点
    current := r.Root 
    // stopAt 用于指示遍历过程经过的最后一个结点
    // 之所以要设置 stopAt 是因为红黑树结点需要记录下其父亲的结点
    // 换句话说我们不仅需要知道应该插入到哪个位置上, 还需要知道插入位置的父结点
    stopAt := r.Leaf 
    for current != r.Leaf {
        stopAt = current
        // 要插入结点的值比当前结点的值大, 则继续去当前结点的右子树搜索
        if current.Value < n.Value {
            current = current.Right
        } else if current.Value > n.Value { // 否则去左子树搜索
            current = current.Left
        } else { // 已经有了就不插入了, 本文只是为了讨论红黑树算法, 我们认为所有结点的值都是不相同的
            return
        }
    }

    // stopAt 即为新插入结点的父结点
    n.Parent = stopAt
    // 如果红黑树原先是空的, 那么新插入的结点是红黑树的根结点
    if stopAt == r.Leaf {
        r.Root = n
    } else if n.Value < stopAt.Value { // 新插入的结点的值比其父亲小, 作为其父亲的左孩子结点
        stopAt.Left = n
    } else { // 否则, 作为其右孩子结点
        stopAt.Right = n
    }

    // 对插入的结点做调整, 使整棵树仍然满足红黑树的 5 条规则
    // 具体算法将在下面详细展开讨论
    InsertFixup(n)
}

红黑树需要满足 6.1 所述的 5 条规则, 当插入新结点后, 可能会使得红黑树的某些规则被破坏, 这时需要对树做一定的调整, 使其仍然遵循红黑树的规则, 首先的一个问题是新插入的结点, 颜色如何确定, 理论上来说, 无论是红色和黑色都是可以的, 但是红黑树中的规则中, 每个结点到任意一个可达的叶子结点的黑结点数目都是相同的, 如果我们将插入的结点颜色设定为黑色, 那么插入操作执行完毕以后, 一定会破坏红黑树的规则, 新插入的结点会使得其所在的子树的结点黑高都增加一, 这一方面会给写代码带来不必要的麻烦, 更重要的是每次插入 「必定」 需要对树做调整, 这会影响红黑树的性能, 因此无论是从代码开发的角度来讲, 还是从红黑树性能的角度来讲, 插入结点的颜色都不应该选择黑色

基于以上的考虑, 新插入的结点我们都规定为红色, 根据原红黑树状态的不同, 插入操作分为以下几种情况(我们以下所有的讨论都假定新插入的结点的父结点是其爷爷结点的的左孩子结点, 反过来同理, 逻辑都一样, 只是方向相反, 不再赘述)

情况 I: 新插入结点的父结点是黑色

这是最简单的一种情形, 新插入的结点是红色, 并且其父结点是黑色的, 在这种情况下不需要做任何调整, 首先新插入的结点是红色的, 所以不会对任何现有结点的黑高产生影响, 其次, 因为父结点是黑色的, 所以放入新的红色结点不会破坏红黑树的规则

对于情况 I, 我们只需执行 Insert 函数即可完成整个插入过程, 不需要再做额外的调整

情况II: 新插入结点的父结点为红色, 叔叔结点(即父结点的兄弟结点)也为红色(根据规则 4 可以推得, 爷爷结点一定为黑色)

对于情况II. 新插入的结点是红色, 其父结点也是红色, 两个红色结点相邻, 违背了规则 4, 所以需要进行调整, 对于情况 II, 我们不需要对树进行旋转操作, 而只需简单的变色, 即可将树重新调整为正常的红黑树, 具体的调整逻辑为:

1. 将新插入结点的父结点的颜色改为黑色
2. 将新插入结点的叔叔结点的颜色改为黑色
3. 将新插入结点的爷爷结点的颜色改为红色

这样以来, 两边的黑高都没有发生变化, 并且也解决了新插入结点与其父结点都是红色这个问题, 但是由于我们将爷爷结点由红色改为了黑色, 所以可能使得爷爷结点与上面的结点不满足红黑树的规则, 因此之后需要递归地调整上面的结点, 图示如下:

代码描述如下:

uncle := n.Parent.Parent.Right
// 情形I. 新插入结点的父亲和叔叔都是红色, 爷爷结点是黑色, 此时将父亲和叔叔改为黑色, 爷爷改为红色, 即可处理完局部区域
// 父亲和父亲的兄弟都是红色(自然也有爷爷结点是黑色), 这时只需将父结点和兄弟结点变为黑色, 爷爷结点变为红色
if uncle.Color == RED {
    uncle.Color = BLACK
    n.Parent.Color = BLACK
    n.Parent.Parent.Color = BLACK
    n = n.Parent.Parent // 将爷爷结点由黑变红, 可能会使得上面的树变得不满足红黑树的性质, 需要向上递归地进行调整
}

情况 III: 新插入结点的父结点为红色, 叔叔结点为黑色(自然可以推得爷爷结点为黑色, 否则其父亲结点不可能为红色), 并且新插入的结点是其父结点的右孩子结点

对于这种情形, 需要对树做旋转, 转化为情形 IV(将在下面讨论), 然后按照情形 IV 的方式进行处理, 使用一个图示来形象地说明

图中的 P 结点即为新插入结点的父结点, 代码描述如下:

if n.Parent.Right == n { // 新插入结点是红色父亲结点的右子结点, 需要以父结点为支点, 进行一次左旋操作
    n = n.Parent
    r.LeftRotate(n)
    // 左旋完成之后, 树的当前形态如下:
    //
    //                  黑
    //                /    \
    //              红      黑
    //            /
    //          红
    //
    // n 目前指向最左下角的红结点, 它的父结点为红色, 父结点的兄弟结点为黑色
}

情况 IV: 新插入结点的父结点为红色, 并且其叔叔结点为黑色

情况 IV 是插入操作的最后一种情形, 需要通过变色和旋转两种调整方式来使树重新满足红黑树的 5 条规则, 首先由于新插入的结点是红色, 其父结点也是红色, 所以我们将父结点的颜色变为黑色, 父结点的颜色变为黑色以后, 从其爷爷结点及往上的结点的黑高都增加了一, 所以我们将爷爷结点的颜色变为红色, 以抵消将父结点的颜色由红变黑而使黑高增加的一, 调整完父亲结点和爷爷结点的颜色以后, 颜色问题都解决了, 此时整棵树没有两个紧靠在一起的红色, 但是刚刚的一番调整由于将爷爷结点由黑色变为红色, 这会使得爷爷结点的右子树的黑高减少了一, 这时我们需要对树做右旋操作, 以弥补右子树减少的黑高, 将这两个阶段用图示来形象地说明:

Step I, 由于新插入结点的颜色与其父结点的颜色都是红色, 所以我们将父结点颜色改为黑色, 但是增加了一个黑结点会使得爷爷结点的黑高增加一, 所以我们将爷爷结点的颜色变为红色

Step II, 第一步的调整没有改变左子树的黑高, 也解决了两个红色相邻的问题, 但由于爷爷结点由红变黑, 所以右子树的黑高少了一, 我们以爷爷为支点做右旋操作, 相当于将 P 结点移到了原爷爷结点的位置上, 这样正好弥补了右子树减少的一个黑结点, 同时左子树的黑高也不会产生任何影响, 至此调整完毕

代码描述如下:

// 情形IV. 父亲为红色, 叔叔为黑色, 新插入的结点为父亲的左子结点
// 将父亲转换为黑色, 但这样会使得经过 父亲-孩子 路径上的黑高增加1, 于是再将爷爷变为红色(爷爷之前一定是黑色, 如果是红色, 它的孩子不能有红色), 之后再进行一次右旋
// 右旋是因为爷爷结点由黑色变为红色, 使得右子树的黑高少了1, 右旋后会使得父结点成为新的右子树的祖先, 弥补回来
n.Parent.Color = BLACK
n.Parent.Parent.Color = RED
r.RightRotate(n.Parent.Parent)

以上我们的分析都是建立在 【新插入的结点的父结点是其爷爷结点的左孩子】 来进行的, 当新插入结点的父结点是其爷爷结点的右孩子时, 处理逻辑一致, 只是旋转方向相反, 这里不再展开讨论, 插入操作虽然有这么多种情形, 但梳理一下会发现其实并不难理解, 这里我们将情况 I ~ IV 合并在一起做一个简短的总结, 便于读者更清晰地了解红黑树的插入过程

1. 新插入结点的父亲是黑色, 直接插入, 无需调整, 因为新插入结点是红色, 红色与黑色靠在一起不会破坏红黑树的规则, 并且因为新插入的结点是红色, 没有对树的黑高产生任何影响, 所以插入后无需调整

2. 新插入结点的父亲是红色

   1. 新插入结点的父亲是红色, 其叔叔结点(父结点的兄弟结点)也是红色。进而我们分析得出其爷爷结点一定是黑色, 对于这种情况, 我们将父结点和兄弟结点的颜色都变为黑色, 将爷爷结点的颜色变为红色, 这样对当前的局部区域来说, 既解决了颜色冲突的问题, 也没有影响黑高, 但由于爷爷结点由黑色变为了红色, 可能使得爷爷结点与爷爷结点的父结点颜色发生冲突, 因此需要递归地向上调整
   2. 新插入结点的父亲是红色, 其叔叔结点是黑色, 进而我们分析得出其爷爷结点一定是黑色, 对于这种情形, 我们进一步划分为两种情形
      1. 新插入的结点是其父亲的右孩子. 对于这种情况, 我们需要以新插入结点的父结点为支点做左旋操作, 然后转化为下面的情况 2 进行处理
      2. 新插入的结点是其父结点的左孩子, 对于这种情况, 我们首先将父结点的颜色由红色变为黑色, 这样会使左子树的黑高增加一, 所以我们继续将爷爷结点的颜色由黑色变为红色, 以抵消多出来的黑结点, 但爷爷结点由黑色变为红色以后, 同时会使得爷爷结点的右子树少了一个黑结点, 我们以新插入结点的父结点为支点, 做右旋操作, 这样会使得新插入结点的父结点成为新的爷爷结点, 以弥补右子树黑高减少的一, 同时也不会影响左子树的黑高, 至此插入过程调整完毕

6.6 红黑树的删除

红黑树的删除相比于插入需要处理的情形相对更多一些, 与插入操作类似, 红黑树的删除首先也是与普通的二叉搜索树一样删除结点, 但结点删除以后可能使得删除后的树结构不再满足红黑树的 5 条规则, 因而需要进行调整(旋转或变色)

删除结点的第一步, 需要搜索到所要删除的目标结点, 这与对普通的二叉搜索树进行删除并无任何差别, 代码如下:

// 在红黑树中搜索指定结点, 返回结点的指针
// 红黑树的搜索与普通二叉搜索树的没有任何不同之处
func (r *RbTree) Search(n *Node) *Node {
    current := r.Root
    for current != r.Leaf {
        if n.Value < current.Value { // 待查找的结点的值比当前结点值小, 应继续在左子树中搜索
            current = current.Left
        } else if n.Value > current.Value { // 待查找的结点的值比当前结点的值大, 应继续在右子树中搜索
            current = current.Right
        } else {
            return current
        }
    }
    return r.Leaf
}

与普通的二叉排序树的删除相同, 若要删除的结点有两个孩子, 则我们将其左子树的最大结点或右子树的最小结点复制到所要删除的结点上, 然后删除左子树的最大结点或右子树的最小结点, 这样以来, 我们所删除的结点至多有一个孩子结点

对于红黑树来说, 结点有两种颜色, 红黑树的重要性质是要保证每个结点到所有可达叶结点路径上的黑结点数目是相等的, 如果所要删除的结点是红色结点, 那么删除后不会对黑高产生任何影响, 可以直接删除, 而若删除的结点是黑结点, 则需要根据情况做一定的调整工作, 我们先给出删除红黑树结点的函数代码

// 删除红黑树的结点
// 执行删除操作后可能会使得结构不再满足红黑树的 5 条规则
// 需要调用 DeleteFixup 函数对删除结点后的树进行修正
func (r *RbTree) Delete(n *Node) {
    // 删除操作的第一步, 应调用搜索函数, 找到待删除的结点
    currentNode := r.Search(n)
    if currentNode == r.Leaf { // 要删除的结点不存在, 删除操作结束
        return
    }

    // 要删除的结点如果有两个孩子结点, 那么我们将其后继结点(即右子树的最小结点)补到它的位置上, 然后将后继结点删掉
    // 这样我们所操作的删除对象都是至多只有一个孩子的结点
    // 将结点删除后, 我们将结点的孩子传递给它的父亲, 然后将它从红黑树中移除
    // 因此先记录下它的孩子, 特别地, 它可能没有孩子, 但是我们仍然可以将它的 Leaf 结点看做孩子传递给它的父亲
    var willDeleteNode *Node
    if currentNode.Left == r.Leaf || currentNode.Right == r.Leaf {
        willDeleteNode = currentNode // 如果当前结点不是有两个孩子的结点, 那么当前结点就是要删除的结点
    } else { // 否则我们在当前结点的右子树找最小结点删除
        willDeleteNode = r.GetNextNode(willDeleteNode)
        currentNode.Item = willDeleteNode.Item
    }

    // 找到孩子结点
    var child *Node
    if willDeleteNode.Left != r.Leaf {
        child = willDeleteNode.Left
    } else if willDeleteNode.Right != r.Leaf {
        child = willDeleteNode.Right
    } else {
        child = r.Leaf
    }

    // 将孩子结点传递给它的父亲
    child.Parent = willDeleteNode.Parent
    if willDeleteNode.Parent == r.Leaf {
        r.Root = child
    } else if willDeleteNode.Parent.Left == willDeleteNode {
        willDeleteNode.Parent.Left = child
    } else {
        willDeleteNode.Parent.Right = child
    }

    // 如果删除的是红结点, 那么所有结点的黑高都不会影响, 删除操作是完全无害的, 无需调整
    // 如果删除的是黑结点, 那么经过删除结点的路径的黑高都减了一, 需要对树进行调整
    if willDeleteNode.Color == BLACK {
        r.DeleteFixup(child)
    }

    return
}

确定所要删除的结点后, 我们将这个结点的孩子结点(至多会有一个)连接到被删除结点的父结点上, 然后需要根据情况对树做调整, 我们将被删除结点的孩子结点记为 N, 接下来便是要对 N 做调整, 与红黑树的插入类似, 由于对称性, 我们只分析一半情况即可, 以下我们所讨论的都是 【假定 N 是其父结点的左孩子】, 反过来逻辑完全相同, 只是旋转方向不同, 不再赘述

情况I: N 是红色结点

情况 I 是所有情形中最简单的一种, 由于 N 是红色结点, 被删掉的结点是黑色结点, 所以用 N 替代被删除结点之后, 只需将 N 结点的颜色变为黑色即可

情况II: N 是黑色结点, N 的兄弟结点是红色(进而 N 的父亲结点一定黑色, 并且如果 N 的兄弟结点有孩子结点, 则孩子结点一定都是黑色的)

这种情况下, 我们对树做变色和旋转操作, 将其转换为情况 III(将在下面讨论), 首先我们将 N 的兄弟结点由红色变为黑色, 然后将 N 的父亲结点由黑色变为红色, 接着我们以 N 的父亲结点为支点, 进行左旋操作, 整个过程如下所示:

代码描述如下:

brother := n.Parent.Right
// 如果其兄弟结点为红色, 则其父亲一定是黑色, 并且兄弟结点的孩子(如果有)一定都是黑色
//
//                                                            黑
//                                                          /
//                  黑                   红               红
//                /    \        ==>    /   \      ==>  /   \
//              黑      红            黑     黑        黑     黑
//                     /                   /
//                   黑                   黑
//
if brother.Color == RED {
    brother.Color = BLACK
    n.Parent.Color = RED
    r.LeftRotate(n.Parent)
    brother = n.Parent.Right // 左旋之后, 原先的 brother 结点已经是其父结点了, 重新指向新的兄弟结点
}

情况 III: N 是黑色结点, N 的兄弟结点是黑色结点(由于 N 的兄弟结点是黑色, 所以兄弟结点的孩子结点的颜色是不确定的), N 的兄弟结点的孩子结点(如果有)都是黑色

对于情况 III, 由于 N 的兄弟结点两个孩子(如果有)都是黑色, 换句话说, N 的兄弟结点没有颜色为红色的孩子结点, 因此我们可以自由地对 N 的兄弟结点的颜色做变换, 由于左子树删除导致少了一个黑结点, 那么我们将 N 的兄弟结点的颜色也改为红色, 这样右子树也减少了一个黑结点, 对于以 N 的父结点为根结点的子树来说, 两次都减少了一个黑结点, 所以下面的子树仍然是平衡的, 但经过 N 的父结点的结点的黑高都减少了一, 因此需要递归地向上继续调整, 情况 III 的图示如下:

情况 IV: N 是黑色结点, N 的兄弟结点也是黑色, 而 N 的兄弟结点的左孩子为红色, 右孩子为黑色

对于情况 IV, 我们首先将 N 的兄弟结点的颜色由黑色变为红色, 然后将兄弟结点的左孩子的颜色由红色变为黑色, 然后以 N 的兄弟结点为支点进行右旋操作, 将其转化为情况 V(将在下面讨论), 图示如下:

代码描述如下:

brother.Color = BLACK
brother.Left.Color = RED
r.RightRotate(brother)

情况 V: N 是黑色结点, N 的兄弟结点是黑色结点, N 的兄弟结点的左孩子为黑色, 右孩子为红色

对于情况 V, 首先我们将父结点的颜色涂到 N 的兄弟结点上(由于 N 和兄弟结点都是黑色, 所以父结点的颜色是不确定的), 然后将父结点的颜色改为黑色, 并将 N 的兄弟结点的右孩子结点由红色改为黑色, 然后我们以 N 的兄弟结点为支点进行左旋操作, 整个过程的图示如下:

我们来分析下情况 V 的操作过程, 第一步是进行变色操作, 总共调整了 3 个结点的颜色, 将 N 的父结点的颜色改为黑色, 将 N 的兄弟结点的颜色改为原父结点的颜色, 将 N 的兄弟结点的右孩子结点的颜色改为黑色, 经过这样一番变色操作后, 左子树的黑高没有发生变化, 但是右子树的黑高增加了一, 然后我们做左旋操作, 刚好将右子树增加的黑高转移到了左子树上, 正好弥补了左子树删除一个黑结点造成的黑高减一, 其实整个过程相当于从右子树 "借" 了一个黑结点过来, 代码实现如下:

brother.Color = n.Parent.Color
n.Parent.Color = BLACK
brother.Right.Color = BLACK
r.LeftRotate(n.Parent)

至此, 我们讨论完了红黑树删除操作的所有情形, 删除操作相对来说比较复杂, 现在我们对删除操作做一个简短的梳理, 便于读者更清晰地认识删除的过程

1. 要删除一个结点, 首先要搜索到这个结点, 若删除的结点有两个孩子结点, 那么我们将所要删除结点的后继结点(即该结点右子树的最小结点)的值复制到所要删除的结点的位置上(当然也可以使用其左子树的最大结点), 将问题转换为删除其后继结点, 之所以要这样做, 是因为这样可以使得所删除的结点至多只有一个孩子结点

2. 如果所删除的结点是红色的, 那么删除以后不会影响树的黑高, 不会破坏红黑树的任何规则, 直接删除即可

3. 如果删除的结点是黑色的, 则要分为以下几种子情形来讨论, 我们将被删除结点的孩子结点记为 N(如果被删除结点没有孩子结点, 则 N 为 Leaf, 它的颜色是黑色的), 我们将结点删除以后, 将结点 N 补到被删除结点的位置上, 以下子情形的讨论都 【假定 N 是其父亲的左孩子】, 反之同理, 不再赘述:

   1. 如果 N 是红色, 那么只需将红色改为黑色即可弥补删除黑色结点造成的黑高减少, 此时, 算法结束
   2. 如果 N 是黑色, 则进一步分为如下几种子情形:
      1. 如果 N 的兄弟结点为红色, 则 N 的父结点一定是黑色, 此时将父结点的颜色变为红色, 将兄弟结点的颜色变为黑色, 然后以 N 的父结点为支点进行左旋, 转化为下面的情形 2
      2. 如果 N 的兄弟结点为黑色, 则进一步分为如下几种子情形:
         1. 如果 N 的兄弟结点不存在红色孩子结点, 则只需将兄弟结点的颜色变为红色, 这样右子树的黑高也减少一, 正好与左子树因删除一个黑结点造成黑高减少一相平衡, 但对于 N 的父结点来说, 左右子树的黑高都减少了一, 因此需要对父结点递归地向上调整
         2. 如果 N 的兄弟结点的左孩子是红色, 右孩子是黑色, 则首先将 N 的兄弟结点的颜色变为红色, 将 N 的兄弟结点的左孩子结点颜色变为黑色, 然后以 N 的兄弟结点为支点进行右旋操作, 转换为如下的情况 3
         3. 如果 N 的兄弟结点的左孩子是黑色, 右孩子是红色, 则将 N 的兄弟结点的颜色涂成和 N 的父结点相同的颜色(因为 N 及其兄弟结点都是黑色, 所以它们的父结点的颜色是不确定的, 但不影响我们的调整过程), 然后将 N 的父结点的颜色涂成黑色, 将 N 的兄弟结点的右孩子颜色涂成黑色, 然后以 N 的父结点为支点进行左旋操作

至此, 对于红黑树删除的调整过程完毕

6.7 总结

红黑树是一种相对比较复杂的数据结构, 主要体现在对插入和删除结点之后, 需要对树进行调整, 使其重新满足红黑树的 5 条规则, 对于红黑树的调整使用变色和旋转即可完成, 由于红黑树对平衡的要求相比较弱, 因此相比于 AVL 树, 当插入或删除结点时, 红黑树的调整工作量在统计意义下要比 AVL 树少, 综合性能要好于 AVL 树