红黑树增删操作详解_红黑树删除操作解决红黑冲突

前言：

        网上众多关于红黑树的讲解，但大多数都是重复的，只列出了几种简单情况，逻辑和思维深度都不足以解答吾之困惑。。。
        直到看到张彦峰先生的 对红黑树的认识总结，基本可以说是集大成者，本文会基于此文章对复杂操作的思路方面做更详细的叙述和逻辑修正，但基本知识会略讲，可以参考原文或其它文章，原文中相关内容图片代码会直接引用，相信本文可以让你彻底弄懂RBTree的增删操作原理。

一、对红黑树的基本理解

定义：

1. 节点是红色或黑色
2. 根是黑色
3. 叶子节点（NIL，空节点）都是黑色
4. 红色节点的子节点都是黑色
5. 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点（黑高度不变）

引理：一棵有n个内部结点的红黑树的高度至多为 2log(n+1)。
红黑树本身就是一颗二叉搜索树，但与之相比“相对平衡”，引理支撑红黑树的增删查找性能稳定在log（n）级别。

二、红黑树基本操作：左旋与右旋

红黑树左旋右旋都类似于AVL树的旋转操作，只需要注意颜色要满足定义，红黑树操作的主题就是通过旋转和变色维持其定义。
左旋就是成为子节点的左子树

相应代码：

/**
     * 功能描述：左旋右侧需要平衡
     *
     * @author yanfengzhang
     * @date 2020-05-27 14:57
     * @author zhj
     * @date 2023-07-11-12-24-25
     */
    private void rotateLeft(RBTreeNode<T> p) {
        if (p != null) {
            /*拿到根节点的右子节点 */
            RBTreeNode<T> r = p.right;
            //左子树拼接
            p.right = r.left;
            if (r.left != null){//注意为空的情况
                r.left.parent = p;
            }
            /*r 将来要成为新的根节点 p.parent 为根 ，使得他为新的根节点 */
            r.parent = p.parent;
            if (p.parent == null) {
                root = r;
            }
            /*如果p 为左孩子，让他还是成为左孩子 同理*/
            else if (p.parent.left == p) {
                p.parent.left = r;
            } else {
                p.parent.right = r;
            }
            /*p设置为r左孩子*/
            r.left = p;
            p.parent = r;
        }
    }
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

右旋就是成为子节点的右子树

    /**
     * 功能描述：右旋代码
     *
     * @author yanfengzhang
     * @date 2020-05-27 14:58
     * @author zhj
     * @date 2023-07-11-12-24-25
     */
    private void rotateRight(RBTreeNode<T>  p) {
        if (p != null) {
            RBTreeNode<T>  l = p.left;
            p.left = l.right;
            if (l.right != null) {
                l.right.parent = p;
            }
            l.parent = p.parent;
            if (p.parent == null) {
                root = l;
            } else if (p.parent.right == p) {
                p.parent.right = l;
            } else {
                p.parent.left = l;
            }
            l.right = p;
            p.parent = l;
        }
    }
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

三、红黑树的插入操作

首先明确：红黑树插入的节点为红色，新插入的节点都是放在叶子节点上，同时把正在处理的节点叫作关注节点。

插入操作要解决的问题： 解决可能的连续红色节点问题（定义4）
解决方案：旋转+变色

情况一

父节点为黑色，直接插

情况二

大部分文章写当插入关注节点e时，如果其叔节点d为红色，采取变色操作就完了，但是当你将b变为红色还需要考虑a是否为红色，为黑色就不用管了

a为红色重新构成红-红结构，需要递归进行调整（一般就是情况二或者情况三）

最后，还有一种可能，a节点不存在，b为根节点，有的时候旋转变色变混了头总想着再怎么变把根节点变黑，最后发现变不出来，实际上根节点为黑色不应该把他看作一种束缚，而是解决方案；

b如果为根节点你就不需要变色或者说按情况二变成了红色，判断其为根节点后就将其变回黑色，我们之前之所以要将b变红是因为要保持节点黑高度不变（定义5）,但b为根节点你不管怎么变色黑高度都不会变，按定义置其为黑

