左偏红黑树稽古 III 插入节点的修正方法

Author: sandyzikun

现在已经先后讲完了二叉查找树的基本增删操作，左偏红黑树的概念与结构特征，以及旋边、翻转操作。
需要的前置内容已经全部理清，现在可以开始审察其节点插入操作。

Intro

左偏红黑树1节点的插入操作可以理解为在常规地二叉查找树插入后，修复插入后的左偏红黑树，以保证其仍然满足左偏红黑树的相关特征。
由于随意插入黑色节点会频繁破坏黑高平衡，使维护工作难度变大，因此我们在插入节点的时候 默认插入的是红色节点， 然后在修复的过程中再进行染色调整。
由于红黑树中本身存在两种节点：红色节点与黑色节点，因此在插入的时候我们也分为向黑色节点插入与向红色节点插入两种情形进行讨论。

Insertion

into Black Nodes

如图，向黑色节点的插入操作可以分为插入为左孩子与插入为右孩子两种情形。
前者情形由于插入的节点目前为叶子，且其母亲节点向上的边为黑边，而在过程中没有破坏左偏红黑树的相关特征，因此不必再进行维护操作；后者情形会使被插入的母亲节点延展出一条右偏的红边，此时需要把这条右偏的红边进行左旋使其左偏，以维护左偏红黑树的相关特征。

into Red Nodes

如图，向红色节点的插入操作可以分为插入为红边左孩子的左孩子、插入为红边左孩子的右孩子与插入为红边母亲节点的右孩子三种情形，根据原作者在文献中的讲解，我们先考虑把前两者转化为第三种情形。

把前两者转化为第三种情形，我们通常采用的手段是：先把第二种情形转化为第一种，再把第一种情形转化为第三种。
把第二种情形转化为第一种的方法很简单，如同插入为黑色节点的右孩子一样，把连接插入的节点与其母亲节点的右偏红边左旋即可。
第一种情形中，会出现两条连续的左偏红边，此时需要操作被插入的母亲节点以及其母亲，使上方的左偏红边右旋，被插入的母亲节点把原本的母亲节点接管为自己的右孩子，并以右偏的红边进行连接。

当我们把前两者都转化为第三种情形后，还需要对第三种情形进行处理，这是因为第三种情形中被插入的母亲节点延展出了一条右偏的红边。
但此时的处理也很简单，根据红黑树的性质，母亲节点向上的一定为黑边，此时可以通过flip翻转操作，把两条红边连接孩子们、一条黑边向上连接的节点变为两条黑边连接孩子们、一条红边向上连接的节点，从而消灭右偏红边（把其转化为右偏黑边）的同时维持局部的黑高平衡。

Solution

让我们稍微总结并整合一下上述的插入过程。
这是原作者Sedgewick在原文ppt2上最初的总结：

我们先处理与4-节点等价的由某个节点延展出的左右两条红边，通过翻转颜色消灭右偏红边的同时把原本左偏的红边上移，实质上等价于把2-3-4树中的一个4-节点分裂为两个2-节点。

如若不属于上述情况，则考虑下面的过程：在插入红色节点之后，我们先把插入的右孩子左旋，如若产生了两条连续红边，再左旋为延展出左右两条红边的，与4-节点等价的节点。

但这样做在最后无疑会遗留新的4-节点，于是后面Sedgewick把分裂4-节点的操作移到最后，以保证不会遗留4-节点：

从程式上看就像是对普通的二叉查找树的插入操作加入了几行修正的操作。

Program

我们可以把这些操作，简单地封装一下。

Color Judgement

首先我们需要一个可以在某个节点非空的基础之上判断其是否被染色的函数：

C++
1
2
3
inline bool judge_colored(struct Node *rt) {
    return (rt != nullptr) ? (rt->colored) : false;
}

Fix Up

然后是封装插入过程中的修正过程，因为后面可能还会用到：

C++
1
2
3
4
5
6
7
8
9
10
11
struct Node * fixup(struct Node *rt) {
    if (judge_colored(rt->rchild))
        rt = rotate(rt);
    if (judge_colored(rt->lchild)
     && judge_colored(rt->lchild->lchild))
        rt = rotrev(rt);
    if (judge_colored(rt->lchild)
     && judge_colored(rt->rchild))
        flip(rt);
    return rt;
}

Insertion Process

于是插入过程可以写如下：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Node * __insert(struct Node *rt, int _value) {
    if (rt == nullptr)
        return new_node(_value);
    else {
        if (rt->val != _value) {
            if (_value < rt->val) {
                rt->lchild = __insert(rt->lchild, _value);
                rt->lchild->parent = rt;
            } else {
                rt->rchild = __insert(rt->rchild, _value);
                rt->rchild->parent = rt;
            }
        }
        // 最后一步，普通的二叉查找树便是直接返回节点`rt`，但我们这里要...
        return fixup(rt);
    }
} inline void insert(int _value) {
    root = __insert(root, _value);
    // 修正过程的最后可能会把根节点染色，在这里我们要强制把它的颜色进行修正
    root->colored = false;
}

Tree-Printing

此外，为了清晰地表示节点的染色情况，我们稍微修改了一下二叉树的printall函数：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void __preorder(struct Node *rt) {
    if (rt != nullptr) {
        if (rt->colored)
            printf(" [%d],", rt->val);
        else
            printf("  %d ,", rt->val);
        __preorder(rt->lchild);
        __preorder(rt->rchild);
    }
}
void __inorder(struct Node *rt) {
    if (rt != nullptr) {
        __inorder(rt->lchild);
        if (rt->colored)
            printf(" [%d],", rt->val);
        else
            printf("  %d ,", rt->val);
        __inorder(rt->rchild);
    }
}
void printall() {
    __preorder(root);   putchar('\n');
    __inorder(root);    putchar('\n');
}

References

1. OI-Wiki章节 左偏红黑树 ↩
2. Left-Leaning Red-Black Trees, Robert Sedgewick, Princeton University ↩