红黑树的插入（C++实现）

1. 红黑树

1.1 概念

红黑树是一种二叉搜索树，它是AVL树的优化版本。红黑树是每个节点都带有颜色属性的二叉搜索树，颜色为红色或黑色。

之所以选择“红色”是因为这是作者在帕罗奥多研究中心公司Xerox PARC工作时用彩色雷射列印机可以产生的最好看的颜色。另一种说法来自Guibas，是因为红色和黑色的笔是他们当时可用来绘制树的颜色。

1.2 性质

在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

1. 节点是红色或黑色；
2. 根是黑色；
3. 所有叶子都是黑色（叶子是NIL节点）；
4. 每个红色节点必须有两个黑色的子节点；
   • （或者说从每个叶子到根的所有路径上不能有两个连续的红色节点。）
   • （或者说不存在两个相邻的红色节点，相邻指两个节点是父子关系。）
   • （或者说红色节点的父节点和子节点均是黑色的。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

下面是一个红黑树的图例：

关于图示中的NIL

图中使用NIL表示空叶子，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略。有这样的结论：所有节点都有两个子节点，尽管其中的一个或两个可能是空叶子。

关键特性

由于有上面的性质（主要是性质4）的限制，使得红黑树从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

由性质4可以知道，最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

对于这个关键特性，可以用一个极端情况理解：红黑树的一个子树是另一个子树的长度的两倍。那么就查找而言，最坏的情况下红黑树也就比AVL树多查找了一次，最坏查找次数是$2lo{g}_{2}N$，得益于CPU算力的强大，这多出来的一倍对整体效率并没有影响（大O计数法也是这么做的）。红黑树放宽了左右高度限制，所以它的旋转次数变少了，而这样做能减少插入时多次旋转造成的性能损失，而这就是红黑树优于AVL树的原因。

2. 实现红黑树

2.1 定义红黑树结点类

和实现AVL树结点类类似，依然使用pair键值对作为结点值的部分。必要时，红黑树依然要进行旋转，所以和AVL一样，也要定义一个parent变量，用于存放结点的父结点的地址。

除此之外，红黑树新增了一个_col变量，用于表示结点的颜色。在此，使用枚举常量保存颜色。

enum Color // 使用枚举
{
    RED,
    BLACK
};
// 红黑树结点类
template<class K, class V>
struct RBTreeNode
{
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;

    Color _col;                         // 颜色
    pair<K, V> _kv;

