AVL和红黑树都是自平衡二叉树

AVL树

AVL树是最早的自平衡二叉树

性质

  • 节点的平衡因子: 左子树高度减去右子树高度
  • 节点平衡因子为1,0,-1认为是平衡,为2,2认为是不平衡需要重新平衡

AVL树的插入删除及查找的复杂度均为O(log(n))O(log(n))

旋转

插入和删除使得AVL树不平衡,有以下四种情况

实现

留坑

红黑树

STL中 set/map 的实现皆为红黑树

性质

红黑树是每个节点为红/黑色的BST,满足以下性质要求:

  1. 节点是红色或黑色
  2. 根是黑色
  3. 所有叶子都是黑色(叶子是NIL节点)
  4. 每个红色节点必须有两个黑色的子节点(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点

这些特性保证了红黑树从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。(最短皆为黑节点,最长为红/黑节点交替)

RB-Tree

红黑树的插入删除及查找的复杂度均为O(log(n))O(log(n))
缺点是实现较为复杂,有五种插入,六种删除操作

与AVL树比较

  • AVL树对平衡的要求更高(左右子树的高度差最多为1),因此一般需要rebalance的次数比红黑树多
  • 插入操作引起树的不平衡时,最坏情况下红黑树和AVL树都需要2次旋转操作
  • 删除操作引起树的不平衡时,最坏情况下红黑树需要3次旋转操作,AVL树需要**log(n)**次旋转操作(需要维护从被删node到root这条路径上所有node的平衡性)

因此map的实现使用的是红黑树

插入

插入节点后需要调整来保证红黑树的性质
设插入的节点为n,父节点为p,叔父节点为u,祖父节点为g
颜色为红色(黑色会导致根到叶子节点一条路径上多一个黑节点,不容易调整),我们发现:

  • 性质1和性质3总是保持着
  • 性质4只在增加红色节点、重绘黑色节点为红色,或做旋转时受到威胁
  • 性质5只在增加黑色节点、重绘红色节点为黑色,或做旋转时受到威胁

1. n在根上

将其重绘为黑

1
2
3
4
5
6
void insert_case1(node *n){
if(n->parent == NULL)
n->color = BLACK;
else
insert_case2 (n);
}

2. p为黑色

不影响红黑树的性质

1
2
3
4
5
6
void insert_case2(node *n){
if(n->parent->color == BLACK)
return; /* 树仍旧有效*/
else
insert_case3 (n);
}

3. p,u都是红色

将p,u重绘为黑,并将g重绘为红,再从case1调整g

1
2
3
4
5
6
7
8
9
10
void insert_case3(node *n){
if(uncle(n) != NULL && uncle (n)->color == RED) {
n->parent->color = BLACK;
uncle (n)->color = BLACK;
grandparent (n)->color = RED;
insert_case1(grandparent(n));
}
else
insert_case4 (n);
}

4.p为红色,u为黑色或不存在,n为p的右(左)孩子,p为g的左(右)孩子

先左(右)旋n,再按第五种情况调整以前的p

1
2
3
4
5
6
7
8
9
10
void insert_case4(node *n){
if(n == n->parent->right && n->parent == grandparent(n)->left) {
rotate_left(n->parent);
n = n->left;
} else if(n == n->parent->left && n->parent == grandparent(n)->right) {
rotate_right(n->parent);
n = n->right;
}
insert_case5 (n);
}

5.p为红色,u为黑色或不存在,n为p的左(右)孩子,p为g的左(右)孩子

p染成黑色,g染成红色,右(左)旋g

1
2
3
4
5
6
7
8
9
10
void insert_case5(node *n){
n->parent->color = BLACK;
grandparent (n)->color = RED;
if(n == n->parent->left && n->parent == grandparent(n)->left) {
rotate_right(grandparent(n));
} else {
/* n == n->parent->right && n->parent == grandparent (n)->right */
rotate_left(grandparent(n));
}
}

删除

设删除的节点为n,父节点为p,兄弟节点为s,左儿子为sl,右儿子为sr

二叉搜索树的删除操作一般如下:

  • 若n为叶子节点,直接删除
  • 若n只有一个儿子,则直接删除,将其儿子放在它的位置
  • 若n有两个儿子,则将其与左(右)子树的最右(左)节点替换,变成了叶子节点

对于两个儿子的情况,我们将其与叶子节点位置替换(颜色也替换)
因此我们只需要讨论删除只有一个儿子(或没有)的节点的情况

若删除节点为红色,则可以直接删除,而不影响性质
若删除节点为黑色,其儿子为红色,只需将其儿子染黑
下面讨论的是删除节点和其儿子都为黑色的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void delete_one_child(struct node *n)
{
/*
* Precondition: n has at most one non-null child.
*/
struct node *child = is_leaf(n->right)? n->left : n->right;

replace_node(n, child); //n与某个孩子位置替换
if(n->color == BLACK){
if(child->color == RED)
child->color = BLACK;
else
delete_case1 (child);
}
free (n);
}

我们对当前的n做如下调整:

1. n是新的根

直接替换

1
2
3
4
5
void delete_case1(struct node *n)
{
if(n->parent != NULL)
delete_case2 (n);
}

2. s为红色

将p染红,将s染黑
n为左(右)儿子,对p左(右)旋,接下来的情况按4,5,6处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void delete_case2(struct node *n)
{
struct node *s = sibling (n);

if(s->color == RED){
n->parent->color = RED;
s->color = BLACK;
if(n == n->parent->left)
rotate_left(n->parent);
else
rotate_right(n->parent);
}
delete_case3 (n);
}

3. p,s,sl,sr都为黑色

将s染红,并从头开始处理p

1
2
3
4
5
6
7
8
9
10
11
12
13
void delete_case3(struct node *n)
{
struct node *s = sibling (n);

if((n->parent->color == BLACK)&&
(s->color == BLACK)&&
(s->left->color == BLACK)&&
(s->right->color == BLACK)) {
s->color = RED;
delete_case1(n->parent);
} else
delete_case4 (n);
}

4.s,sl,sr为黑色,p为红色

将s染红,p染黑

1
2
3
4
5
6
7
8
9
10
11
12
13
void delete_case4(struct node *n)
{
struct node *s = sibling (n);

if((n->parent->color == RED)&&
(s->color == BLACK)&&
(s->left->color == BLACK)&&
(s->right->color == BLACK)) {
s->color = RED;
n->parent->color = BLACK;
} else
delete_case5 (n);
}

5.s,sr为黑,sl为红,n为左儿子

将s右旋(这样s的左儿子成为s的父亲和n的兄弟),交换s和其新父亲的颜色,进入情况6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void delete_case5(struct node *n)
{
struct node *s = sibling (n);

if(s->color == BLACK){
/* this if statement is trivial, due to Case 2(even though Case two changed the sibling to a sibling's child, the sibling's child can't be red, since no red parent can have a red child). */
// the following statements just force the red to be on the left of the left of the parent,
// or right of the right, so case six will rotate correctly.
if((n == n->parent->left)&&
(s->right->color == BLACK)&&
(s->left->color == RED)) { // this last test is trivial too due to cases 2-4.
s->color = RED;
s->left->color = BLACK;
rotate_right (s);
} else if((n == n->parent->right)&&
(s->left->color == BLACK)&&
(s->right->color == RED)) {// this last test is trivial too due to cases 2-4.
s->color = RED;
s->right->color = BLACK;
rotate_left (s);
}
}
delete_case6 (n);
}

6. s为黑,sr为红,n为左儿子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void delete_case6(struct node *n)
{
struct node *s = sibling (n);

s->color = n->parent->color;
n->parent->color = BLACK;

if(n == n->parent->left){
s->right->color = BLACK;
rotate_left(n->parent);
} else {
s->left->color = BLACK;
rotate_right(n->parent);
}
}

实现

留坑,可以参考维基百科的实现

参考