1.AVL树概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下,
所以在此基础上提出解决办法：
当向二叉搜索树中插入新节结点时，如果能保证每个节点的左右子树高度之差的绝对值不超过1即可降低树的高度，从而减少平均搜索长度
AVL树又称平衡二叉搜索树

2. AVL树性质

AVL树的性质：
1.它的左右子树都是AVL树
2.左右子树高度之差(平衡因子)的绝对值不超过1(1/0/-1)
平衡因子=右子树高度-左子树高度

3.AVL树的实现

在实现结构与插入功能时，与二叉搜索树有很多相似的地方 ：二叉搜索树
所以一部分关于二叉搜索树的地方就不详细说了

---

与二叉搜索树定义结构不同的是，多了一个父节点parent以及平衡因子bf

insert

insert的实现前半部分与二叉搜索树的insert实现大部分相同

---

parent的右子树连接新节点为例，出while循环后，需要反向链接父节点，而此时的父节点就为刚才记录cur前一个节点的parent

---

插入情况分析

---

1.

若新增节点作为parent的右子树即cur==parent->right
parent的平衡因子+1 即 parent->bf++

---

若新增节点作为parent的左子树即cur==parent->left
parent的平衡因子 -1 即 parent->bf–

---

3.

若新增节点作为parent的左子树即cur==parent->left
parent的平衡因子-1 即 parent->bf–

---

若parent的平衡因子等于1或者-1 即第一种与第二种情况，说明parent所在子树变了，需要继续向上更新爷爷节点
为什么需要继续更新？
说明插入前parent的平衡因子为0，插入前左右高度相等，现在一边高1，高度变了

若parent的平衡因子等于2或者-2 ， 说明parent所在子树不平衡，需要以旋转的方式处理子树

若parent的平衡因子等于0， parent所在子树高度不变，就不需要向上更新，插入结束了
为什么插入结束了呢？
插入前parent的平衡因子是-1或者1，插入前一边高一边低，插入节点到矮的那边，高度不变

更新平衡因子

插入新增节点后，更新平衡因子
如果更新之后，平衡因子没有问题(绝对值<=1)，说明插入对树的平衡机构没有影响，不需要处理
如果更新之后，平衡出现问题，平衡结构受到影响(平衡因子为2/-2)，需要旋转
插入新增节点，会影响部分/整体祖先

旋转处理

旋转的原则：保持继续是搜索树
旋转的目的：左右均衡，降低高度

---

a/b/c分别代表高度为h的AVL子树
平衡因子=右子树深度-左子树深度

---

情况1——h=0

当h=0时，60的平衡因子：0-1=-1
30的平衡因子：2-0=2
由于平衡因子出现2，所以需要旋转

---

情况2——h=1

当h=2时，60的平衡因子:2-1=1，30的平衡因子:3-1=2
由于平衡因子出现2，所以需要旋转
在parent节点左右插入，都会引发平衡因子变为2

---

情况3——h=2

---

对于c来说，必定是x形状
假设c为y形状

在左子树新插入一个节点，那这颗子树的平衡因子变为-2，需要旋转，而不会去往上更新到30

---

若右子树插入一个节点，parent的平衡因子变为0，不需要往上更新到30

---

对于a和b，必定是x、y、z中的一种形状

假设abc都是x形状，则在c中插入节点，无论插入左边还是右边，都会导致parent的平衡因子为2或者-2

c的高度变化，必定引发旋转

---

在红框中的四个位置任意一边插入，30的平衡因子都会变为2/-2

虽然分为三种情况，但是旋转的规则是相同

左单旋

以h=1为例

左单旋的旋转方式：
把B变成30的右边，30变成60的左边，60变成整棵树的根

---

左单旋抽象图

父节点问题
把subR作为30的右子树时，需要更新sub的父节点为parent
把parent作为subR的左子树时，更新parent的父节点为subR

有可能当前旋转的是整棵树或者整棵树的一部分
设置一个ppnode，用于存放parent的父节点
若旋转一部分时，跟ppnode相连接，同时也要判断连接到左子树还是右子树
若旋转整棵树时，父节点置NULL，subR作为新的根

---

右单旋

在a处新增节点，使其高度变为h+1，造成旋转
右单旋的旋转方式：
b作为60的左边，60作为30的右边，30变成整棵树的根
右单旋h与左单旋一样，都有h为1、2、3的三种情况，只不过右单旋的插入节点在a处，其他的条件都是相同的

---

