> 科技资讯 > 红黑树是怎么来的

红黑树是怎么来的

科技资讯 投稿 9000℃ 0 评论

红黑树是怎么来的

平衡的关键

在前文《二叉搜索树的本质》中我们提到，二叉搜索树在实践中有个很大的问题：树倾斜。按如下顺序插入数据会让二叉搜索树退化成普通链表，进而相关操作的时间复杂度退化到 O(n)：

R 教授一边呷着黑咖啡，一边盯着这棵“畸形”的二叉树发愣。

忽然，他两眼放光，好像发现了什么！

“那么，如果不让这棵树向下生长呢？”这是个大胆的想法。

既然它叫树，就必然需要生长。

如何让树向上生长呢？

我们取有序数组的中间元素作为父节点 P，将左右子数组分别作为 P 的左右子树，通过这种方式我们最终构造出了一棵平衡二叉树。

当节点中元素数量达到 3 个时，我们取中间的元素作为父节点 P，两边的元素分别作为 P 的左右子节点。

裂变成了 三个节点，以该节点为根的子树高度加 1。

我们当然可以选择在节点包含 n 个元素的时候裂变。

在二叉搜索树中，每个节点 P 最多可以有两个孩子节点：左孩子的值小于等于 P 的值，右孩子的值大于等于 P 的值。在我们新型搜索树中，一个节点最多可以有两个元素，当有两个元素 a, b 时，是可以表示三个区间的：小于 a 的元素集合 [,a)、介于 a,b 之间的元素集合 [a,b) 以及大于等于 b 的元素集合 [b,)。所以，当某节点 P 有两个元素时，它最多可以有三个子节点（想象成有序数组中两个元素分割开的三个区域）。

2-3 树。

进一步，我们发现，只有一种情况会导致树高度增加：根节点分裂——当根节点填入第三个元素时，会将中间的元素提升作为新根，而该元素左右两边的元素分别裂变成左右子树。该过程是对称的（左右子树高度同时加 1），因而无论如何裂变，整棵树都是平衡的。

通过自下而上裂变式生长，真的能保证搜索树的平衡性（至少插入元素时是这样）——发现这点后，R 教授乐坏了，赶紧开瓶香槟以示庆祝。


2-3 树的问题

不过在实现上他遇到了问题。

他在写删除逻辑的时候终于忍无可忍，将一大瓶香槟扔进了垃圾桶里。

于是他找来 L 教授帮忙。

“但我没有什么好办法让它变成二叉树或者三叉树，一个节点在成为 3 节点之前必然要先成为 2 节点，所以这两种节点都必然会实际存在。”

“不过我们能否在实现上消除一类节点呢——我的意思是，能否用 2 节点来表示 3 节点？”

L 教授解释道：“无论是 2 节点还是 3 节点，它们在逻辑上都是等价的：都是表示有序序列（有序数组），而且相互之间很容易转化。”

/**
 * 最基本的数组表示法
 */
var arr = [...[-∞, a), a, ...[a, b), b,  ...[b, ∞)]

/**
 * 2-3 搜索树的 3 节点表示法
 */
var node = {
  // 本节点元素数量
  size: 2,
  // 元素数组，升序排列
  elements: [a, b],
  // 子节点数组
  // node1 子树中元素范围：[-∞, a)
  // node2 子树中元素范围：[a, b)
  // node3 子树中元素范围：[b, ∞)
  children: [node1, node2, node3]
}

/**
 * 二叉搜索树表示法
 */
var nodeB = {
  element: b,
  left: nodeA,
  // nodeZ 子树的元素范围：[b, ∞)
  right: nodeZ
}

var nodeA = {
  element: a,
  // nodeX 子树的元素范围：[-∞, a)
  left: nodeX,
  // nodeY 子树的元素范围：[a, b)
  right: nodeY
}

L 教授画出如下草图：

为了着重表示左边的 3 节点如何拆分成右边的 2 节点，L 教授将 a、b 之间的连线用红色笔画出。

“所以待分裂的 4 节点可以用两条红线来表示。” R 教授顺着 L 教授的思路画了下图：

“不过，这种转换有何用？我们不过是把 2-3 树又变成了二叉树而已。” R 教授兴奋过后两眼又泛起了疑惑。

