Rbtree学习
rbtree的几个原则
- （颜色属性）节点非黑即红
- （根属性）根节点一定是黑色
- （叶子属性）叶子节点（NIL）一定是黑色
- （红色属性）每个红色节点的两个子节点，都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- （黑色属性）从任一节点到其每个叶子的所有路径，都包含相同数目的黑色节点。
rbtree平衡调整的两个手段： 旋转 和 变色
rbtree的平衡调整需要关注两个场景：当父亲节点为红色
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
| 叔叔节点为红：
即父亲叔叔都为红-》调整为黑，同时爷爷变红
爷爷向上递推调整
叔叔节点为黑：
1、LL型失衡：变色、对爷爷左旋或右旋
privot，root颜色取反，旋转
2、LR型失衡：对父亲旋转-》LL型
## 说白了即满足黑色属性和红色属性因此
# 平衡调整代码：
inline void
Rb_tree_rebalance(Rb_tree_node_base* __x, Rb_tree_node_base*& __root)
{
__x->_color = red;
while (__x != __root && __x->_parent->_color == red)
{
if (__x->_parent == __x->_parent->_parent->_left)
{
Rb_tree_node_base* __y = __x->_parent->_parent->right;
if (__y && __y->_color == red)
{
__x->_parent->_color = black;
__y->_color = black;
__x->_parent->parent->_color = red;
__x = __x->_parent;
}
else
{
if (__x == __x->_parent->right)
{
__x == __x->_parent;
Rb_tree_rotate_left(__x, __root);
}
__x->_parent->_color = black;
__x->_parent->_parent->_color = red;
Rb_trer_rotate_right(__x->_parent->_parent, __root);
}
}
else {
Rb_tree_node_base* __y = __x->_parent->_parent->_left;
if (__y && __y-> _color == red)
{
__x->_parent->_color = black;
__y->_color = black;
__x->_parent->_parent->_color = red;
__x = __x->_parent->_parent;
}
else
{
if (__x == __x->_parent->_left)
{
__x = __x->_parent;
Rb_trer_rotate_right(__x, __root);
}
__x->_parent->_color = black;
__x->_parent->_parent->_color = red;
Rb_tree_rotate_left(__x->_parent->_parent, __root);
}
}
}
__root->_color = black;
}
|
由此可以很快得出插入、删除的操作
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
|
Rb_tree_node_base* erase_aux(Rb_tree_node_base* x, Rb_tree_node_base* root)
{
if(x->left == 0 && x->right == 0)
{
if(x->color == red)
{
if(x == x->parent->left) x->parent->left = nullptr;
else x->parent->right = nullptr;
return x;
}
else
{
Rb_tree_node_base* p = x->parent;
Rb_tree_node_base* bro = p->left == x ? p->right : p->left;
if(bro->color == red)
{
if(bro == p->left)
{
bro->right->color = red;
bro->color = black;
rotate_right(p);
}
else
{
bro->left->color = red;
bro->color = black;
rotate_left(p);
}
}
else
{
if(bro->left == 0 && bro->right == 0)
{
bro->color = red;
p->color = black;
}
else if(bro->right == 0)
{
if(bro == p->left)
{
bro->left->color = black;
bro->color = p->color;
p->color = black;
rotate_right(p);
}
else(bro == p->right)
{ }
}
else if(bro->left == 0)
{
}
else 有两个孩子，都为红色
{
if(bro == p->left)
{
bro->left->color = black;
bro->color = p->color;
p->color = black;
rotate_right(p);
}
else
{}
}
}
}
}
else if(x->right == 0)
{
}
else
{
}
}
|
常见面试题
BST和AVL区别：
BST没有自平衡，查找效率容易变成O(n)，引入左右子树高度差保证O(logn)
有AVL为什么还要Rbtree：
AVL的左右子树高度差不能超过1，每次进行插入/删除操作时，几乎都需要通过旋转操作保持平衡
在频繁进行插入/删除的场景中，频繁的旋转操作使得AVL的性能大打折扣
红黑树通过牺牲严格的平衡，换取插入/删除时少量的旋转操作，
整体性能优于AVL
红黑树插入时的不平衡，不超过两次旋转就可以解决；删除时的不平衡，不超过三次旋转就能解决
红黑树的红黑规则，保证最坏的情况下，也能在O ( log n）时间内完成查找操作。
AVL rbtree区别
1、调整平衡的实现机制不同
红黑树根据路径上黑色节点数目一致，来确定是否失衡，如果失衡，就通过变色和旋转来恢复
AVL根据树的平衡因子(所有节点的左右子树高度差的绝对值不超过1)，来确定是否失衡，如果失衡，就通过旋转来恢复
2、红黑树的插入效率更高
红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，
红黑树并不追求“完全平衡”，它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能
而AVL是严格平衡树(高度平衡的二叉搜索树)，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。
所以红黑树的插入效率更高
3、红黑树统计性能比AVL树更高
红黑树能够以O(log n) 的时间复杂度进行查询、插入、删除操作。
AVL树查找、插入和删除在平均和最坏情况下都是O(log n)。
红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高，
4、适用性：AVL查找效率高
如果你的应用中，查询的次数远远大于插入和删除，那么选择AVL树，如果查询和插入删除次数几乎差不多，应选择红黑树。
即，有时仅为了排序（建立-遍历-删除），不查找或查找次数很少，R-B树合算一些
