类比4阶B树，了解红黑树基本概念及新增删除操作_4阶b-tree

基本概念

红黑树也是一种自平衡的二叉搜索树，以前也叫做平衡二叉B树（Symmetric Binary B-tree）

必须满足以下 5 条性质

1. 节点是 RED 或者 BLACK

2. 根节点是 BLACK

3. 叶子节点（外部节点，空节点）都是 BLACK

4. RED 节点的子节点都是 BLACK

   • RED 节点的 parent 都是 BLACK

   • 从根节点到叶子节点的所有路径上不能有 2 个连续的 RED 节点

5. 从任一节点到叶子节点的所有路径都包含相同数目的 BLACK 节点

红黑树的等价变换

• 红黑树 和 4阶B树（2-3-4树）具有等价性
• BLACK 节点与它的 RED 子节点融合在一起，形成1个B树节点
• 红黑树的 BLACK 节点个数 与 4阶B树的节点总个数 相等

添加

已知

B树中，新元素必定是添加到叶子节点中

4阶B树所有节点的元素个数 x 都符合 1 ≤ x ≤ 3

建议新添加的节点默认为 RED，这样能够让红黑树的性质尽快满足（性质 1、2、3、5 都满足，性质 4 不一定）

上图所示为添加节点的所有12种情况

新增节点parent 为 BLACK

上图中粉色的四个节点的父节点为BLACK,满足 4阶B树 的性质，因此不用做任何额外处理

新增节点parent 为 RED（ Double Red ）

uncle 不是 RED

L\R-新增节点相对于祖父节点所在左右子树位置

LL/RR

1. parent 染成 BLACK，grand 染成 RED
2. grand 进行单旋操作

LR\RL

1. 自己染成BLACK,grand染成RED
2. 进行双旋

uncle 是 RED

上溢 – LL/RR/LR/RL(仅需染色)

1. parent、uncle 染成 BLACK

2. grand 向上合并，染成 RED，当做是新添加的节点进行处理

3. grand 向上合并时，可能继续发生上溢

4. 若上溢持续到根节点，只需将根节点染成 BLACK

   LL

RR

LR

RL

protected void afterAdd(Node<E> node) {
        Node<E> parent = node.parent;
        //添加的是根节点，或者上溢到达根节点
        if (parent == null) {
            black(node);
        }
        //parent节点为黑色
        if (isBlack(parent)) {
            return;
        }
        Node<E> uncle = parent.sibling();
        Node<E> grand = red(parent.parent);
        //parent节点为红色
        //uncle节点是红色
        if (isRed(uncle)) {
            black(parent);
            black(uncle);
            //祖父节点上溢，染成RED,当成新添加节点处理
            afterAdd(grand);
            return;
        }
        //uncle节点不是红色
        if (parent.isLeftChild()) { //L
            if (node.isLeftChild()) {
                //LL
                black(parent);
            } else {
                //LR
                black(node);
                rotateLeft(parent);
            }
            rotateRight(grand);
        } else { //R
            if (node.isLeftChild()) {
                //RL
                black(node);
                rotateRight(parent);
            } else {
                //RR
                black(parent);
            }
            rotateLeft(grand);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

删除

根据B树的性质，删除的节点肯定是叶子节点

RED节点

直接删除，不做任何调整

BLACK节点

拥有 2 个 RED 子节点的 BLACK 节点

不可能被直接删除，因为会找它的子节点替代删除

因此不用考虑这种情况，例如上图中的25，根据二叉搜索树的知识可知，他会找前驱节点17或者后继节点33替代他，然后删除前驱节点17或者后继节点33

拥有 1 个 RED 子节点的 BLACK 节点

判定条件：用以替代的子节点是 RED

将替代的子节点染成 BLACK 即可保持红黑树性质

BLACK 叶子节点

sibling为BLACK

BLACK 叶子节点被删除后，会导致B树节点下溢（比如删除88）

sibling 至少有 1 个 RED 子节点

1. 进行旋转操作
2. 旋转之后的中心节点继承 parent 的颜色
3. 旋转之后的左右节点染为 BLACK

sibling 没有 1 个 RED 子节点

将 sibling 染成 RED、parent 染成 BLACK 即可修复红黑树性质

如右边的情况，parent 是 BLACK ，会导致 parent 也下溢 ，这时只需要把 parent 当做被删除的节点处理即可

sibling为RED

1. sibling 染成 BLACK
2. parent 染成 RED
3. 进行旋转 ，回到 sibling 是 BLACK 的情况
4. 更换兄弟—sibling = parent.left

代码实现

@Override
    protected void afterRemove(Node<E> node) {
        //如果删除的节点是红色
//        if (isRed(node)) {
//            return;
//        }
        //用以取代node的节点是RED
        if (isRed(node)) {
            black(node);
            return;
        }
        //删除的黑色叶子节点[下溢]
        //删除的是根节点
        Node<E> parent = node.parent;
        if (parent == null) {
            return;
        }
        //删除的是黑色叶子节点
        //判断被删除的节点是左还是右
        boolean left = parent.left == null || node.isLeftChild();
        Node<E> sibling = left ? parent.right : parent.left;
        if (left) {
            //被删除的节点在左边，兄弟节点在右边
            if (isRed(sibling)) {
                //兄弟节点是红色
                black(sibling);
                red(parent);
                rotateLeft(parent);
                //更换兄弟
                sibling = parent.right;
            }
            //兄弟节点是黑色
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                //兄弟节点没有一个红色子节点
                //父节点要向下和兄弟节点合并
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentBlack) {
                    afterRemove(parent);
                }
            } else {
                //兄弟节点至少有一个红色子节点
                //向兄弟节点借元素
                if (isBlack(sibling.right)) {
                    //兄弟左边是黑色，要先左旋转
                    rotateRight(sibling);
                    sibling = parent.right;
                }
                color(sibling, colorOf(parent));
                black(sibling.right);
                black(parent);
                rotateLeft(parent);
            }
        } else {
            //被删除的节点在右边，兄弟节点在左边
            if (isRed(sibling)) {
                //兄弟节点是红色
                black(sibling);
                red(parent);
                rotateRight(parent);
                //更换兄弟
                sibling = parent.left;
            }
            //兄弟节点是黑色
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                //兄弟节点没有一个红色子节点
                //父节点要向下和兄弟节点合并
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentBlack) {
                    afterRemove(parent);
                }
            } else {
                //兄弟节点至少有一个红色子节点
                //向兄弟节点借元素
                if (isBlack(sibling.left)) {
                    //兄弟左边是黑色，要先左旋转
                    rotateLeft(sibling);
                    sibling = parent.left;
                }
                color(sibling, colorOf(parent));
                black(sibling.left);
                black(parent);
                rotateRight(parent);
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89