“不过在继续之前，我们先做个小小的优化。” L 教授继续道，“因为我们编码的时候是基于节点（而不是边）来编码的，所以我们可以将边的颜色转移给两端之一的节点——我们决定统一转给下端节点。”

“很形象的名字！”


红黑树的特性

红黑树中不可能存在两个连续的红节点。

L 教授盯着 2-3 树和转换后的红黑树思索良久，道：“2-3 树中所有叶子节点到根节点形成的简单路径上拥有的节点数量都相等。对于 2 节点，由于和红黑树中的（黑色）节点一一对应，不难处理；对于 3 节点，它在红黑树中其实由两个节点——一红一黑——构成，如果我们将这两个节点合二为一，那么红黑树中从任何叶节点到根节点的简单路径上节点数量也应该都是相同的。”

剩下的节点——也就是黑色节点——数量是相同的。”

特性 1: 不能存在两个连续的红节点；
特性 2: 从任何叶节点到根节点的简单路径上的黑节点数量是相同的；

另外，显而易见，树根节点一定是黑色的——因为它的上游不可能有节点跟它组成 2-3 树中的 3 节点。

特性 3: 树根节点是黑色的。

左倾红黑树。”

特性 4: 红节点必须是其父节点的左子节点。

“的确。3 节点转成二叉树中的两个 2 节点后，有可能增加树高度。因为二叉树本质上仍然是自上而下生长的（而非自下而上裂变的），所以注定了它不可能是一棵完美的平衡树。我们所追求的是实践意义上的近似平衡性。” L 教授略显尴尬地解释道。

插入元素

先看看插入元素 1.5。

再看看插入元素 11。

“虽然我们总能够先操作 2-3 树，然后将结果映射到红黑树，但这在实现上并不可行——到目前为止我尚未发现将 2-3 树转换成红黑树其实现意义何在。” R 教授一本正经。

神奇的三板斧

喝完咖啡，听了段莫扎特，两位教授继续研究红黑树。

“我发现前面插入元素 11 后，虽然导致整棵红黑树结构变化很大，不过还是有规律的。我感觉好像将节点 4 围绕节点 8 逆时针旋转了一下，将 4 和 8 调换了父子关系，然后将 8 的左子节点给 4，整个二叉搜索树性质并未改变。” R 教授惊喜的说到。

左旋吧——因为被旋的节点在轴的左边。” L 教授补充道。

左右旋能保证二叉搜索树性质不变（请仔细分析上两图中字母大小关系，其中椭圆节点表示子树），如果在旋转中同时保证所涉及路径上的黑色节点数量不变，则旋转操作便可以用于维护红黑树性质。

接下来我们看看能否通过上面介绍的左旋、右旋和颜色翻转来维护红黑树的性质（包括二叉搜索树的性质）。


细谈插入

假设新节点初始化为黑色，那么它必然会导致某条路径的黑色节点数加 1，进而破坏红黑树性质。

所以我们决定让新节点初始化为红色，然后试图通过“三板斧”来修复特性 1。

场景二：待插入节点的父节点是红色（也有两种情况，不过我们可以通过左旋操作让其变成一种情况）：

不过，我们得考察一下 α 子树和 β 子树。

如果 α 子树的树根是红节点，则节点 P 的颜色违反了特性 1。

不过，细心的你肯定发现问题了。颜色翻转并没有解决问题，只是将可能的冲突从下面转移到了上面：翻转后，x 的颜色有可能跟其父节点颜色冲突（同为红色）。

因而，翻转颜色后，我们还要判断 x.parent 的颜色，如果是黑色则万事大吉，倘若是红色，则需要递归处理，直到整棵树的根节点。

红节点合并与裂变的对应关系如下：

    如果 P 节点不存在，则 b 会成为新的根（在红黑树中，需要将它再变成黑色）；
  1. 否则，在 2-3 树中，b 提升后至少会形成 3 节点，对应红黑树中红色 b 节点；
  2. b 提升后也可能形成 4 节点（当原本的 P 就是 3 节点时），此时会继续裂变，对应到红黑树中就是红色 b 的父节点仍然是红色；

