热门标签
热门文章
- 1防止ISE优化信号_ise防止信号
- 2stm32f103真实项目程序。 c原程序 keil工程。 硬件平台采用小米1代扫地机_小米扫地1c stm32
- 3一个通过照片识别地理位置的应用_geospy官网
- 4跨主机Docker容器部署hadoop集群方法_docker 部署hdp 集群 并实现跨服务器访问
- 5Hadoop 高可用集群完全分布式安装教程一篇就够用（zookeeper、spark、hbase、mysql、hive)_hadoop教程
- 62023年最新ADB工具箱R34下载-自带驱动常见ADB命令刷机ROOT神器
- 7python可以开发手机AAP吗？kivy说可以_kivy designer
- 8MySQL---视图（定义、修改、更新、重命名、删除）_修改视图语句
- 9IDEA将本地源代码工程纳入SVN管理_idea项目加入svn管理
- 10区块链技术之身份认证_区块链中的身份认证
当前位置: article > 正文
【数据结构】AVL树（平衡二叉树）
作者：爱喝兽奶帝天荒 | 2024-06-20 13:19:54
赞
踩
avl树
前言：
在前面我们学习了平衡二叉树，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现，下面我们要学习的AVL树就是处理二叉树自身缺陷的一种方式
一、AVL树的概念
在平衡二叉树中，如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素的时间复杂度会退化成O(N)。
因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
AVL树可以是一颗空树，如果不是，则它（或者它的任何一颗子树）需要具备以下性质：
- 它的左右孩子都是AVL树
- 左右子树的高度之差（平衡因子）的绝对值不超过1
如果它有n个节点，它的高度可以保持在log_n，时间复杂度为O(log_n)
二、AVL树的节点
AVL树的节点定义：
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) , _bf(0) , _kv {} };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
三、AVL树的插入
总的来说，AVL树就是在二叉搜索树的基础上加了一个平衡因子，所以AVL树的插入分两步：
1.按二叉搜索树的方式插入节点
2.插入后调节平衡因子
bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; while (parent) { // 更新双亲的平衡因子 if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } //没有改变高度，不继续向上更新平衡因子 if (parent->_bf == 0) { break; } // 插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者 -1 ，说明以双亲为根的二叉树的高度增加了一层，因此需要继续向上调整 else if (parent->_bf == 1 || parent->_bf == -1) { cur = cur->_parent; parent = parent->_parent; } // 双亲的平衡因子为正负2，违反了AVL树的平衡性，需要对以Parent为根的树进行旋转处理 else if (parent->_bf == 2 || parent->_bf == -2) { // 旋转处理 ....... break; } else { // 插入之前AVL树就有问题 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
四、AVL树的旋转
当插入一个新节点时，若是平衡因子到了2，则会导致树的不平衡，此时我们就要对这棵树进行旋转操作，使其重新满足AVL树的性质。
注意：旋转的本质是在降低树的高度
根据节点插入位置，AVL树的旋转分四种:
1.插入在较高左子树的左侧，使用右单旋
上图在插入前，AVL树是平衡的，新节点插入到4的左子树(注意：此处不是左孩子)中，2左子树增加了一层，导致以1为根的二叉树不平衡，要让1平衡，只能将1左子树的高度减少一层，右子树增加一层， 即将左子树往上提，这样1节点转下来，因为1节点比2节点大，只能将其放在2的右子树，而如果2节点有右子树，右子树根的值一定大于2节点，小于1节点，只能将其放在1节点的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：
- **2节点的右孩子可能存在，也可能不存在
- 1节点可能是根节点，也可能是子树
如果是根节点，旋转完成后，要更新根节点
如果是子树，可能是某个节点的左子树，也可能是右子树**
说白了就是把5节点给1节点，再把1节点给2节点，就像是用手把1节点按下来一样（画图理解更佳）
代码：
void RotateR(Node* parent)//以1为旋转点，进行右单旋 { Node* subL = parent->_left;//2节点 Node* subLR = subL->_right;//5节点，也可能没有 parent->_left = subLR;//5节点给1节点 if (subLR) { subLR->_parent = parent; } subL->_right = parent; //1节点可能是根节点，也可能是子树 // 如果是根节点，旋转完成后，要更新根节点 // 如果是子树，可能是某个节点的左子树，也可能是右子树 Node* ppnode = parent->_parent; parent->_parent = subL; if (parent == root) { _root = subL; subL->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subL; } else { ppnode->_right = subL; } subL->_parent = ppnode; } //更新平衡因子 subL->_bf = 0; 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
2.插入在较高右子树的右侧，使用左单旋
参考上面的右单旋，代码：
void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; Node* ppnode = parent->_parent; parent->_parent = subR; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subR; } else { ppnode->_right = subR; } subR->_parent = ppnode; } parent->_bf = 0; subR->_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
3.插入较高左子树的右侧，先左单旋再右单旋
将双旋变成单旋后再旋转，先以2节点为旋转点进行左单旋，然后再以1节点为旋转点进行右单旋，旋转完成后再考虑平衡因子的更新
代码：
void RorareLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; // 旋转之前，60的平衡因子可能是-1/0/1，旋转完成之后，根据情况对其他节点的平衡因子进行调整 int bf = subLR->_bf; // 先对2节点进行左单旋 RorateL(parent->_left); // 再对对1节点进行右单旋 RotateR(parent); if (bf == -1) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 1; } else if (bf == 1) { subLR->_bf = 0; subL->_bf = -1; parent->_bf = 0; } else if (bf == 0) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 0; } else { assert(false); } }
- 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
4.插入较高右子树的左侧，先右单旋再左单旋
和上面的先左再右差不多
总结一下：假如以parent为根的子树不平衡，即parent的平衡因子为2或者-2，分以下情况考虑：
-
parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR
当subR的平衡因子为1，左单旋
当subR的平衡因子为-1，右左单旋 -
parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL
当subL的平衡因子为1，左单旋
当subL的平衡因子为-1，左右单旋
旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新
五、AVL树的验证
如何去验证我们写出来的是AVL树呢？
我们知道，AVL树是在二叉搜索树的基础上加入了控制高度平衡限制，所以对于验证AVL树，我们可以分两步：
-
验证是否为二叉搜索树
对其来一次中序遍历，如果得到一个有序的序列，则为二叉搜索树 -
验证是否为平衡树
(1) 各节点高度差的绝对值不超过1 （2）各节点的平衡因子是否正确
代码：
int _Height(Node* root) { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } int Height() { return _Height(_root); } bool _IsBalance(Node* root, int& height) { // 空树也是AVL树 if (root == nullptr) { height = 0; return true; } int leftHeight = 0, rightHeight = 0; if (!_IsBalance(root->_left, leftHeight) || !_IsBalance(root->_right, rightHeight)) { return false; } if (abs(rightHeight - leftHeight) >= 2) { cout << root->_kv.first << "不平衡" << endl; return false; } if (rightHeight - leftHeight != root->_bf) { cout << root->_kv.first << "平衡因子异常" << endl; return false; } height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; return true; } bool IsBalance() { int height = 0; return _IsBalance(_root, height); }
- 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
六、AVL树的删除
AVL树也算是二叉搜索树，所以我们可以用二叉搜索树删除节点的方式进行删除（可以看看之前讲的二叉搜索树删除操作：https://blog.csdn.net/liuty0125/article/details/139508094?spm=1001.2014.3001.5501），不过有差别的是，在删除后还要更新删除后的平衡因子，最坏情况可能会更新到根节点，所以一般不会对AVL树进行删除操作
七、讲讲AVL树的性能
先说优点：AVL树是一个平衡的二叉搜索树，它的每个节点的左右子树高度差的绝对值不超过1，因此，哪怕最坏也只是查找高度次，保证了查询时高效的时间复杂度O(log_n)。
但是它的缺陷也很明显：如果我们要对AVL树做一些修改方面的操作时，它的性能就十分低了，因为在修改时我们还要维护它的绝对平衡，旋转的次数比较多，而且在删除时，最坏情况可能会更新到根节点。
所以，如果只是需要一种查询高效且有序的数据结构，且数据个数为静态（不改变），比较适合AVL树，但如果你需要经常修改的话，AVL树可能就不太适合了。
八、完整代码
#pragma once #include<iostream> #include<cstring> 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) , _bf(0) , _kv {} }; 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; Node* cur = _root; while (cur) { if (cur->kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; while (parent) { if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } if (parent->_bf == 0) { break; } else if (parent->_bf == 1 || parent->_bf == -1) { cur = cur->_parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -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 { RotateRL(parent); } break; } else { // 插入之前AVL树就有问题 assert(false); } } return true; } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) { subLR->_parent = parent; } subL->_right = parent; Node* ppnode = parent->_parent; parent->_parent = subL; if (parent == root) { _root = subL; subL->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subL; } else { ppnode->_right = subL; } subL->_parent = ppnode; } subL->_bf = 0; parent->_bf = 0; } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; Node* ppnode = parent->_parent; parent->_parent = subR; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subR; } else { ppnode->_right = subR; } subR->_parent = ppnode; } parent->_bf = 0; subR->_bf = 0; } void RorareLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RorateL(parent->_left); RotateR(parent); if (bf == -1) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 1; } else if (bf == 1) { subLR->_bf = 0; subL->_bf = -1; parent->_bf = 0; } else if (bf == 0) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 0; } else { assert(false); } } void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(subR); RotateL(parent); subRL->_bf = 0; if (bf == 1) { subR->_bf = 0; parent->_bf = -1; } else if (bf == -1) { parent->_bf = 0; subR->_bf = 1; } else { parent->_bf = 0; subR->_bf = 0; } } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first < key) { cur = cur->_right; } else if (cur->_kv.first > key) { cur = cur->_left; } else { return cur; } } return NULL; } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->left); cout << root->value << " "; _InOrder(root->right); } void InOrder() { _InOrder(root); } int _Height(Node* root) { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } int Height() { return _Height(_root); } bool _IsBalance(Node* root, int& height) { if (root == nullptr) { height = 0; return true; } int leftHeight = 0, rightHeight = 0; if (!_IsBalance(root->_left, leftHeight) || !_IsBalance(root->_right, rightHeight)) { return false; } if (abs(rightHeight - leftHeight) >= 2) { cout << root->_kv.first << "不平衡" << endl; return false; } if (rightHeight - leftHeight != root->_bf) { cout << root->_kv.first << "平衡因子异常" << endl; return false; } height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; return true; } bool IsBalance() { int height = 0; return _IsBalance(_root, height); } size_t Size() { return _Size(_root); } size_t _Size(Node* root) { if (root == NULL) return 0; return _Size(root->_left) + _Size(root->_right) + 1; } private: Node* root = nullptr; };
- 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
- 339
- 340
- 341
- 342
- 343
- 344
- 345
- 346
- 347
- 348
- 349
- 350
- 351
- 352
- 353
- 354
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/739927
推荐阅读
相关标签
