0. 概述
对于普通的搜索树，如果一直插入比第一个元素小的元素，它会退化成一个无限向左下角眼神的单链表，使得时间复杂度退化为O(n)。如果我们在插入时保持树的结构是平衡的，则可以保证查找、插入和删除的时间复杂度有对数级的时间性能，下面讲到的AVL树和红黑树都是平衡搜索树，通过旋转来保持平衡
1. AVL树
1.1 定义
Adelson-Velskii 和 Landis 在 1962年提出的一种平衡树，保证搜索树的高度是O(logn)，这样就可以保证查找、插入和删除的时间为O(logn)
1.2 AVL树的描述
AVL 树一般用链表描述，为了简化插入和删除操作，为每个节点增加一个平衡因子 bf ，平衡因子 bf(x) 的定义为：x 的左子树的高度 - x 的右子树的高度
从 AVL 树的定义可以知道，平衡因子 bf 的取值为 -1、0 和 1
1.3 AVL树的搜索
与普通的搜索树相同，根据 theKey 不断向左孩子或右孩子移动寻找即可，时间复杂度为O(logn)
1.4 AVL树的插入
首先是区分4种旋转情况的代码，具体在1.4.1-1.4.4部分
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
| template<class K, class V>
bool avlTree<K, V>::insert(K key, V val)
{
if (_root == NULL)
{
_root = new Node<K, V>(key, val);
return true;
}
else
{
Node<K, V>* cur = _root;
Node<K, V>* parent = NULL;
while (cur!=NULL)
{
parent = cur;
if (cur->_key > key)
cur = cur->_left;
else if (cur->_key < key)
cur = cur->_right;
else
return false;
}
cur = new Node<K, V>(key, val);
if (parent->_key > key)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
while (parent!=NULL)
{
if (cur == parent->_left)
parent->_bf++;
else
parent->_bf--;
if (parent->_bf == 0)
break;
else if (parent->_bf == -1 || parent->_bf == 1)
{
cur = parent;
parent = parent->_parent;
}
else
{
if (parent->_bf == 2)
{
if (cur->_bf == 1)
rotateLL(parent);
else
rotateLR(parent);
}
else
{
if (cur->_bf == -1)
rotateRR(parent);
else
rotateRL(parent);
}
break;
}
}
return true;
}
}
|
1.4.1 LL型不平衡（单旋转）
插入前左子树高度比右子树高度高 1，然后在左子树的左侧插入一个新的元素，只需要一次 右单旋 就可以转为平衡搜索树。具体操作如下，根节点A的左孩子B转换为新的根节点，B的右孩子转换为A的左孩子
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
| template <class K, class V>
void avlTree<K, V>::rotateLL(Node<K, V>* parent)
{
Node<K, V>* subL = parent->_left;
Node<K, V>* subLR = subL->_right;
Node<K, V>* ppNode = parent->_parent;
parent->_left = subLR;
if (subLR != NULL)
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = NULL;
}
else
{
if (ppNode->_right == parent)
{
ppNode->_right = subL;
}
else
{
ppNode->_left = subL;
}
subL->_parent = ppNode;
}
subL->_bf = 0;
parent->_bf = 0;
}
|
1.4.2 RR型不平衡（单旋转）
插入前右子树高度比左子树高度高 1，然后在右子树的右侧插入一个新的元素，只需要一次 左单旋 就可以转为平衡搜索树。具体操作如下，根节点A的右孩子B转换为新的根节点，B的左孩子转换为A的右孩子
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
| template <class K, class V>
void avlTree<K, V>::rotateRR(Node<K, V>* parent)
{
Node<K, V>* subR = parent->_right;
Node<K, V>* subRL = subR->_left;
Node<K, V>* pParent = parent->_parent;
parent->_right = subRL;
if (subRL != NULL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
_root->_parent = NULL;
}
else
{
if (pParent->_left = parent)
pParent->_left = subR;
else
pParent->_right = subR;
subR->_parent = pParent;
}
parent->_bf = 0;
subR->_bf = 0;
}
|
1.4.3 LR型不平衡（双旋转）
左子树高度更高的情况下，在左子树的右侧插入一个节点。首先进行一次 左单旋 ，将它转换为LL型不平衡，然后进行一次 右单旋 转换为平衡搜索树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| template <class K, class V>
void avlTree<K, V>::rotateLR(Node<K, V>* parent)
{
Node<K, V>* subL = parent->_left;
Node<K, V>* subLR = subL->_right;
int bf = subLR->_bf;
rotateRR(parent->_left);
rotateLL(parent);
if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
}
|
1.4.4 RL型不平衡（双旋转）
与LR型不平衡类似，这里直接给出代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| template <class K, class V>
void avlTree<K, V>::rotateRL(Node<K, V>* parent)
{
Node<K, V>* subR = parent->_right;
Node<K, V>* subRL = subR->_left;
int bf = subRL->_bf;
rotateLL(parent->_right);
rotateRR(parent);
if (bf == 1)
{
subR->_bf = 0;
parent->_bf = -1;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
}
|
2. 红黑树（red-black tree）
2.1 基本概念
红黑树是一棵扩充二叉树，每个空指针用一个外部节点来代替，除此之外还有以下性质
- 根节点和外部节点颜色都是黑色
- 在根节点到外部节点的路径上，没有连续两个节点是红色
- 在所有根节点到外部节点的路径上，黑色节点的数目都相同
红黑树一个节点的阶（rank）：从该节点到一外部节点的路径上黑色节点的数量
红黑树最大的高度是2log2(n+1)
2.2 RBT的搜索
与普通的搜索树相同，根据 theKey 不断向左孩子或右孩子移动寻找即可，时间复杂度为O(logn)
2.3 RBT的插入
我们的插入目标实际上是，和普通搜索树一样插入一个元素，然后再让它额外满足红黑树的性质。变色处理仅仅在父节点为红色是才会触发，本质上是在满足没有两个相同节点是红色，接下来回溯处理是为了满足黑色节点。
2.3.1 情况一：变色处理
这种情况是最简单的情况，如果插入节点的父节点和叔叔节点（父亲的对称孩子）是红色，则只需要进行变色处理
循环处理直到根节点为止，最后将根节点变为黑色结束
2.3.2 情况二：单旋加变色处理
如果新插入节点的父节点红色，叔叔不存在或为黑色，并且新插入节点在外侧（外侧单璇）
- 进行一次单旋转
- 把父亲节点更改为黑色，曾祖父节点更改为红色（最后这个三角形是黑色连两个红色）
2.3.3 情况三：双旋加变色处理
如果新插入节点父节点为红色，叔叔节点不存在或为黑色，并且新插入节点在内侧（内侧双璇）
- 对父亲节点进行一次单旋转
- 对曾祖父节点进行一次单旋转
- 将新插入节点修改为黑色，曾祖父节点修改为红色（最后这个三角形是黑色连两个红色）
下面是一个例子，首先插入新的红色元素26。因为该元素与父节点都为红色，违反了不能有两个红色的规则，并且它的叔叔节点为红色，符合情况一，进行调整：将他的父节点与叔叔节点修改为黑色，曾祖父节点修改为红色；此时元素28和元素30都为红色，违反了不能有两个红色的规则，并且它的叔叔节点为黑色，且该节点在内侧，符合情况三，需要进行两次单旋调整。
2.3.4 RBT插入的实现
2.3.4.1 对外暴露的插入函数
1
2
3
4
5
6
7
8
9
10
| template <class K, class V>
bool RBTree<K, V>::insert(K key, V val)
{
RBTNode<K, V>* z = NULL;
if ((z = new RBTNode<K, V>(key, val, RED, NULL, NULL, NULL)) == NULL)
return false;
return insert(this->_root, z);
}
|
2.3.4.2 按照普通的搜索树进行插入操作
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
| template <class K, class V>
bool RBTree<K, V>::insert(RBTNode<K, V>*& root, RBTNode<K, V>* node)
{
if (root == NULL)
{
node->_color = BLACK;
root = node;
return true;
}
else
{
RBTNode<K, V>* cur = root;
RBTNode<K, V>* parent = NULL;
while (cur != NULL)
{
parent = cur;
if (node->_key < cur->_key)
cur = cur->_left;
else if (node->_key > cur->_key)
cur = cur->_right;
else
return false;
}
if (parent->_key > node->_key)
{
parent->_left = node;
node->_parent = parent;
}
else
{
parent->_right = node;
node->_parent = parent;
}
return insertFixUp(root, node);
}
}
|
2.3.4.3 插入完成后的颜色修正
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
| template <class K, class V>
bool RBTree<K, V>::insertFixUp(RBTNode<K, V>*& root, RBTNode<K, V>* node)
{
RBTNode<K, V>* parent, * grandparent, * cur;
cur = node;
parent = cur->_parent;
while (parent && rb_is_red(parent))
{
grandparent = parent->_parent;
if (parent == grandparent->_left)
{
RBTNode<K, V>* uncle = grandparent->_right;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(grandparent);
cur = grandparent;
parent = cur->_parent;
}
else
{
if (parent->_left == cur)
{
rightRotate(grandparent);
rb_set_black(parent);
rb_set_red(grandparent);
}
else
{
leftRotate(parent);
rightRotate(grandparent);
rb_set_black(cur);
rb_set_red(grandparent);
}
break;
}
}
else
{
RBTNode<K, V>* uncle = grandparent->_left;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(grandparent);
cur = grandparent;
parent = cur->_parent;
}
else
{
if (parent->_right == cur)
{
leftRotate(grandparent);
rb_set_black(parent);
rb_set_red(grandparent);
}
else
{
rightRotate(parent);
leftRotate(grandparent);
rb_set_black(cur);
rb_set_red(grandparent);
}
}
}
}
rb_set_black(root);
return true;
}
|
Author:
mxwu
Permalink:
https://mingxuanwu.com/2023/10/18/202310181024/
License:
Copyright (c) 2023 CC-BY-NC-4.0 LICENSE
