参考
漫画：什么是红黑树？
wikipedia
在线测试
Red Black Tree
动机
二叉搜索树(也叫二叉查找树，二叉排序树)利用二分法的思想，使得查找效率很高。最大查找次数是树的高度。但由于不平衡的原因，某些情况下，树的高度很高，查找近乎单链表遍历。AVL/红黑树就是为了均衡这种情况，让二叉搜索树变得稳定，可靠
性质
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：
1 节点是红色或黑色。
2 根是黑色
3 所有叶子都是黑色（叶子是NIL节点）
4 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点）
5 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
变换规则
插入的节点是红色节点(如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。)
1.变颜色的情况：当前节点的父节点是红色，且它的叔叔节点也是红色.
- 把父节点设为黑色
- 把叔叔节点设为黑色
- 把祖父节点设为红色
- 把当前结点指向祖父结点
2.左旋：当前节点的父节点是红色，叔叔节点是黑色。且当前的节点是右子树。
左旋以父节点作为左旋
3.右旋：当前节点的父节点是红色，叔叔节点是黑色，且当前的节点是左子树。右旋
- 把父节点变为黑色
- 把祖父节点变为红色
- 以祖父节点旋转
实践
before
insert 1
after
before
insert 7
after
before
insert 6 step1
insert 6 step2
insert 6 step3
endding
代码实现
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
| #define RED BOOL_FLASE
#define BLACK BOOL_TRUE
class Node
{
int date;
bool color;
Node *left;
Node *right;
Node *parent;
Node *root;
public:
Node(int &date)
{
this->date = data;
}
void LeftRotation(Node *e)
{
Node *s = e->right;
if (e->parent == NULL)
root = s;
else if (e->parent->left = e)
e->parent->left = s;
else
e->parent->right = s;
if (s->left != NULL)
s->left->parent = e;
s->parent = e->parent;
e->parent = s;
e->right = s->left;
s->left = e;
}
void RightRotation(Node *s)
{
Node *e = s->left;
if (s->parent == NULL)
root = e;
else if (s->parent->left == s)
s->parent->left = e;
else if (s->parent->right == s)
s->parent->right = e;
if (e->right != NULL)
e->right->parent = s;
e->parent = s->parent;
s->parent = e;
s->left = e->right;
e->right = s;
}
void InsertRBT(Node *root, int data)
{
if (data > root->data)
{
if (root->right == NULL)
{
root->right = new Node(data);
root->right.color = RED;
}
else
InsertRBT(root->right, data);
}
else
{
if (root->left == NULL)
{
root->left = new Node(data);
root->right.color = RED;
}
else
InsertRBT(root->left, data);
}
InsertRBTFixedUp();
}
void InsertRBT(Node *root, int data)
{
Node *x = this->root;
Node *y = NULL;
Node *n = new Node(data);
n.color = RED;
while (x)
{
y = x;
if (data > x->data)
x = x->right;
else
x = x->left;
}
if (!y)
this->root = Node;
else if (date > y->date)
y->right = n;
else
y->left = n;
InsertRBTFixedUp();
}
InsertRBTFixedUp(Node *c)
{
while (c->parent->color == RED)
{
if (c->parent->parent->left->color == RED && c->parent->parent->right->color == RED)
{
c->parent->parent->right->color = BLACK;
c->parent->parent->left->color = BLACK;
c->parent->parent->color = RED;
c = c->parent->parent;
}
else if (c->parent->parent->left->color == BLACK || c->parent->parent->right->color == BLACK)
{
if (c == c->parent->left)
{
c->parent->color = BLACK;
c->parent->parent = RED;
RightRotation(c->parent->parent);
}
else
{
LeftRotation(c->parent);
}
}
}
root->color = BLACK;
}
void DeleteRBT(Node *root, int data)
{
}
}
|
ending
