??博客代碼已上傳至gitee：https://gitee.com/byte-binxin/cpp-class-code
概念
二叉搜索樹雖可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當(dāng)于在順序表中搜索元素，效率低下。因此，兩位俄羅斯的數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis在1962年發(fā)明了一種解決上述問題的方法：當(dāng)向二叉搜索樹中插入新結(jié)點(diǎn)后，如果能保證每個結(jié)點(diǎn)的左右子樹高度之差的絕對值不超過1(需要對樹中的結(jié)點(diǎn)進(jìn)行調(diào)整)，即可降低樹的高度，從而減少平均搜索長度。
- 它的左右子樹都是AVL樹
- 左右子樹高度之差的絕對值（也叫平衡因子）不超過1
- 我規(guī)定：平衡因子（balance factor）= 右子樹高度 - 左子樹高度（后面這樣實(shí)現(xiàn)）
AVL樹的實(shí)現(xiàn)
AVL樹的節(jié)點(diǎn)定義
這里節(jié)點(diǎn)是一個三叉鏈，里面存放了元素的數(shù)據(jù)和該節(jié)點(diǎn)此時的平衡因子。不管今后我們進(jìn)行什么操作，都要維持這里的平衡因子的絕對值不超過1。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
template<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) {}}; |
AVL樹的插入
方法概述
第一步： 我們先按照二叉搜索樹樹插入節(jié)點(diǎn)的方式，插入節(jié)點(diǎn)（這一步很簡單，上一篇博客介紹過）
第二步： 更新平衡因子，更新平衡因子的過程是一個難點(diǎn)，下面我給大家分析一下整個過程
平衡因子的調(diào)節(jié)
正常情況
實(shí)際上，我們應(yīng)該能夠發(fā)現(xiàn)，插入一個節(jié)點(diǎn)后，它之后影響它祖先的平衡因子（可能是所有祖先，也可能是一部分祖先），下面就是一個分析過程：
第一步： 判斷父親節(jié)點(diǎn)是否存在，不存在直接結(jié)束，如果存在，且插入節(jié)點(diǎn)是它的左孩子，那么父親節(jié)點(diǎn)的平衡因子就減1，如果是父親的右，父親的平衡因子就加1。然后對父親節(jié)點(diǎn)的平衡因子進(jìn)行檢索。
第二步： 繼續(xù)對父親節(jié)點(diǎn)的平衡因子進(jìn)行檢索，平衡因子會有一下三種情況
第一種情況： 此時父親的平衡因子為0，則說明插入前父親的平衡因子為1或-1，缺少左節(jié)點(diǎn)或右節(jié)點(diǎn)插入后，插入的節(jié)點(diǎn)已經(jīng)補(bǔ)齊了左節(jié)點(diǎn)或右節(jié)點(diǎn)，整體高度不變，對上層無影響，不需要繼續(xù)調(diào)節(jié)。下面是一個演示圖：
第二種情況 此時父親節(jié)點(diǎn)的平衡因子為-1或1，則說明插入前父親的平衡因子為0，插入后增加了一個左節(jié)點(diǎn)或右節(jié)點(diǎn)，整體高度增加1，對上層有影響，繼續(xù)迭代更新祖先的平衡因子。下面是一個演示圖：
第三種情況： 此時父親節(jié)點(diǎn)的平衡因子為-2或2，則說明插入前父親的平衡因子為-1或1，多了一個左節(jié)點(diǎn)或一個右節(jié)點(diǎn)，插入后增加了一個左節(jié)點(diǎn)或右節(jié)點(diǎn)，此時多了兩個左節(jié)點(diǎn)和右節(jié)點(diǎn)，這棵子樹一邊已經(jīng)被拉高了，此時這棵子樹不平衡了，需要旋轉(zhuǎn)處理。下面是一個演示圖：
旋轉(zhuǎn)處理（出現(xiàn)了不平衡子樹）
旋轉(zhuǎn)有四種情況：
1.左單旋（新插入的節(jié)點(diǎn)在右子樹的右側(cè)）
具體步驟： 讓subR的左孩子成為parent的右孩子，然后讓parent成為subR的左孩子，最后把兩個節(jié)點(diǎn)的平衡因子修改為0.
先畫一個具像圖給大家演示如何進(jìn)行這個操作（下面是一部分失衡的子樹）：
再畫一個抽像圖來演示：
代碼實(shí)現(xiàn)如下：
|
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
|
// 左單旋 bf為2 右邊高，把上面的壓下來放到左邊void RotateL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left; // 1.先讓把subR的左邊（可能為空也可能不為空）作為parent的右邊 parent->_right = subRL; // 2.如果subRL不為空，就讓subRL的父指針指向parent if (subRL) subRL->_parent = parent; // 3.先記錄parent的父節(jié)點(diǎn)的位置，然后把parent作為subR的左邊 Node* ppNode = parent->_parent; subR->_left = parent; // 4.parent的父指針指向subR parent->_parent = subR; // 5.如果ppNode為空==>說明subR現(xiàn)在是根節(jié)點(diǎn)，就讓subR的父指針指向nullptr // 不是根節(jié)點(diǎn)就把subR的父指針指向parent的父節(jié)點(diǎn)，parent的父節(jié)點(diǎn)（左或右）指向subR if (ppNode == nullptr) { // 更新根節(jié)點(diǎn) _root = subR; subR->_parent = nullptr; } else { // 判斷parent是ppNode的左還是右 if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; subR->_parent = ppNode; } // 6.把parent和subR的平衡因子更新為0 subR->_bf = parent->_bf = 0;} |
2.右單旋 （新節(jié)點(diǎn)插入到較高左子樹的左側(cè)）
具體步驟： 讓subL的右孩子成為parent的左孩子，然后讓parent成為subL的右孩子，最后把兩個節(jié)點(diǎn)的平衡因子修改為0.
先畫一個具像圖給大家演示如何進(jìn)行這個操作（下面是一部分失衡的子樹）：
在給大家演示一下抽象圖：
代碼實(shí)現(xiàn)如下：
|
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
|
// 右單旋 bf為-2 左邊高，把上面的壓下來放到右邊void RotateR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right; // 1.先讓把subL的右邊（可能為空也可能不為空）作為parent的左邊 parent->_left = subLR; // 2.如果subLR不為空，就讓subLR的父指針指向parent if (subLR) subLR->_parent = parent; // 3.先記錄parent的父節(jié)點(diǎn)的位置，然后把parent作為subL的右邊 Node* ppNode = parent->_parent; subL->_right = parent; // 4.parent的父指針指向subL parent->_parent = subL; // 5.如果ppNode為空==>說明subR現(xiàn)在是根節(jié)點(diǎn)，就讓subL的父指針指向nullptr // 不是根節(jié)點(diǎn)就把subL的父指針指向parent的父節(jié)點(diǎn)，parent的父節(jié)點(diǎn)（左或右）指向subL if (ppNode == nullptr) { // 更新根節(jié)點(diǎn) _root = subL; subL->_parent = nullptr; } else { // 判斷parent是ppNode的左還是右 if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; subL->_parent = ppNode; } // 6.把parent和subL的平衡因子更新為0 subL->_bf = parent->_bf = 0;} |
3.右左雙旋（新節(jié)點(diǎn)插入在較高右子樹左側(cè)，這里和第一種情況的區(qū)別就是前者是直線，后者是折線）
具體步驟 先對subR進(jìn)行一個右單旋，然后對parent進(jìn)行左單旋，修改平衡因子，有三種改法。
三個節(jié)點(diǎn)從左至右的三個節(jié)點(diǎn)一次是：parent、subRL和subR。
如果subRL的平衡因子為0，就將它們依次改為0，0, 0；
如果subRL的平衡因子為1，就將它們依次改為-1，0, 0；
如果subRL的平衡因子為-1，就將它們依次改為0，0, 1。
先看具像圖：
再看一個抽象圖（兩種情況）：
subRL的bf為1
subRL的bf為-1
代碼實(shí)現(xiàn)如下：
|
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
|
// 右左旋轉(zhuǎn)==>parent->_bf==2&&cur->_bf==-1void RotateRL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf;// 保留subRL的平衡因子的值，方便知道新插入的節(jié)點(diǎn)是在subRL的左子樹還是右子樹 // 旋轉(zhuǎn) 先對subR進(jìn)行右旋轉(zhuǎn)，再對parent進(jìn)行左旋轉(zhuǎn) RotateR(subR); RotateL(parent); // 從左到右 parent subRL subR if (bf == -1)// subRL的左子樹 bf: 0 0 1 { parent->_bf = 0; subRL->_bf = 0; subR->_bf = 1; } else if (bf == 1)// subRL的右子樹 bf: -1 0 0 { parent->_bf = -1; subRL->_bf = 0; subR->_bf = 0; } else if (bf == 0) { parent->_bf = 0; subRL->_bf = 0; subR->_bf = 0; }} |
4.左右雙旋（新節(jié)點(diǎn)插入在較高右子樹左側(cè)，這里和第一種情況的區(qū)別就是前者是直線，后者是折線）
具體步驟先對subL進(jìn)行一個左單旋，然后對parent進(jìn)行右單旋，修改平衡因子，有三種改法。三個節(jié)點(diǎn)從左至右的三個節(jié)點(diǎn)一次是：subL、subLR和parent。（和上面的類似，這樣有助于我們記住平衡因子的調(diào)整，同時我們也可以畫簡圖理解記憶）
如果subLR的平衡因子為0，就將它們依次改為0，0, 0；
如果subLR的平衡因子為1，就將它們依次改為-1，0, 0；
如果subLR的平衡因子為-1，就將它們依次改為0，0, 1。
先看具像圖：
再看一個抽象圖（也有兩種情況）：
subLR的bf為-1
subLR的bf為1
代碼實(shí)現(xiàn)如下：
|
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
|
// 左右旋轉(zhuǎn)==>parent->_bf==-2&&cur->_bf==1void RotateLR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf;// 保留subLR的平衡因子的值，方便知道新插入的節(jié)點(diǎn)是在subLR的左子樹還是右子樹 // 旋轉(zhuǎn) 先對subL進(jìn)行左旋轉(zhuǎn)，再對parent進(jìn)行右旋轉(zhuǎn) RotateL(subL); RotateR(parent); // 從左到右 subL subLR parent if (bf == -1)// subLR的左子樹 bf: 0 0 1 { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 1; } else if (bf == 1)// subLR的右子樹 bf: -1 0 0 { subL->_bf = -1; subLR->_bf = 0; parent->_bf = 0; } else if (bf == 0) { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 0; }} |
插入代碼實(shí)現(xiàn)
插入的步驟也就是如上面說的一樣，下面的代碼我們通過迭代實(shí)現(xiàn)。
代碼實(shí)現(xiàn)如下：
|
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
|
bool Insert(const pair<K, V>& kv){ // 先按照二叉搜索數(shù)一樣插入元素 // 無節(jié)點(diǎn)是插入 if (_root == nullptr) { _root = new Node(kv); return true; } // 有節(jié)點(diǎn)時插入 Node* parent = nullptr; Node* cur = _root; while (cur) { parent = cur; // 小于往左走 if (kv.first < cur->_kv.first) { cur = cur->_left; } // 大于往右走 else if (kv.first > cur->_kv.first) { cur = cur->_right; } else { // 找到了，就返回false return false; } } cur = new Node(kv); // 判斷cur應(yīng)該插在parent的左還是右 // 小于在左，大于在右 if (cur->_kv.first < parent->_kv.first) { parent->_left = cur; cur->_parent = parent; } else { parent->_right = cur; cur->_parent = parent; } // 更新parent的平衡因子 // 節(jié)點(diǎn)的插入只會影響cur的祖先的平衡因子（不是所有的，是一部分，分情況） while (parent) { // 更新parent的平衡因子 // cur在parent的左，parent->_bf-- // cur在parent的右，parent->_bf++ if (cur == parent->_left) parent->_bf--; else parent->_bf++; // bf 可能為 -2、-1、0、1、2 // 如果平衡因子為0，說明更新之前，parent的bf為-1或1，現(xiàn)在補(bǔ)齊了左節(jié)點(diǎn)或右節(jié)點(diǎn)，bf==0，對上層無影響 // 如果平衡因子為-1或1，說明更新之前，parent的bf為0，現(xiàn)在增加了一個左節(jié)點(diǎn)或有節(jié)點(diǎn)，bf==-1 || bf==1,對上層有影響 // 如果平衡因子為-2或2，說明更新之前，parent的bf為-1或1，現(xiàn)在往左（右）節(jié)點(diǎn)補(bǔ)了左（右）節(jié)點(diǎn)，也就是一邊 // 拉高了，樹不平衡了，需要用左旋轉(zhuǎn)或右旋轉(zhuǎn)來進(jìn)行調(diào)整 if (parent->_bf == 0) { // 對上層無影響，退出 break; } else if (parent->_bf == -1 || parent->_bf == 1) { // 對上層有影響，迭代更新 cur = parent; parent = parent->_parent; } else { // 平衡樹出現(xiàn)了問題，需要調(diào)整 // 1.右邊高，左旋轉(zhuǎn)調(diào)整 if (parent->_bf == 2) { // 如果是一條直線==>左旋轉(zhuǎn)即可 // 如果是一條折線==>右左旋轉(zhuǎn) if (cur->_bf == 1) RotateL(parent); else if (cur->_bf == -1) RotateRL(parent); } // 2.左邊高，右旋轉(zhuǎn)調(diào)整 else if (parent->_bf == -2) { // 如果是一條直線==>右旋轉(zhuǎn)即可 // 如果是一條折線==>左右旋轉(zhuǎn) if (cur->_bf == -1) RotateR(parent); else if (cur->_bf == 1) RotateLR(parent); } // 調(diào)整后是平衡樹，bf為0，不需要調(diào)整了 break; } } return bool;} |
AVL樹的查找
查找的代碼和二叉搜索樹是一樣的，這里就不過多介紹。
代碼實(shí)現(xiàn)如下：
|
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
|
bool Find(const K& key){ if (_root == nullptr) return false; Node* cur = _root; while (cur) { // 小于往左走 if (key < cur->_kv.first) { cur = cur->_left; } // 大于往右走 else if (key > cur->_kv.first) { cur = cur->_right; } else { // 找到了 return true; } } return false;} |
AVL樹的刪除
方法概述
第一步： 我們先按照二叉搜索樹樹刪除節(jié)點(diǎn)的方式，刪除節(jié)點(diǎn)（這一步很簡單，上一篇博客介紹過）
第二步： 然后根據(jù)對應(yīng)刪除情況更新平衡因子，這里更新平衡因子的方法與插入的更新方法是相反的，下面我給大家分析一下整個過程
平衡因子的調(diào)節(jié)
正常情況
刪除節(jié)點(diǎn)后，如果刪除的節(jié)點(diǎn)為根節(jié)點(diǎn)，就結(jié)束。否則根據(jù)刪除節(jié)點(diǎn)為父節(jié)點(diǎn)的左右調(diào)整父節(jié)點(diǎn)的平衡因子。如果刪除節(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子，那么父親節(jié)點(diǎn)的平衡因子加1，否則減1。然后對父親節(jié)點(diǎn)進(jìn)行檢索。
有以下幾種情況：
第一種情況： 此時父親的平衡因子為0，則說明刪除前父親的平衡因子為1或-1，多出一個左節(jié)點(diǎn)或右節(jié)點(diǎn)，刪除節(jié)點(diǎn)后，左右高度相等，整體高度減1，對上層有影響，需要繼續(xù)調(diào)節(jié)。下面是一個演示圖：（如果此時3為根節(jié)點(diǎn)，那么也可以結(jié)束）
第二種情況： 此時父親的平衡因子為-1或1，則說明刪除前父親的平衡因子為0，左右高度相等，刪除節(jié)點(diǎn)后，少了一個左節(jié)點(diǎn)或右節(jié)點(diǎn)，但是整體高度不變，對上層無影響，不需要繼續(xù)調(diào)節(jié)。下面是一個演示圖：
第三種情況： 此時父親節(jié)點(diǎn)的平衡因子為-2或2，則說明刪除前父親的平衡因子為-1或1，多了一個左節(jié)點(diǎn)或一個右節(jié)點(diǎn)，刪除了一個右節(jié)點(diǎn)或左節(jié)點(diǎn)，此時多了兩個左節(jié)點(diǎn)和右節(jié)點(diǎn)，這棵子樹一邊已經(jīng)被拉高了，此時這棵子樹不平衡了，需要旋轉(zhuǎn)處理。下面是一個演示圖：
需要旋轉(zhuǎn)處理的幾種情況
這里我只分析右邊高的情況，左邊高和它對稱的，操作是相同的。
情況一：
操作方法： 對parent進(jìn)行左旋轉(zhuǎn)，因?yàn)閟ubR的平衡因子為0，需要繼續(xù)檢索，然后繼續(xù)迭代，把cur迭代sub的位置，parent到cur的父親的位置
具像圖：
抽象圖：
情況二：
操作方法： 對parent進(jìn)行左旋，然后修改平衡因子，把subR的平衡因子改為-1，parent的平衡因子改為1，因?yàn)閟ubR的平衡因子為-1，所以無需迭代，直接結(jié)束
具像圖：
抽象圖：
情況三：
操作方法： 對subR進(jìn)行右旋，然后對parent進(jìn)行左旋，此時subR的平衡因子為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
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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
|
bool Erase(const K& key){ if (_root == nullptr) return false; // 有節(jié)點(diǎn)時插入 Node* parent = nullptr; Node* cur = _root; while (cur) { // 小于往左走 if (key < cur->_kv.first) { parent = cur; cur = cur->_left; } // 大于往右走 else if (key > cur->_kv.first) { parent = cur; cur = cur->_right; } else { // 找到了 // 1.左邊為空，把parent指向cur的右 // 2.右邊為空，把parent指向cur的左 // 3.左右都不為空，用右子樹的最左邊的節(jié)點(diǎn)（最小節(jié)點(diǎn)）的值替換要刪除的節(jié)點(diǎn)，然后轉(zhuǎn)換為用1的情況刪除該節(jié)點(diǎn) if (cur->_left == nullptr) { if (cur == _root) { _root = cur->_right; delete cur; break; } else { if (parent->_left == cur) { parent->_left = cur->_right; parent->_bf++; } else { parent->_right = cur->_right; parent->_bf--; } } if (parent->_bf != -1 && parent->_bf != 1) AfterEraseUpdateBf(parent); delete cur; } else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; delete cur; break; } else { if (parent->_left == cur) { parent->_left = cur->_left; parent->_bf++; } else { parent->_right = cur->_left; parent->_bf--; } } if (parent->_bf != -1 && parent->_bf != 1) AfterEraseUpdateBf(parent); delete cur; } else { Node* rightMinParent = cur; Node* rightMin = cur->_right;// 先去右子樹 while (rightMin->_left) { rightMinParent = rightMin; rightMin = rightMin->_left;// 一種往左走 } cur->_kv = rightMin->_kv; // 替代刪除 // 刪除minNode 第一種情況：左節(jié)點(diǎn)為空 if (rightMinParent->_left == rightMin) { rightMinParent->_left = rightMin->_right; rightMinParent->_bf++; } else { rightMinParent->_right = rightMin->_right; rightMinParent->_bf--; } if (rightMinParent->_bf != -1 && rightMinParent->_bf != 1) AfterEraseUpdateBf(rightMinParent); delete rightMin; } return true; } } return false;}void AfterEraseUpdateBf(Node* parent){ if (parent == nullptr) return; Node* cur = parent; goto first; while (parent) { // 更新parent的平衡因子 // cur在parent的左，parent->_bf++ // cur在parent的右，parent->_bf-- if (cur == parent->_left) parent->_bf++; else parent->_bf--; // bf 可能為 -2、-1、0、1、2 // 如果平衡因子為0，說明更新之前，parent的bf為-1或1，現(xiàn)在刪掉了左節(jié)點(diǎn)或右節(jié)點(diǎn)，整體高度變了，對上層有影響 // 如果平衡因子為-1或1，說明更新之前，parent的bf為0，現(xiàn)在刪掉了一個左節(jié)點(diǎn)或有節(jié)點(diǎn)，整體高度不變，對上層無影響 // 如果平衡因子為-2或2，說明更新之前，parent的bf為-1或1，現(xiàn)在往左（右）節(jié)點(diǎn)補(bǔ)了左（右）節(jié)點(diǎn)，也就另一邊 // 拉高了，樹不平衡了，需要用左旋轉(zhuǎn)或右旋轉(zhuǎn)來進(jìn)行調(diào)整 first: if (parent->_bf == 0) { // 對上層有影響，迭代更新 // 如果parent是根節(jié)點(diǎn)就結(jié)束 if (parent->_parent == nullptr) break; cur = parent; parent = parent->_parent; } else if (parent->_bf == -1 || parent->_bf == 1) { // 對上層無影響，退出 break; } else { // 平衡樹出現(xiàn)了問題，需要調(diào)整 // 1.右邊高，左旋轉(zhuǎn)調(diào)整 if (parent->_bf == 2) { // 如果是一條直線==>左旋轉(zhuǎn)即可 // 如果是一條折線==>右左旋轉(zhuǎn) if (parent->_right->_bf == 1) { RotateL(parent); cur = parent->_parent; parent = cur->_parent; continue; } else if (parent->_right->_bf == -1)// 調(diào)整后 p sL s 如果sL是1或-1可以退出 { Node* s = parent->_right; Node* sL = s->_left; RotateRL(parent); // 不平衡向上調(diào)整 注意：bug1（以為調(diào)整完就是1或-1了，其實(shí)這里不是，畫圖思考一下） //if (sL->_bf != 1 && sL->_bf != -1) { cur = sL; parent = cur->_parent; continue; } } else if (parent->_right->_bf == 0)// 旋轉(zhuǎn)后平衡因子要修改，畫圖感受 parent: 1 parent->_parent:- 1 { RotateL(parent); parent->_bf = 1; parent->_parent->_bf = -1; } } // 2.左邊高，右旋轉(zhuǎn)調(diào)整 else if (parent->_bf == -2) { // 如果是一條直線==>右旋轉(zhuǎn)即可 // 如果是一條折線==>左右旋轉(zhuǎn) if (parent->_left->_bf == -1) { RotateR(parent); cur = parent->_parent;// bug2 cur要變成這個位置是因?yàn)檫x擇后父親的位置變了，畫圖 parent = cur->_parent; continue;//parent不是-1或1就繼續(xù) } else if (parent->_left->_bf == 1)// 調(diào)整后 s sR p 如果sL是1或-1可以退出 { Node* s = parent->_left; Node* sR = s->_right; RotateLR(parent); // 不平衡向上調(diào)整 為0時如果parent為根 //if (sR->_bf != 1 && sR->_bf != -1) { cur = sR; parent = cur->_parent; continue; } } else if (parent->_left->_bf == 0)// 平衡因子要修改，畫圖感受 parent->_parent: 1 parent: -1 { RotateR(parent); parent->_parent->_bf = 1; parent->_bf = -1; } } // 調(diào)整后是平衡樹，bf為1或-1，不需要調(diào)整了 break; } }} |
AVL樹的測試代碼
下面是驗(yàn)證是否為AVL樹的代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
int _Height(Node* root){ if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return 1 + max(leftHeight, rightHeight);}bool _IsBalanceTree(Node* root){ if (root == nullptr) return true; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return rightHeight - leftHeight == root->_bf && abs(rightHeight - leftHeight) < 2 && _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);} |
實(shí)例演示：
|
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
|
void TestAVLTree1(){ AVLTree<int, int> at; srand((size_t)time(nullptr)); // int a[] = { 4,3,5,3,1,2,7 }; // int a[] = { 1,2,3,4,5,6,7,8,9 }; // int a[] = { 2,4,6,3,5,1,9,10,8,7 }; // int a[] = { 4,2,3,5 }; // int a[] = { 16,3,7,11,9,26,18,14,15 }; // int a[] = { 4,2,6,1,3,5,15,7,16,14 }; // int* a = new int[10000]; /*int i = 1; for (auto& e : a) { e = i++; }*/ vector<int> a; for (size_t i = 0; i < 13; ++i) { // a.push_back(rand()); a.push_back(13); } for (auto e : a) { int begin = clock(); pair<AVLTreeNode<int, int>*, bool> ret = at.Insert(make_pair(e, e)); int end = clock(); // cout << ret.first->_kv.second << endl; // cout << ret.first->_kv.second << ":" << ret.second << endl; cout << "插入 " << e << " 后變化 --> Height: " << at.Height() << " 是否為AVLTree：" << at.IsBalanceTree(); cout << " 用時: " << end - begin << "ms" << endl; } cout << "------------------------------------------------------" << endl; // at.InOrder(); for (auto e : a) { if (e == 11478) { int a = 0; } int begin = clock(); at.Erase(e); int end = clock(); cout << "刪除 " << e << " 后變化 --> Height: " << at.Height() << " 是否為AVLTree：" << at.IsBalanceTree(); cout << " 用時: " << end - begin << "ms" << endl; } at.InOrder();} |
代碼運(yùn)行結(jié)果如下：
總結(jié)
AVL樹的全部內(nèi)容就介紹到這，圖畫了一下午，創(chuàng)造不易，感謝支持，下一篇博客更新紅黑樹的相關(guān)內(nèi)容，喜歡的話，歡迎點(diǎn)贊支持~
到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)AVL樹全面分析的文章就介紹到這了,更多相關(guān)C++ AVL樹內(nèi)容請搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://blog.csdn.net/weixin_58450087/article/details/123090533