    RBTreeNode(const pair<K, V>& kv)
            : _left(nullptr)
            , _right(nullptr)
            , _parent(nullptr)
            , _kv(kv)
            , _col(RED)                 // 默认插入结点为红色
    {}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

默认插入的颜色为什么是红色？

如果是红色，可能会违反红黑树的性质4，但如果是黑色，一定会违反红黑树的性质5，这是性质4和性质5之间的抗衡。

就如示例中的这棵红黑树，如果在11的右孩子处新增红色结点，那么刚刚好不会破坏红黑树的性质，但如果在27的右孩子处新增黑色结点，会违反红黑树的规则5：从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点，这样会有一条路径的黑色结点比其他结点多一个。

对于插入结点颜色的设置，因为两种颜色都（可能）会违反规则，破坏红黑树的性质，所以选择影响较小的方式：默认新插入结点为红色。不论哪种方式，后续都有其对应的解决办法，即变色和旋转。

2.2 插入

由于红黑树是一种二叉搜索树，新插入结点必须在一个适合自己大小的位置插入，所以在真正插入结点之前还是二叉搜索树查找位置的逻辑。

红黑树新增了颜色的限制，去除了AVL树高度限制，所以插入以后只要根据颜色的情况采取对应操作。

插入步骤：

1. 按二叉搜索树的插入步骤找到插入的位置；
2. 插入新结点；
3. 如果新插入的父结点是红色，要对红黑树调整。

为了理解和代码实现的方便，在下面的示例中用cur表示当前结点，用parent表示cur的父结点，用uncle表示cur的叔叔（即parent的另一个兄弟），用grandparent表示cur的祖父结点（即parent的父结点）。

插入结点之后，不一定要对树进行调整，只有当parent为红色时才需要。因为当当parent为红色，说明parent不是根结点（注意根结点是黑色的），所以grandparent一定存在，故parent为黑色时不影响红黑树的性质（以图理解）。

情况1：uncle存在且为红

抽象图能表示一类能用相同方式解决的所有情况：

而叔叔存在且为红最简单的情况就是abcde都是空树，一个最简单的例子：

然而，调整到此还未结束，因为我们要用一般情况看待调整的对象，即变色和旋转的对象都是整棵树的其中一棵子树。所以对grandparent而言，还需要再讨论它是否是根结点：

• 如果grandparent是根结点，将parent置黑，相当于每条路径的黑结点都多了一个；
• 如果grandparent不是根结点，说明它就是一棵子树，那么对于整棵树而言，这棵调整以后的子树就是新子树，要将新插入结点cur更新为grandparent插入原树。

上面的操作可能不止一次地被执行，因为此次插入新结点以后，grandparent的父结点也可能是红色的。

不论cur是parent的左右孩子，不论abcde是否为空，处理方式都是将parent和uncle置黑，将grandparent置红。

情况2：uncle存在且为黑

这种情况只可能是情况1变色调整过程中出现的，因为在变色之前叔叔如果存在的话不可能为黑，否则这一条路径下的黑色结点的个数就比其他路径多1了。

而且cur一定是上次调整以后更新的grandparent。

当叔叔存在且为黑时，不仅单纯需要变色，而且需要旋转。根据cur、parent和grandparent之间的结构，可以分为单旋和双旋。

• c、p、g呈直线，单旋+变色；
• c、p、g呈折线，双旋+变色。

c、p、g呈直线

cur、parent和grandparent呈直线时，根据uncle是否存在，还可以分为两种情况。

uncle存在

下面的例子能更好地理解叔叔结点存在且为黑的原因：

此例中第二棵树中的cur就是上一棵子树中插入新结点、调整颜色以后的grandparent。

从结果来看（就像分析AVL树的旋转过程一样），对于整棵树而言，插入新结点以后，它的左子树红色结点的个数大于右子树红色结点的个数，所以可以简单地理解为向右旋转后会把左边多出来的红色结点甩到右边。

事实上旋转并不能达到这种效果，但是旋转以后改变了cur、parent和grandparent的相对位置，当旋转完毕以后执行“parent和uncle变黑，grandparent变红”后，变能达到这种效果。

再来重新审视这个步骤：parent和uncle变黑，grandparent变红：

• 旋转之前：

  

• 旋转之后：

  

旋转以后再执行变色操作，可以将原来左边的红色结点“甩”到右边。

uncle不存在

当cur、parent和grandparent呈折线，而uncle不存在，则说明parent一定是红色的，这也说明cur一定是新插入的结点而不是颜色调整以后的上一次处理的grandparent。uncle为空，说明以grandparent为根结点的这棵子树只有一个子树，假如cur是上次处理后的grandparent，那么上次处理的子树中一定会多一个黑色结点（parent和uncle变黑），这样以grandparent为根结点的左右子树的黑色节点的个数就不相同了。

c、p、g呈折线

当cur、parent和grandparent呈折线时，根据uncle结点存在与否，也可以分为两种情况。

uncle存在

最简单的例子：

旋转的目的是一样的，将左边多余的红色结点“甩”到右边。由于最后这棵子树的根结点的颜色被更新为黑色，所以不用再往上更新了。

uncle不存在

当祖孙三代结点呈折线时，uncle不存在也说明cur是新插入结点，原因同上。

注意

上面的每种情况都存在对称的情况，所以在代码中会有多个if…else语句区分左右子树，操作都是镜像的。

代码

typedef RBTreeNode<K, V> Node;