最后一个问题是，当红色合并操作递归到整棵树的根节点时会发生什么？

我们看看递归到根节点时的几种情况：

    不存在连续的红节点；
  1. 当原本根节点是黑色时，自然没问题；
  2. 当原本根节点时红色时，变成黑色后，所有路径上黑节点数都加 1，仍然满足红黑树的性质；

再谈三板斧

从上面例子可知，当我们想将右倾红节点变成左倾红节点以满足特性 4 时要用到左旋，旋转后，父节点位置的颜色保持不变，原先右边的红色跑道左边去了。如图：

/**
 * 将 h 围绕其右子节点左旋。
 * @returns 返回新的父节点
 */
function rotateLeft(h: Node): Node {
    assert(h && h.right)

    const x = h.right
    h.right = x.left
    x.left = h

    x.color = h.color
    h.color = 'RED'

    return x
}

对称地，右旋如下：

/**
 * 将 h 围绕其左子节点右旋。
 * @returns 返回新的父节点
 */
function rotateRight(h: Node): Node {
    assert(h && h.left)

    const x = h.left
    h.left = x.right
    x.right = h

    x.color = h.color
    h.color = 'RED'

    return x
}

颜色翻转代码实现：

/**
 * 将 h 和其两个子节点执行颜色翻转
 * 要求 h 的两个子节点颜色相同而且和 h 的颜色不同
 */
function flipColors(h: Node) {
    assert(h && h.left && h.right)
    assert(h.left.color === h.right.color && h.left.color !== h.color)

    const hColor = h.color
    h.color = h.left.color
    h.left.color = hColor
    h.right.color = hColor
}

经分析发现，以上三种操作既不会破坏二叉搜索树的性质，也不会导致任何一条“叶-根”路径上黑节点数量发生改变，近乎完美——除了可能导致出现两个连续的红节点（破坏特性 1），因而实际使用中需要自下而上递归处理。


插入操作的代码实现

interface Value {
    key: number;
    val: unknown;
}

/**
 * 定义树的节点
 */
interface Node extends Value {
    left: Node | null;
    right: Node | null;
    color: 'RED' | 'BLACK';
}

class RedBlackTree {
    protected root: Node | null
    // 树节点数量
    protected _size: number

    public constructor() {
        this.root = null
        this._size = 0
    }

    /**
     * 插入元素
     * 从根节点往下找，直到找到合适的位置后插入
     * 
     * @param key - 关键字
     * @param val - 卫星数据
     */
    public insert(key: number, val: unknown) {
        this.root = this.innerInsert(this.root, { key, val })
        // 处理完成后，将根节点变成黑色，结束战斗
        this.root.color = 'BLACK'
        this._size++
    }

    /**
     * 递归地往 p 子树插入元素 value，并维护红黑树性质
     * @param p 
     * @param value
     * @returns 返回子树 p 新的根（插入并维护红黑性质后，新的根节点不一定还是原来的那个节点了）
     */
    private innerInsert(p: Node | null, value: Value): Node {
        if (p === null) {
            // p 子树是个空指针（空树），创建并返回新节点
            return this.newNode(value.key, value.val)
        }

        // p 是非空子树，则视情况将 value 插入到 p 的左子树或者右子树中
        if (value.key < p.key) {
            p.left = this.innerInsert(p.left, value)
        } else {
            p.right = this.innerInsert(p.right, value)
        }

        // 修复 p 子树的红黑性质
        return this.balance(p)
    }

    /**
     * 对以 p 为根的子树执行红黑平衡修复让该子树符合红黑树的性质
     * 注意：情况一、二、三必须按顺序执行，因为前面情况的解决可能带来后面的情况
     * @param p 子树的根
     * @returns 修复完成后返回新的根（不一定是原先那个 p 了）
     */
    private balance(p: Node): Node {
        // 情况一（右倾），执行左旋
        if (!this.isRed(p.left) && this.isRed(p.right)) {
            p = this.rotateLeft(p)
        }

        // 情况二：连续两个左倾的红节点
        if (this.isRed(p.left) && this.isRed(p.left.left)) {
            p = this.rotateRight(p)
        }

        // 情况三：一个黑节点下面挂两个红节点，其中右边的红节点违反了“左倾”原则，通过翻转颜色解决
        if (this.isRed(p.left) && this.isRed(p.right)) {
            this.flipColors(p)
        }

        return p
    }

