map、set（底层结构）——C++

4. 底层结构

map/multimap/set/multiset这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

 

4.1 AVL 树

高度平衡二叉搜索树，是以人名命名的

4.1.1 AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)（非必须）
  平衡因子 = 右子树高度-左子树高度

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在
$O(lo{g}_{2}n)$，搜索时间复杂度O($lo{g}_{2}n$)

平衡因子需要三叉链
但是旋转的时候也会变复杂

 

4.1.2AVL树节点的定义

t

emplate<class K, class V>
struct AVLTreeNode
{
   
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;

pair<K, V> _kv;
int _bf;  // balance factor

AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{
   }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

 

4.1.3 AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子

更新平衡因子的规则：
1.新增在右，parent->bf++;新增在左，parent->bf–
 
2.更新后，parent->bf == 1 or -1,说明parent插入前的平衡因子是0，说明左右子树高度相等，插入后有一边高，parent高度变了，需要继续往上更新
 
3.更新后，parent->bf == 0，说明parent插入前的平衡因子是1或-1，说明左右子树一边高一边低，插入后两边一样高，插入填上了矮的那边，parent所在子树高度不变，不需要继续往上更新
 
4.更新后，parent->bf == 2 or -2，说明parent插入前的平衡因子是1或-1，已经到达平衡临界值，插入后变成2或-2，打破平衡，parent所在子树需要旋转处理
 
5.更新后，parent->>2 or <-2的值，不可能，如果存在，说明插入前的就不是AVL数，需要去检查之前操作的问题

//插入
cur = new Node(kv);
//链接
if (parent->_kv.first < kv.first)
{
   
//插入的值大就插入右边
parent->_right = cur;
}
else
{
   
//插入的值小就插入左边
parent->_left = cur;
}
//三叉链还要考虑parent
cur->_parent = parent;


// 控制平衡
// 1、更新平衡因子
while (parent)
{
   
if (cur == parent->_right)
{
   
parent->_bf++;
}
else
{
   
parent->_bf--;
}

if (parent->_bf == 0)
{
   
break;
}
else if (abs(parent->_bf) == 1)
{
   
                                //往上更新
parent = parent->_parent;
cur = cur->_parent;
}
else if (abs(parent->_bf) == 2)
{
   
// 说明parent所在子树已经不平衡了，需要旋转处理
if (parent->_bf == 2 && cur->_bf == 1)
{
   
RotateL(parent);
}
else if ((parent->_bf == -2 && cur->_bf == -1))
{
   
RotateR(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
   
RotateLR(parent);
}

break;
}
else
{
   
assert(false);
}
}

return true;
}
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

 
 

4.1.4 AVL树的旋转

原则：

1. 旋转成平衡树
2. 保持搜索树的规则

 else if (abs(parent->_bf) == 2)
{
   
// 说明parent所在子树已经不平衡了，需要旋转处理
if (parent->_bf == 2 && cur->_bf == 1)
{
   
RotateL(parent);
}
else if ((parent->_bf == -2 && cur->_bf == -1))
{
   
RotateR(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
   
RotateLR(parent);
}
                                 else if (parent->_bf == 2 && cur->_bf == -1)
{
   
RotateRL(parent);
}

break;
}

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

 

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

 

1. 新节点插入较高左子树的左侧—左左：右单旋

a、b、c是h >= 0的平衡树
左边高，往右边旋转
只有parent和subL的平衡因子受影响——全变为0

void RotateR(Node* parent)
{
   
Node* subL = parent->_left;
Node* subLR = subL->_right;

parent->_left = subLR;
if (subLR)
{
   
subLR->_parent = parent;
}

Node* ppNode = parent->_parent;

subL->_right = parent;
parent->_parent = subL;

if (_root == parent)
{
   
_root = subL;
subL->_parent = nullptr;
}
else
{
   
if (ppNode->_left == parent)
{
   
ppNode->_left = subL;
}
else
{
   
ppNode->_right = subL;
}

subL->_parent = ppNode;
}

subL->_bf = parent->_bf = 0;
}
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

 

2. 新节点插入较高右子树的右侧—右右：左单旋

parent是整棵树的根
parent是子树的根
要动六个指针
只有parent和subR的平衡因子受影响——全变为0

void RotateL(Node* parent)
{
   
Node* subR = parent->_right;
Node* subRL = subR->_left;

parent->_right = subRL;
if (subRL)
subRL->_parent = parent;

Node* ppNode = parent->_parent;

subR->_left = parent;
parent->_parent = subR;

if (_root == parent)
{
   
_root = subR;
subR->_parent = nullptr;
}
else
{
   
if (ppNode->_left == parent)
{
   
ppNode->_left = subR;
}
else
{
   
ppNode->_right = subR;
}

subR->_parent = ppNode;
}

subR->_bf = parent->_bf = 0;
}
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

 

单旋（1、2）：a、b、c是高度为h的AVL子树，h>=0; 旋转的价值和意义：

• 平衡 降高度（高度恢复到插入之前的样子）
• 新节点插入较高左子树的右侧—左右：先左单旋再右单旋

 

3. 新节点插入较高左子树的右侧—左右：先左单旋再右单旋

void RotateLR(Node* parent)
{
   
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;

RotateL(parent->_left);
RotateR(parent);

subLR->_bf = 0;
if (bf == 1)
{
   
parent->_bf = 0;
subL->
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15