-
【平衡二叉搜索树】细撕AVL树的插入操作
朋友们好,这篇博客我们学习非常重要的一个数据结构——AVL树，针对AVL树的插入进行了详细的分析，并整理出来一篇博客供我们一起学习和后续的复习,如果文章中有理解不当的地方,还希望朋友们在评论区指出,我们相互学习,共同进步!
☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️☀️一：(…•˘_˘•…)AVL树的概念
二叉搜索树虽然可以提高查找的效率，但是如果数据是有序的或者接近有序的情况时，二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新节点后，如果能保证每个节点的左右子树高度之差的绝对值不超过1（需要对树中的节点进行调整），既可以降低树的高度，从而减少平均搜索长度。
一颗AVL树或者空树：- 📈它的左右子树均是AVL树
- 📈左右子树高度之差（定义平衡因子）的绝对值不超过1。
注：本文平衡因子定义为bf = 右子树的高度 - 右子树的高度
如图即为一颗AVL树，图中红色数字是每个节点的平衡因子。
如果一棵树二叉搜索树是高度平衡的，他就是AVL树，如果他有n个节点，其高度保持在对数量级，因此其搜索的时间复杂度也在对数量级。二：(…•˘_˘•…)AVL树节点的定义
我们以KV模型为背景创建平衡二叉树。
💻：template<class K, class V> struct AVLTreeNode { pair<K, V> _kv; AVLTreeNode<K, V>* _parent; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _left; int _bf; AVLTreeNode(const pair<K, V>& kv) :_kv(kv) , _bf(0) , _parent(nullptr) , _right(nullptr) , _left(nullptr) {} };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
AVL树并没有规定必须要设计平衡因子。只是一个实现的选择，方便控制平衡。
三：(…•˘_˘•…)AVL树节点的插入
AVL树就是在二叉搜索树的基础上引入平衡因子，因此AVL树也可看做二叉搜索树，那么AVL树的插入操作可以分为两个步骤：
3.1：٩͡[๏̯͡๏]按照二叉搜索树的方式插入新节点
💻代码示例：
template<class K, class V> class AVLTree { public: typedef AVLTreeNode<K, V> Node; bool Insert(const pair<K, V>& kv) { // 1、搜索树的规则插入 if (_root == nullptr) { _root = new Node(kv); _root->_bf = 0; return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first)//这里我们可以像模拟实现priority那里一样用仿函数类型对象来控制 { 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;//指回去 } }- 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
🐮🐮🐮：我们以搜索二叉树的规则插入新节点
3.2：٩͡[๏̯͡๏]调整新节点的祖先的平衡因子
🐯新节点插入以后，AVL树的平衡性可能会遭到破坏，此时就需要更新新插入节点的祖先的平衡因子，并检测是否破坏了AVL的平衡性。
💻代码示例：// 更新平衡因子 while (parent) // 最远要更新根 { if (cur == parent->_right) { parent->_bf++; } else { parent->_bf--; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
💡💡💡也就是说当新插入的节点cur在当前祖先节点的右子树上时，当前祖先节点的平衡因子+1，当新插入的节点cur在当前祖先节点的左子树上时，当前祖先节点的平衡因子-1。
⭐️:是否继续更新祖先的平衡因子，关键看子树的高度是否变化。
1️⃣第一种情况：子树高度发生变化，当前父节点平衡因子绝对值为1时：
🔦：parent->bf == 1,parent所在子树的高度发生变化，上图说明原来parent->bf = 0，现在右边插入节点变高了，那么继续更新祖先的平衡因子。
🔦parent->bf == -1,parent所在子树的高度发生变化，上图说明原来parent->bf = 0，现在左边插入节点变高了，那么继续更新祖先的平衡因子。2️⃣第二种情况：子树高度不发生变化，当前祖先节点平衡因子为0时：
🔦parent所在的子树高度不变，说明原来parent->bf == 1或者-1，现在插入新的节点到矮的那边，因此插入成功。
3️⃣第三种情况：子树高度发生变化，当前祖先节点平衡因子的绝对值为2时，这时就违反了平衡树的规则，涉及到通过旋转对树做出调整。
💻:代码示例while (parent) // 最远要更新根 { if (cur == parent->_right) { parent->_bf++; } else { parent->_bf--; } // 是否继续更新？ if (parent->_bf == 0) // 1 or -1 -》 0 插入节点填上矮的那边 { // 高度不变，更新结束,插入成功 break; } else if (parent->_bf == 1 || parent->_bf == -1) // 0 -》 1 或 -1 插入节点导致一边变高了 { // 子树的高度变了，继续更新祖先 cur = cur->_parent;//cur = parent parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) // -1 or 1 -》 2 或 -2 插入节点导致本来高一边又变高了 { // 子树不平衡 -- 需要旋转处理 // ...什么时候左单旋，右单旋，左右双旋，右左双旋 //由平衡因子决定该怎么旋转 } else { // 插入之前AVL就存在不平衡子树，|平衡因子| >= 2的节点 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
- 36
- 37
3.3：٩͡[๏̯͡๏]AVL树的旋转
📢📢📢旋转规则：
- 保持搜索树的规则。
- 子树变平衡。
3.3.1:◔ ‸◔？新节点插入较高右子树的右侧（右右）
🔑🔑🔑解决方法：左单旋
✏️解释：这里的a、b、c表示的是子树，代表所有抽象的情况。
比如h == 0时：
比如h == 1时：
比如h == 2时：
🔬🔬🔬从上面分析可知，当h==2时，如果画出其所有具体情况，那么将会有36种画法，所以我们以抽象图来简化！
🆘左单旋调整过程：
1.B节点带着他的右子树一起上升。
2.A节点成为B的左孩子。
3.原来B的左孩子成为A的右孩子。
💻代码示例：//旋转操作旨在改变各个节点的链接关系，使之平衡并且满足搜索数特性 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL)//防止对空指针解引用 { subRL->_parent = parent; } Node* pp = parent->_parent; subR->_left = parent; parent->_parent = subR; if (parent == _root) { _root = subR; _root->_parent = nullptr; } else { if (pp->_left == parent) { pp->_left = subR; subR->_parent = pp; } else { pp->_right = subR; subR->_parent = pp; } } // 更新平衡因子 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
- 35
- 36
- 37
- 38
- 39
- 40
旋转完后别忘了更新平衡因子！
3.3.2:◔ ‸◔？新节点插入较高左子树的左侧（左左）
🔑🔑🔑解决方法：右单旋
😁😁😁其中具体的情况可按照3.3.1节具体分析。
📖总结：- A节点带着它的左子树一起上升。
- B节点及其子树变成A的右子树。
- 原来A的右子树变成B的左子树。
💻代码示例：
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 (parent == _root) { _root = subL; _root->_parent = nullptr; } else { if (ppNode->_right == parent) { ppNode->_right = subL; } else { ppNode->_left = subL; } subL->_parent = ppNode; } parent->_bf = 0; subL->_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
3.3.3:◔ ‸◔？新节点插入较高左子树的右侧（左右）
🔑🔑🔑解决方法：先左单旋再右单旋
✏️✏️✏️具体分析：
当h == 0时：
h == 1时：
h == 2时：
这里a和d可以是X、Y、Z子树中的任意一种，且在b、c的4个孩子位置插入均会引发旋转，因此当h等于2时，具体情况共有36种。
🔧🔧🔧具体操作旋转：
当h >= 1时：
当h == 0时：
💻代码示例：
void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(subL); RotateLR(parent); //更新平衡因子 if (bf == 0) { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } else if (bf == 1) { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else if (bf == -1) { parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else{ //subLR->_bf旋转前就有问题 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
3.3.4:◔ ‸◔？新节点插入较高右子树的左侧（右左）
🔑🔑🔑解决方法：先进行右单旋，在进行左单旋。
💡💡💡如图在c的子树上插入新节点引发旋转，先以C为旋转点进行右单旋，再以A为旋转点左单旋！
同理其他的具体情况可按照3.3.3的思路分析！
💻代码示例：void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(subR); RotateL(parent); //更新平衡因子 if (bf == 0) { parent->_bf = 0; subR->_bf = 0; subRL->_bf = 0; } else if (bf == 1) { parent->_bf = -1; subR->_bf = 0; subRL->_bf = 0; } else if (bf == -1) { subR->_bf = 1; subRL->_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
⚠️⚠️⚠️注意：旋转过后一定得更新相关节点的平衡因子！
四：AVL树插入完整代码
💻
template<class K, class V> struct AVLTreeNode { pair<K, V> _kv; AVLTreeNode<K, V>* _parent; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _left; int _bf; // AVL树并没有规定必须要设计平衡因子 // 只是一个实现的选择，方便控制平衡 AVLTreeNode(const pair<K, V>& kv) :_kv(kv) , _bf(0) , _parent(nullptr) , _right(nullptr) , _left(nullptr) {} }; template<class K, class V> class AVLTree { public: typedef AVLTreeNode<K, V> Node; bool Insert(const pair<K, V>& kv) { // 1、搜索树的规则插入 // 2、看是否违反平衡规则，如果违反就需要处理：旋转 if (_root == nullptr) { _root = new Node(kv); _root->_bf = 0; return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first)//这里我们可以像模拟实现priority那里一样用仿函数类型对象来控制 { 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->_right) { parent->_bf++; } else { parent->_bf--; } // 是否继续更新？ if (parent->_bf == 0) // 1 or -1 -》 0 插入节点填上矮的那边 { // 高度不变，更新结束,插入成功 break; } else if (parent->_bf == 1 || parent->_bf == -1) // 0 -》 1 或 -1 插入节点导致一边变高了 { // 子树的高度变了，继续更新祖先 cur = cur->_parent;//cur = parent parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) // -1 or 1 -》 2 或 -2 插入节点导致本来高一边又变高了 { // 子树不平衡 -- 需要旋转处理 // ...什么时候左单旋，右单旋，左右双旋，右左双旋 //由平衡因子决定该怎么旋转 if (parent->_bf == 2 && parent->_right->_bf == 1) { RotateL(parent); break; } else if (parent->_bf == -2 && parent->_right->_bf == -1) { RotateR(parent); break; } else if (parent->_bf == -2 && parent->_right->_bf == 1) { RotateLR(parent); break; } else if (parent->_bf == 2 && parent->_right->_bf == -1) { RotateRL(parent); break; } else { assert(false); } } else { // 插入之前AVL就存在不平衡子树，|平衡因子| >= 2的节点 assert(false); } } return true; } private: //旋转操作旨在改变各个节点的链接关系，使之平衡并且满足搜索数特性 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL)//防止对空指针解引用 { subRL->_parent = parent; } Node* pp = parent->_parent; subR->_left = parent; parent->_parent = subR; if (parent == _root) { _root = subR; _root->_parent = nullptr; } else { if (pp->_left == parent) { pp->_left = subR; subR->_parent = pp; } else { pp->_right = subR; subR->_parent = pp; } } // 更新平衡因子 parent->_bf = 0; subR->_bf = 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 (parent == _root) { _root = subL; _root->_parent = nullptr; } else { if (ppNode->_right == parent) { ppNode->_right = subL; } else { ppNode->_left = subL; } subL->_parent = ppNode; } parent->_bf = 0; subL->_bf = 0; } void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(subL); RotateLR(parent); //更新平衡因子 if (bf == 0) { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } else if (bf == 1) { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else if (bf == -1) { parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else{ //subLR->_bf旋转前就有问题 assert(false); } } void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(subR); RotateL(parent); //更新平衡因子 if (bf == 0) { parent->_bf = 0; subR->_bf = 0; subRL->_bf = 0; } else if (bf == 1) { parent->_bf = -1; subR->_bf = 0; subRL->_bf = 0; } else if (bf == -1) { subR->_bf = 1; subRL->_bf = 0; parent->_bf = 0; } else { assert(false); } } 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
🎉🎉🎉：朋友们，插入操作的讨论就到这里了，如果看了觉得还不错希望三连支持一下，谢谢！🌹🌹🌹
✉️✉️✉️如果有更多的讨论可以加我的VX: F19151796,或者QQ🐧：1501114586。 -
相关阅读:
图像标签的使用2
在你所有的项目中都加入 TailwindCSS 吧！
一文读懂什么是布隆过滤器
leetcode — 动态规划 — 打家劫舍、完全平方数
Himall验证Web帮助类是否是get请求、是否是post请求、是否是Ajax请求、获得查询字符串中的值
动态规划44（Leetcode983最低票价）
MindSpore：强化学习基础-蒙特卡洛(Monte Carlo)
用Python实现一个简单的——人脸相似度对比
【Leetcode】189. 轮转数组
掌握优先级队列：提升效率的关键技巧
- 原文地址：https://blog.csdn.net/qq_43727529/article/details/126222081