右单旋跟左单旋思想相同，
只不过把b作为60的左子树，再把60作为30的右子树
同样考虑父节点问题以及旋转整棵树或者部分子树旋转问题

---

在insert中判断左右单旋的条件

当parent的平衡因子为2并且cur的平衡因子为1时，为左单旋

---

当parent的平衡因子为-2并且cur的平衡因子为-1时，为右单旋

---

双旋转

抽象图

---

当h=0时，60作为新增节点

---

当h==1时，60的左右子树新增都会引用旋转

---

假设在左子树处新增节点

---

若h==2时

a/d是x/y/z中的任意一种
b/c的孩子位置的任意一点插入节点，都会引发旋转

左右双旋

当h==2时， 假设在b的右子树插入节点

将30进行左旋：30是parent的左子树
将b作为30的右子树，将30作为60的左子树，将60作为90的左子树

---

将60进行右旋：60作为整棵树新的根
将60的右子树作为90的左子树，将90作为60的右子树

---

假设在c的右子树插入新增节点

新增节点插入在b和c节点，各个位置的平衡因子是不一样的

---

当h=0时，左右双旋后，平衡因子与上述两个也是不同的

---

当subLR即60节点处的平衡因子为-1时，说明在b处插入新增节点，
双旋后 subl的平衡因子为0，subLR的平衡因子为0，parent的平衡因子为1

当subLR即60节点处的平衡因子为1时，说明在c处插入新增节点，
双旋后 subl的平衡因子为-1，subLR的平衡因子为0，parent的平衡因子为0

当subLR即60节点处的平衡因子为0时，说明在60即为新增节点，
双旋后 subl的平衡因子为0，subLR的平衡因子为0，parent的平衡因子为0

右左双旋

当h==0时，60作为新增节点

---

当h==1时，60的左右新增节点都会引发旋转

---

a/d是x/y/z中任意一个
b和c是一个节点的子树

---

b/c的四个孩子位置的任意一个位置新增节点，都会引发旋转

---

假设在c处新增节点

---

对于90进行右单旋，将c作为90的左子树，将90作为60的右子树

---

对30进行左单旋，将b作为30的右子树，将30作为60的左子树

插入引发双旋的场景

1.h==2时，c插入，c的高度变化为h

刚开始60的平衡因子为1

---

2…h==2时，b插入，b的高度变化为h

刚开始60的平衡因子为-1

---

3. h==1时，60本身就是新增节点

刚开始60的平衡因子为0

---

当subLR即60节点处的平衡因子为1时，说明在c处插入新增节点，
双旋后 subR的平衡因子为0，subRL的平衡因子为0，parent的平衡因子为-1

当subLR即60节点处的平衡因子为-1时，说明在b处插入新增节点，
双旋后 subR的平衡因子为1，subRL的平衡因子为0，parent的平衡因子为0

当subLR即60节点处的平衡因子为0时，说明在60即为新增节点，
双旋后 subR的平衡因子为0，subRL的平衡因子为0，parent的平衡因子为0

---

当parent的平衡因子为2，并且cur的平衡因子为-1时，为右左双旋

中序遍历

平衡树的中序遍历与搜索树的中序遍历基本一致，root->_kv.first 实际上代表的是kv中key值

如果不懂可以查看：二叉搜索树

判断一颗二叉树是否为平衡树

因为平衡因子是自己更新的，如果更新错了，那检查将无意义
所以通过高度差去判断

---

在height函数中，求出其左右子树高度，并返回左右子树高度大的加1 即当前树的高度

---

在_isbalance函数中，通过左右子树高度差的绝对值 ，判断是否为平衡树 ，即 高度差不超过2

---

在当前情况下，虽然左子树与右子树的高度差为1，
但是并不是平衡树，因为它的右子树节点6的高度差为2
所以还要判断子树是否符合平衡树

---

若平衡因子异常，虽然在当前判断平衡树是没有影响的，但是在后续插入判断时，使不该旋转的进行旋转了
所以需要判断下当前root的平衡因子是否与左右子树高度差相等，若不想等则平衡因子异常

---

整体代码

#include<iostream>
#include<cassert>
using namespace std;
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;//平衡因子

AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_kv(kv),
_bf(0)
{
}
};


template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
   public:
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;//用于记录cur的前一个节点
Node* cur = _root;
while (cur)
{
//若插入的值比当前树的值小 插入左边
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
//若插入的值比当前树的值大 插入右边
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
//若插入的值，在树中有相同的值 ，则插入失败
return false;
}
}
cur = new Node(kv);
//再次判断parent当前节点值与插入值大小
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
//cur的上一个节点即为 刚才的记录cur前一个节点的parent
cur->_parent = parent;



