-
AVL 树
AVL树
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下
为了解决上诉问题有这么一种方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
AVL树的结构
template<class K,class V> struct AVLTreeNode { AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _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);// protected: 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
AVL树的插入
先按照二叉搜索树的方式插入新节点(二叉搜索树的实现)
然后调整节点的平衡因子
bf平衡因子==2 or -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 (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else { return false; } } Node* newnode = new Node(kv); if (parent->_kv.first > kv.first) { parent->_left = newnode; newnode->_parent = parent; parent->_bf--; } else if (parent->_kv.first < kv.first) { parent->_right = newnode; newnode->_parent = parent; parent->_bf++; } else { assert(false); } //通过平衡因子的变化判断是否需要旋转 while (parent) { //cout << "parent-val=" << parent->_kv.first << endl; //cout << "parent-bf=" << parent->_bf << endl; if (parent->_bf == 0) { //父亲所在子树高度不变，不需要向上更新平衡因子 return true; } else if (parent->_bf == 1 || parent->_bf == -1) { //父亲所在子树高度变化，可能会影响到上面的树，需要向上更新 if (parent->_parent == nullptr) ; else if (parent == parent->_parent->_right) parent->_parent->_bf++; else if (parent == parent->_parent->_left) parent->_parent->_bf--; else assert(false); parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { //平衡因子出现异常，需要进行旋转 if (parent->_bf == 2 && parent->_right->_bf == 1) { //右右的情况，需要左单旋 RotateL(parent); } else if (parent->_bf == -2 && parent->_left->_bf == -1) { //左左的情况，需要右单旋 RotateR(parent); } else if (parent->_bf == 2 && parent->_right->_bf == -1) { //右左的情况，需要右单旋然后左单旋 RotateRL(parent); } else if (parent->_bf == -2 && parent->_left->_bf == 1) { //左右的情况，需要左单旋然后右单旋 RotateLR(parent); } else { cout <<"parent->bf=" << parent->_bf << endl; cout << "parent->left->bf=" << parent->_left->_bf << endl; cout << "parent->right->bf=" << parent->_right->_bf << endl; assert(false); } //经过旋转，该子树的高度已经降低，所以不会影响到上面树 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
- 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
能用else if就用else if，留else来快速判断错误出现位置
AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
- 验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树 - 验证其为平衡树
- 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
- 节点的平衡因子是否计算正确
public: void InOrder() { _InOrder(_root); cout << endl; } bool IsBalance()//检查平衡因子是否正确 { return _IsBalance(_root); } protected: bool _IsBalance(Node* root)//检查左右树高度差，看是不是和平衡因子给的结果一样 { if (root == nullptr) return true; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); if (rightHeight - leftHeight != root->_bf) { cout <<"root == " <<root->_kv.first<< " 时平衡因子异常:" << root->_bf << endl; return false; } return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right); } int _Height(Node* root) { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return leftHeight < rightHeight ? rightHeight + 1 : leftHeight + 1; } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); }- 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
可以先用指定数据测试，没问题了之后使用随机数进行测试，可以通过手动打断点的方式快速定位到出问题的数据。
int main() { const int N = 1000; srand(time(0)); vector<int> v; v.reserve(N); for (int i=0;i<N;i++) { v.push_back(rand()); cout << v.back() << " "; } cout << endl; //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> t; for (auto e : v) { //if (e == 5) //{ // cout << endl; //} cout << "Insert:" << e << endl; t.Insert(pair<int,int>(e,e)); } t.InOrder(); cout << t.IsBalance() << endl; return 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
AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log2N，但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
完整代码
#include#include #include using namespace std; template<class K,class V> struct AVLTreeNode { AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _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; Node* cur = _root; while (cur) { if (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else { return false; } } Node* newnode = new Node(kv); if (parent->_kv.first > kv.first) { parent->_left = newnode; newnode->_parent = parent; parent->_bf--; } else if (parent->_kv.first < kv.first) { parent->_right = newnode; newnode->_parent = parent; parent->_bf++; } else { assert(false); } //通过平衡因子的变化判断是否需要旋转 while (parent) { //cout << "parent-val=" << parent->_kv.first << endl; //cout << "parent-bf=" << parent->_bf << endl; if (parent->_bf == 0) { //父亲所在子树高度不变，不需要向上更新平衡因子 return true; } else if (parent->_bf == 1 || parent->_bf == -1) { //父亲所在子树高度变化，可能会影响到上面的树，需要向上更新 if (parent->_parent == nullptr) ; else if (parent == parent->_parent->_right) parent->_parent->_bf++; else if (parent == parent->_parent->_left) parent->_parent->_bf--; else assert(false); parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { //平衡因子出现异常，需要进行旋转 if (parent->_bf == 2 && parent->_right->_bf == 1) { //右右的情况，需要左单旋 RotateL(parent); } else if (parent->_bf == -2 && parent->_left->_bf == -1) { //左左的情况，需要右单旋 RotateR(parent); } else if (parent->_bf == 2 && parent->_right->_bf == -1) { //右左的情况，需要右单旋然后左单旋 RotateRL(parent); } else if (parent->_bf == -2 && parent->_left->_bf == 1) { //左右的情况，需要左单旋然后右单旋 RotateLR(parent); } else { cout <<"parent->bf=" << parent->_bf << endl; cout << "parent->left->bf=" << parent->_left->_bf << endl; cout << "parent->right->bf=" << parent->_right->_bf << endl; assert(false); } //经过旋转，该子树的高度已经降低，所以不会影响到上面树 break; } else { assert(false); } } return true; } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; //subR变成新的子树的头，parent链接到subR左边，并把subRL链接到自己右边 subR->_left = parent; parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* parentParent = parent->_parent; parent->_parent = subR; if (parentParent == nullptr) { _root = subR; subR->_parent = nullptr; } else { subR->_parent = parentParent; if (parentParent->_left == parent) { parentParent->_left = subR; } else if (parentParent->_right == parent) { parentParent->_right = subR; } else { assert(false); } } //左单旋后树高度降低平衡因子更正 parent->_bf = subR->_bf = 0; } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; //subL变成新的子树的头，parent链接到subL右边，并把subLR链接到自己左边 subL->_right = parent; parent->_left = subLR; if (subLR) subLR->_parent = parent; Node* parentParent = parent->_parent; parent->_parent = subL; if (parentParent == nullptr) { _root = subL; subL->_parent = nullptr; } else { subL->_parent = parentParent; if (parentParent->_left == parent) { parentParent->_left = subL; } else if (parentParent->_right == parent) { parentParent->_right = subL; } else { assert(false); } } //右单旋后树高度降低，平衡因子更正 parent->_bf = subL->_bf = 0; } void RotateRL(Node* parent) { //先记录当前subRL的bf，不然右和左旋转后就找不到了 Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; //对subR进行右单旋，再对自己左单旋 RotateR(subR); RotateL(parent); //旋转完之后位置正确，高度降低，但是bf需要调整回正确值 if (bf == 0) { parent->_bf = subR->_bf = subRL->_bf = 0; } else if (bf == -1) { subRL->_bf = 0;//新的头 parent->_bf = 0; subR->_bf = 1; } else if (bf == 1) { subRL->_bf = 0;//新的头 parent->_bf = -1; subR->_bf = 0; } else { assert(false); } } void RotateLR(Node* parent) { //先记录当前subLR的bf，不然左右分别旋转后就找不到了 Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; //对subL进行左单旋，再对自己右单旋 RotateL(subL); RotateR(parent); //旋转完之后位置正确，高度降低，但是bf需要调整回正确值 if (bf == 0) { parent->_bf = subL->_bf = subLR->_bf = 0; } else if (bf == -1) { subLR->_bf = 0;//新的头 parent->_bf = 1; subL->_bf = 0; } else if (bf == 1) { subLR->_bf = 0;//新的头 parent->_bf = 0; subL->_bf = -1; } else { assert(false); } } void InOrder() { _InOrder(_root); cout << endl; } bool IsBalance()//检查平衡因子是否正确 { return _IsBalance(_root); } protected: bool _IsBalance(Node* root)//检查左右树高度差，看是不是和平衡因子给的结果一样 { if (root == nullptr) return true; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); if (rightHeight - leftHeight != root->_bf) { cout <<"root == " <<root->_kv.first<< " 时平衡因子异常:" << root->_bf << endl; return false; } return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right); } int _Height(Node* root) { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return leftHeight < rightHeight ? rightHeight + 1 : leftHeight + 1; } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); } Node* _root = nullptr; }; //测试 int main() { const int N = 1000; srand(time(0)); vector<int> v; v.reserve(N); for (int i=0;i<N;i++) { v.push_back(rand()); cout << v.back() << " "; } cout << endl; //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> t; for (auto e : v) { //if (e == 5) //{ // cout << endl; //} cout << "Insert:" << e << endl; t.Insert(pair<int,int>(e,e)); } t.InOrder(); cout << t.IsBalance() << endl; return 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
- 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
- 355
- 356
-
相关阅读:
OpenCV练习（1）签名修复
小米秋招卷1
必看：阿里云99元服务器老用户续费到2027年的方法！
Spring Bean的作用域有哪些？它的注册方式有几种？
[SpringBoot系列]进阶配置
图表开发工具LightningChart .NET v12.0正式发布——拥有新图表、新系列类型
驱动开发，IO模型之IO多路复用实现过程，select方式
PHP 用户注册和登录表单 – PDO。
聊聊 JSON Web Token (JWT) 和 jwcrypto 的使用
c语言中extern定义和引用其他文件的变量，（sublime text）单独一个文件编译不会成功
- 原文地址：https://blog.csdn.net/Adz1119/article/details/134265254