我上面说的根节点为黑色不应该把他看作一种束缚，而是解决方案，是因为根节点一定为黑色，有多‘一定’呢，一定到利用它可以解决红黑树插入删除问题所有的矛盾点，即只要有问题把他向上递归引到根节点上矛盾必然解决，这一点在删除节点的方案中同样适用。

情况三

关注节点a的叔节点为黑就旋转+变色；
值得一提的是情况三的关注节点a不会是新插入进来的节点，因为你看c-d的黑高度至少为2，c-b-a黑高度只有1，所以a必定有黑子节点，这也是为什么我叫他 ‘关注节点’ 而不叫他 ‘插入节点’ 的原因，这种情况多见与情况二的这种调整后出现红-红冲突的情况。

情况四

插入的关注节点a为右子树时，将b左旋，再转换为前三种情况。

插入操作的总结：
插入后的修复操作（如情况二就需要修复）是一个向root节点回溯的操作，一旦牵涉的节点都符合了红黑树的定义，修复操作结束。

之所以会向上回溯是由于情况二操作会将父节点，叔叔节点和祖父节点进行换颜色，有可能会导致祖父节点红-红。这个时候需要对祖父节点为起点进行调节（向上回溯）。

为什么向上？
因为向上回溯要么满足上面的几种情况要么必然收敛于根节点，收敛于根节点定义4，5必然满足，矛盾必然解决。

如果上面的几种情况如果对应的操作是在右子树上，做对应的镜像操作。

代码如下：

    /**
     * 功能描述：插入一个节点
     *
     * @author yanfengzhang
     * @date 2020-05-27 15:07
     */
    private void insert(RBTreeNode<T> node) {
        int cmp;
        RBTreeNode<T> root = this.rootNode;
        RBTreeNode<T> parent = null;
 
        /*定位节点添加到哪个父节点下*/
        while (null != root) {
            parent = root;
            cmp = node.key.compareTo(root.key);
            if (cmp < 0) {
                root = root.left;
            } else {
                root = root.right;
            }
        }
 
        node.parent = parent;
        /*表示当前没一个节点，那么就当新增的节点为根节点*/
        if (null == parent) {
            this.rootNode = node;
        } else {
            //找出在当前父节点下新增节点的位置
            cmp = node.key.compareTo(parent.key);
            if (cmp < 0) {
                parent.left = node;
            } else {
                parent.right = node;
            }
        }
 
        /*设置插入节点的颜色为红色*/
        node.color = COLOR_RED;
 
        /*修正为红黑树*/
        insertFixUp(node);
    }
 
    /**
     * 功能描述：红黑树插入修正
     *
     * @author yanfengzhang
     * @date 2020-05-27 15:07
     */
    private void insertFixUp(RBTreeNode<T> node) {
        RBTreeNode<T> parent, gparent;
        /*节点的父节点存在并且为红色*/
        while (((parent = getParent(node)) != null) && isRed(parent)) {
            gparent = getParent(parent);
 
            /*如果其祖父节点是空怎么处理, 若父节点是祖父节点的左孩子*/
            if (parent == gparent.left) {
                RBTreeNode<T> uncle = gparent.right;
                if ((null != uncle) && isRed(uncle)) {
                    setColorBlack(uncle);
                    setColorBlack(parent);
                    setColorRed(gparent);
                    node = gparent;
                    continue;
                }
 
                if (parent.right == node) {
                    RBTreeNode<T> tmp;
                    leftRotate(parent);
                    tmp = parent;
                    parent = node;
                    node = tmp;
                }
 
                setColorBlack(parent);
                setColorRed(gparent);
                rightRotate(gparent);
            } else {
                RBTreeNode<T> uncle = gparent.left;
                if ((null != uncle) && isRed(uncle)) {
                    setColorBlack(uncle);
                    setColorBlack(parent);
                    setColorRed(gparent);
                    node = gparent;
                    continue;
                }
 
                if (parent.left == node) {
                    RBTreeNode<T> tmp;
                    rightRotate(parent);
                    tmp = parent;
                    parent = node;
                    node = tmp;
                }
 
                setColorBlack(parent);
                setColorRed(gparent);
                leftRotate(gparent);
            }
        }
        setColorBlack(this.rootNode);
    }
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
90
91
92
93
94
95
96
97
98
99
100
101
102