//更新平衡因子
while (parent)
{
//若插入节点在parent的右子树
if (cur == parent->_right)
{
parent->_bf++;
}
//若插入节点在parent的左子树
else
{
parent->_bf--;
}


if (parent->_bf == 1 || parent->_bf == -1)
{
//继续向上更新
parent = parent->_parent;
cur = cur->_parent;
}
//平衡因子为0，不需要向上更新
else if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//旋转
//1.让这颗子树平衡 2.降低子树高度
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);
}
else
{
assert(false);
}
//旋转后整颗树已经平衡了，就不需要在继续了
break;
}
}

return true;
}


void inorder()//中序遍历
{
_inorder(_root);
cout << endl;
}
//判断一颗二叉树是否为平衡树
bool isbalance()
{
return _isbalance(_root);
}
private:

int height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int leftH = height(root->_left);//左子树高度
int rightH = height(root->_right);//右子树高度
//返回左右子树高度大的加1
return leftH > rightH ? leftH + 1 : rightH + 1;
}
bool _isbalance(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftH = height(root->_left);
int rightH = height(root->_right);

if (rightH - leftH != root->_bf)
{
cout << root->_kv.first << "节点平衡因子异常" << endl;
return false;
 }
//判断最终绝对值是否小于2
return abs(leftH - rightH) < 2&&_isbalance(root->_left)&&_isbalance(root->_right);
}
 
void _inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_inorder(root->_left);
cout << root->_kv.first << " ";
_inorder(root->_right);
}
void RotateL(Node* parent)//左单旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;

parent->_right = subRL;
if (subRL != nullptr)
{
subRL->_parent = parent;
}
Node* ppnode = parent->_parent;//记录parent的前一个节点

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

if (ppnode == nullptr)//说明parent是根即代表整棵树
{
_root = subR;//subR作为新的根
_root->_parent = nullptr;//subR的父节点指向原来的parent,所以要置nullptr
}
else//说明旋转的是一部分，所以要跟ppnode相连接
{
if (ppnode->_left == parent)//若连接在左子树上
{
ppnode->_left = subR;
}
else//若连接在右子树上
{
ppnode->_right = subR;
}
subR->_parent = ppnode;//将subR父节点置为ppnode
}
parent->_bf = subR->_bf = 0;//平衡因子都为0
}

void RotateR(Node* parent)//右单旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR != nullptr)
{
subLR->_parent = parent;
}
Node* ppnode = parent->_parent;//记录parent的父节点
subL->_right = parent;
parent->_parent = subL;

if (ppnode == nullptr)//若旋转整棵树
{
_root = subL;
_root->_parent = nullptr;
}
else//若旋转整棵树的部分子树
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;//使subL的父节点为ppnode
}
parent->_bf = subL->_bf = 0;

}

void RotateLR(Node* parent)//左右双旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;//记录平衡因子，在后续单旋会置为0

//先对parent的左子树进行左单旋
RotateL(parent->_left);
//再对当前根进行右单旋
RotateR(parent);

if (bf == -1)//h==2时，在b处插入节点
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)//h==2时，在c处插入节点
{
subL ->_bf = -1;
subLR ->_bf= 0;
parent->_bf = 0;
}
else if (bf == 0)//当h==0时，60作为新增节点
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
}

}

void RotateRL(Node* parent)//右左双旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;//记录平衡因子，在后续单旋会置为0
RotateR(parent->_right);
RotateL(parent);
//h==2时，c插入，c的高度变化为h
if (bf == 1)
{
subR->_bf = 0;
parent->_bf = -1;
subRL->_bf = 0;
}
//h==2时，b插入，b的高度变化为h
else if (bf ==-1)
{
subR->_bf = 1;
parent->_bf = 0;
subRL->_bf = 0;
}
// h==1时，60本身就是新增节点
else if(bf == 0 )
{
subR->_bf = 0;
parent->_bf = 0;
subRL->_bf = 0;
}
else
{
//不存在情况，若进入则出问题了
assert(false);
}
}

private:
Node* _root = nullptr;
};


void test_AVLTree1()
{
    //int a[]={16, 3, 7, 11, 9, 26, 18, 14, 15};
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14};
AVLTree<int, int>v1;
for (auto e : a)
{
v1.insert(make_pair(e,e));
}
v1.inorder();
cout << v1.isbalance() << endl;//返回值为布尔值
}


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
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338