    // 插入函数
    bool Insert(const pair<K, V>& kv)
    {
        if (_root == nullptr)                   // 空树
        {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }

        Node *cur = _root;
        Node *parent = nullptr;

        while (cur)                             // 迭代,找到插入位置
        {
            if (kv.first < cur->_kv.first)      // 插入的值比key值小
            {
                parent = cur;
                cur = cur->_left;               // 往左走
            }
            else if (kv.first > cur->_kv.first) // 插入的值比key值大
            {
                parent = cur;
                cur = cur->_right;              // 往右走
            }
            else                                // 找不到
            {
                return false;
            }
        }
                                                // 跳出循环,说明找到插入的位置了
        cur = new Node(kv);                     // 将cur更新为新插入结点
        if (cur->_kv.first < parent->_kv.first) // 新结点值比叶子(父)结点小
        {
            parent->_left = cur;                // 作为父结点的左孩子插入
            cur->_parent = parent;
        }
        else
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
                                                // 插入成功

                                                // 检查并调整颜色
        while (parent && parent->_col == RED)   // 父结点非空且为红,说明它是子树的根结点
        {
            Node *grandparent = parent->_parent;// 祖父结点
                                                // parent的位置分两种情况
            if (parent == grandparent->_left)   // (1). 父结点是祖父节点的左孩子
            {
                Node *uncle = grandparent->_right; // 叔叔就是祖父节点的另一个孩子
                if (uncle != nullptr && uncle->_col == RED) // 情况1:叔叔存在且为红
                {
                    parent->_col = BLACK;       // 父结点变黑
                    uncle->_col = BLACK;        // 叔叔结点变黑
                    grandparent->_col = RED;    // 祖父结点变红

                    cur = grandparent;
                    parent = cur->_parent;      // 继续向上处理
                }
                else                            // 跳出了上面的判断,有两种有效组合:叔叔为空,叔叔为黑
                {
                                                // 情况2：叔叔存在且为黑,右单旋+变色
                                                //     g    右旋       p
                                                //   p   u  -->   cur    g
                                                // cur                     u
                    if (cur == parent->_left)   // cur是parent的左子树
                    {
                        RotateR(grandparent);   // 以祖父结点为轴心右旋

                        parent->_col = BLACK;   // 父节点变黑
                        grandparent->_col = RED;// 祖父结点变黑
                    }
                    else                        // cur是parent的右子树
                    {
                                                // 情况3:
                                                //    g   左右旋     c
                                                //  p   u  -->    p   g
                                                //    c                 u
                        RotateR(grandparent);   // 以祖父结点为轴心右旋

                        grandparent->_col = RED;     // 父节点变黑
                        cur->_col = BLACK; // 祖父结点变黑
                    }
                    break;                      // 旋转后子树根节点变黑,停止向上调整
                }
            }
            else                                // (2). 父结点是祖父节点的右孩子,步骤相同
            {
                Node *uncle = grandparent->_left;
                if (uncle && uncle->_col == RED)
                {
                    uncle->_col = BLACK;
                    parent->_col = BLACK;
                    grandparent->_col = RED;

                    cur = grandparent;
                    parent = cur->_parent;
                }
                else
                {
                    if (cur == parent->_left)
                    {
                        RotateRL(grandparent);

                        cur->_col = BLACK;
                        grandparent->_col = RED;
                    }
                    else
                    {
                        RotateL(grandparent);

                        grandparent->_col = RED;
                        parent->_col = BLACK;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK;                    // 不论根节点何种颜色,统一处理为黑色
        return true;
    }

// 右单旋函数
    void RotateR(Node *parent)
    {
        Node *subL = parent->_left;
        Node *subLR = subL->_right;
        Node *pParent = parent->_parent;        // 保存父结点的父结点

        parent->_left = subLR;                  // 重建subLR和parent联系
        if (subLR != nullptr)
        {
            subLR->_parent = parent;
        }

        subL->_right = parent;                  // 重建subL和parent联系
        parent->_parent = subL;


        if (parent == _root)                    // 父结点为根结点，旋转后的subL作为根结点，无父结点
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (pParent->_left == parent)
            {
                pParent->_left = subL;
            }
            else
            {
                pParent->_right = subL;
            }

            subL->_parent = pParent;
        }
    }
    // 左单旋函数
    void RotateL(Node *parent)
    {
        Node *subR = parent->_right;
        Node *subRL = subR->_left;
        Node *pParent = parent->_parent;        // 保存父结点的父结点

        parent->_right = subRL;                 // 重建subRL和parent联系
        if (subRL != nullptr)
        {
            subRL->_parent = parent;
        }

        subR->_left = parent;                   // 重建subR和parent联系
        parent->_parent = subR;


        if (parent == _root)                    // 父结点为根结点，旋转后的subR作为根结点，无父结点
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (pParent->_left == parent)
            {
                pParent->_left = subR;
            }
            else
            {
                pParent->_right = subR;
            }

            subR->_parent = pParent;
        }
    }
    // 左右双旋函数
    void RotateLR(Node *parent)
    {
        Node *subL = parent->_left;

        RotateL(subL);
        RotateR(parent);
    }
    // 右左双旋函数
    void RotateRL(Node *parent)
    {
        Node *subR = parent->_right;

        RotateR(subR);
        RotateL(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
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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214

2.3 红黑树的验证

红黑树是一种二叉搜索树，所以最基本地，用中序遍历查看结点值是否有序。其次要用红黑树的规则验证。

//中序遍历
void Inorder()
{
	_Inorder(_root);
    cout << endl;
}
//中序遍历子函数
void _Inorder(Node* root)
{
	if (root == nullptr)
		return;
	_Inorder(root->_left);
	cout << root->_kv.first << " ";
	_Inorder(root->_right);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

验证左右子树黑结点的个数是否相等。

由于红黑树的每条路径中黑色结点的个数都相等，所以可以任意取一条路径中的黑色结点个数作为基准值。怎么取才最方便呢？对于一棵树，它的最左路径和最右路径是最好走的，所以在这里以最左路径的黑色结点个数为基准值。

只需要验证是否是红黑树，而不用找到具体哪一条路径有问题，所以只要某条路径和基准值是否相等即可判断是否是红黑树。

采用递归方式：

//判断是否为红黑树
bool ISRBTree()
{
	if (_root == nullptr)
	{
		return true;
	}
    
	if (_root->_col == RED)
	{
		cout << "error:根结点为红色" << endl;
		return false;
	}
	
	// 以最左路径的黑色结点数做为的参考值
	Node* cur = _root;
	int BlackCount = 0;
	while (cur)
	{
		if (cur->_col == BLACK)
			BlackCount++;
		cur = cur->_left;
	}

	int count = 0;
	return _ISRBTree(_root, count, BlackCount);
}
// ISRBTree的子函数
bool _ISRBTree(Node* root, int count, int BlackCount)
{
	if (root == nullptr) // 该路径走到空
	{
		if (count != BlackCount) // 黑色结点数量和基准值不相等
		{
			cout << "error:黑色结点的数目不相等" << endl;
			return false;
		}
		return true;
	}

	if (root->_col == RED && root->_parent->_col == RED)
	{
		cout << "error:存在连续的红色结点" << endl;
		return false;
	}
	if (root->_col == BLACK)
	{
		count++;
	}
	return _ISRBTree(root->_left, count, BlackCount) 
        && _ISRBTree(root->_right, count, BlackCount);
}

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