四、红黑树的删除操作

删除操作相比插入会困难许多，首先明确：
后继节点：对一棵二叉树进行中序遍历，遍历后的顺序，当前节点的后一个节点为该节点的后继节点；简单来说就是刚好比你大的那个节点。（后继节点用来代替删除节点是最完美的方案）

关注节点：正在处理的节点叫作关注节点。

红黑树的定义中“只包含红色节点和黑色节点”，经过初步调整之后，为了保证满足红黑树定义的最后一条要求，有些节点会被标记成两种颜色，“红 - 黑”或者“黑 - 黑”。如果一个节点被标记为了“黑 - 黑”，那在计算黑色节点个数的时候，要算成两个黑色节点。

备注：如果一个节点既可以是红色，也可以是黑色，图中用一半红色一半黑色来表示。如果一个节点是“红 - 黑”或者“黑 - 黑”，图中用左上角的一个小黑点来表示额外的黑色。

插入操作要解决的问题：

1. 解决可能的连续红色节点问题（定义4）
2. 解决黑高度不变问题（定义5）

解决方案：这就是原文章作者厉害的地方了，分两步解决，先把删除操作处理好，使树结构完整；然后提出这种不定颜色的“红 - 黑”或者“黑 - 黑”节点大大提升讨论的效率，同时凝结矛盾点在一个关注节点上，通过变换尝试解决多余黑色高度的问题，因为旋转是不愁没黑色高度的，多试几次肯定是能凑出黑色高度的；

1.针对删除节点初步调整

情况一：如果要删除的关注节点是 a，它只有一个子节点 b

注意，为什么原文章只画了a为红，b为黑的情况，因为

1. 要么a为红，b就只能为黑，但是a只有一个子节点还是黑色,那左右黑高度必然不等，不满足黑高度不变原则。
2. a黑，b黑同样不满住黑高度不变原则。
   只剩图示情况；

情况二：如果要删除的节点 a 有两个非空子节点，并且它的后继节点就是节点 a 的右子节点 c

一定是后继节点代替删除节点，且后继节点颜色要变为与删除节点颜色相同；
先说好，根据后继节点的定义，后继节点一定是左到不能再左的那一个，要么是情况二要么是情况三；
而且后继节点如果为红色，直接换下删除节点就完了，不存在黑高度问题了，所以这里讨论的后继节点为黑色。

后继节点换完删除节点a后，变成和a一样的颜色，那么d就少了一个黑高度，所以标记一下，同时关注节点由a变为d，因为接下来的工作就是围绕d去让他增加黑高度。

情况三：如果要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是右子节点

原文章的这张图有两个问题：

1. 这个c-d之间其实可以多画几个左节点，不然有歧义，记住，d扮演的是a的后继节点（看清楚定义），最接近a的值；
2. 原图好像有问题，新的关注节点应该是e,不是c
   

2. 针对关注节点进行二次调整

情况一：如果关注节点是 a，它的兄弟节点 c 是红色的

情况二：如果关注节点是 a，它的兄弟节点 c 是黑色的，并且节点 c 的左右子节点 d、e 都是黑色的

情况二很特殊，他给了关注节点上浮的机会，随着各种情况的迭代，那么关注节点就必定可以收敛于根节点，问题必然可以解决！

情况三：如果关注节点是 a，它的兄弟节点 c 是黑色，c 的左子节点 d 是红色，c 的右子节点 e 是黑色

情况四：如果关注节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色的

这一步是核心，提供了增加黑高度的解决方案，前面的迭代到这一步就可以解决矛盾，要不然就得靠情况二了。