    /**
     * 新节点默认是红色
     */
    protected newNode(key: number, val: unknown): Node {
        return { key, val, left: null, right: null, color: 'RED', size: 1 }
    }

    /**
     * 让节点 h 相对于 h.right 执行左旋
     */
    protected rotateLeft(h: Node): Node {
        // 见前面实现
    }

    /**
     * 让节点 h 相对于 h.left 执行右旋
     */
    protected rotateRight(h: Node): Node {
        // 见前面实现
    }

    /**
     * 翻转颜色
     */
    protected flipColors(h: Node) {
        // 见前面实现
    }

    /**
     * 判断节点 node 是否为红色
     * 规定 null 节点是黑色
     */
    protected isRed(node: Node | null): boolean {
        if (!node) {
            return false
        }

        return node.color === 'RED'
    }
}

删除

树形数据结构中，删除操作总是最复杂的，红黑树也不例外。

“你等等，我好像发现了个重大问题！” R 教授突然打断了 L 教授的滔滔不绝。

“你说叶子节点——这里有问题！” R 教授指着下面这棵红黑树：

“嗯......不会怎样，仍然满足红黑树全部特性，换句话说，它仍然是一棵红黑树。” L 教授若有所思，他好像也意识到了什么。

“或许我们可以引入哨兵——具体来说，我们让每个实节点都必须有两个子节点，如果没有，则用哨兵节点代替。为了不让哨兵的颜色影响实节点的颜色，哨兵节点必须是黑色（如实节点是红色，如果哨兵也是红色，则会违反特性 1）。” L 教授说道。

2-3 树必须是完全平衡的搜索树，而上面这个（删掉节点 7 后）有问题的 2-3 树并不是一棵平衡树，不过这点从图中并不能明显地看出来，如果转成代码则较明显：

var node = {
 // 本节点元素数量
 size: 2,
 // 元素数组，升序排列
 elements: [6, 8],
 // 子节点数组
 // node1 的值是 [5]
 // node2 是 null
 // node3 的值是 [9, 10]
 children: [node1, null, node3]
}

如上表示节点 node(6,8)，从 children 可见，第二个子节点是 null，而其它两个均有实际子节点，因而这里不再平衡。
所以，实际上在设计 2-3 树的时候就应该引入哨兵节点的概念了，如果 2-3 树引入了哨兵节点，那么转换为红黑树后，自然将哨兵的概念带过来了。

我们知道，对于一条路径，删除路径上的红色节点不会影响路径上黑色节点数量。

如果节点 7 本身就是红色的，那么直接删除就行了。

我们只看节点 7 到根节点这条路径：

然而，如果整条路径上本来一个红节点都没有咋办呢？

如果要删除的节点不是叶子节点呢？比如如何删除节点 8？

此处只是描述了节点删除的大体逻辑思想，具体实现仍然是用前面提到的“三板斧”，而且实现代码要比插入逻辑复杂，此处不再给出完整代码实现，感兴趣可参见本人 github https://github.com/linzier/algo-ts 中红黑树的实现。


搜索

总结

至此，我们在两位教授的帮助下，大体厘清了红黑树的演化过程：

    找到二叉树倾斜的原因：向下生长；
  1. 阻止倾斜的策略：改变生长方向——采用裂变式向上生长策略；
  2. 基于 2，演化出 2-3 树；
  3. 由于 2-3 树实现上的复杂性，引出用二叉树表示 2-3 树的想法——红黑树；
  4. 基于 2-3 树的相关特性，总结出左倾红黑树的 4 条特性，其中特性 1 和特性 2 是核心特性；
  5. 基于二叉搜索树的特性，发现三个核心操作：左旋、右旋和颜色翻转——有了这三板斧，便可以完全脱离 2-3 树来处理红黑树的平衡性，至此红黑树有了实现上的可能；

红黑树的完整实现（TypeScript 版本）见本人 github：https://github.com/linzier/algo-ts。

编程笔记 » 红黑树是怎么来的

赞同 (34) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(0)个小伙伴在吐槽