代码如下：

    /**
     * 功能描述：删除节点
     *
     * @author yanfengzhang
     * @date 2020-05-27 15:11
     */
    private void remove(RBTreeNode<T> node) {
        RBTreeNode<T> child, parent;
        boolean color;
        /*被删除节点左右孩子都不为空的情况*/
        if ((null != node.left) && (null != node.right)) {
 
            /*获取到被删除节点的后继节点*/
            RBTreeNode<T> replace = node;
 
            replace = replace.right;
            while (null != replace.left) {
                replace = replace.left;
            }
 
            /*node节点不是根节点*/
            if (null != getParent(node)) {
                /*node是左节点*/
                if (getParent(node).left == node) {
                    getParent(node).left = replace;
                } else {
                    getParent(node).right = replace;
                }
            } else {
                this.rootNode = replace;
            }
 
            child = replace.right;
            parent = getParent(replace);
            color = getColor(replace);
 
            if (parent == node) {
                parent = replace;
            } else {
                if (null != child) {
                    setParent(child, parent);
                }
                parent.left = child;
 
                replace.right = node.right;
                setParent(node.right, replace);
            }
 
            replace.parent = node.parent;
            replace.color = node.color;
            replace.left = node.left;
            node.left.parent = replace;
            if (color == COLOR_BLACK) {
                removeFixUp(child, parent);
            }
 
            node = null;
            return;
        }
 
        if (null != node.left) {
            child = node.left;
        } else {
            child = node.right;
        }
 
        parent = node.parent;
        color = node.color;
        if (null != child) {
            child.parent = parent;
        }
 
        if (null != parent) {
            if (parent.left == node) {
                parent.left = child;
            } else {
                parent.right = child;
            }
        } else {
            this.rootNode = child;
        }
 
        if (color == COLOR_BLACK) {
            removeFixUp(child, parent);
        }
        node = null;
    }
 
    /**
     * 功能描述：删除修复
     *
     * @author yanfengzhang
     * @date 2020-05-27 15:11
     */
    private void removeFixUp(RBTreeNode<T> node, RBTreeNode<T> parent) {
        RBTreeNode<T> other;
        /*node不为空且为黑色，并且不为根节点*/
        while ((null == node || isBlack(node)) && (node != this.rootNode)) {
            /*node是父节点的左孩子*/
            if (node == parent.left) {
                /*获取到其右孩子*/
                other = parent.right;
                /*node节点的兄弟节点是红色*/
                if (isRed(other)) {
                    setColorBlack(other);
                    setColorRed(parent);
                    leftRotate(parent);
                    other = parent.right;
                }
 
                /*node节点的兄弟节点是黑色，且兄弟节点的两个孩子节点也是黑色*/
                if ((other.left == null || isBlack(other.left)) &&
                        (other.right == null || isBlack(other.right))) {
                    setColorRed(other);
                    node = parent;
                    parent = getParent(node);
                } else {
                    /*node节点的兄弟节点是黑色，且兄弟节点的右孩子是红色*/
                    if (null == other.right || isBlack(other.right)) {
                        setColorBlack(other.left);
                        setColorRed(other);
                        rightRotate(other);
                        other = parent.right;
                    }
                    /*node节点的兄弟节点是黑色，且兄弟节点的右孩子是红色，左孩子是任意颜色*/
                    setColor(other, getColor(parent));
                    setColorBlack(parent);
                    setColorBlack(other.right);
                    leftRotate(parent);
                    node = this.rootNode;
                    break;
                }
            } else {
                other = parent.left;
                if (isRed(other)) {
                    setColorBlack(other);
                    setColorRed(parent);
                    rightRotate(parent);
                    other = parent.left;
                }
 
                if ((null == other.left || isBlack(other.left)) &&
                        (null == other.right || isBlack(other.right))) {
                    setColorRed(other);
                    node = parent;
                    parent = getParent(node);
                } else {
                    if (null == other.left || isBlack(other.left)) {
                        setColorBlack(other.right);
                        setColorRed(other);
                        leftRotate(other);
                        other = parent.left;
                    }
 
                    setColor(other, getColor(parent));
                    setColorBlack(parent);
                    setColorBlack(other.left);
                    rightRotate(parent);
                    node = this.rootNode;
                    break;
                }
            }
        }
        if (node != null) {
            setColorBlack(node);
        }
    }
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

参考文献：

1. 对红黑树的认识总结
2. 红黑树深入剖析及Java实现 - 美团技术团队