【C++高阶(三)】AVL树深度剖析&模拟实现
💓博主CSDN主页:杭电码农-NEO💓
⏩专栏分类:C++从入门到精通⏪
🚚代码仓库:NEO的学习日记🚚
🌹关注我🫵带你学习C++
🔝🔝
AVL树
- 1. 前言
- 2. AVL树的概念以及特性
- 3. AVL树模拟实现基本框架
- 4. AVL树插入函数深度剖析
- 5. AVL树插入代码剖析(无旋转)
- 6. AVL树的旋转操作深度剖析(一)
- 7. AVL树的旋转操作深度剖析(二)
- 8. AVL树旋转的代码实现
- 9. 总结以及所有代码
1. 前言
如果你不知道什么是二叉搜索树
请一定先阅读这篇文章:
二叉搜索树深度剖析
二叉搜索树如果插入顺序是有序的 那么这棵树的查找效率将会是O(N) 所以说在实际情况下,二叉搜索很少被使用
为了解决二叉搜索树不稳定的问题
于是乎有人提出了AVL树结构,也就是
高度平衡二叉搜索树!
本章重点:
本篇文章着重讲解AVL树的概念以及
定义,并且在模拟实现AVL树前,将AVL
树的插入的情况做系统分析,最后模拟
实现AVL树的插入操作,进一步理解它!
2. AVL树的概念以及特性
AVL树通过一个特性来保证二叉
搜索的平衡性问题: 那就是任一
节点两边的子树高度差不超过1!
高度差一般是右子树高度减左子树高度
由于AVL树的这种特殊性质,使得它的
查找效率是百分百的O(logn),可以说
这是天才的发明,当插入或删除节点时,
高度差不符合要求后,可以通过旋转的
方式来重新让这棵树变成AVL树!
下面,我们一般尝试理解AVL树
一边来模拟实现它!
3. AVL树模拟实现基本框架
首先我们应该想到一点,当高度差
大一1时我们需要做处理,但是我们
怎么知道哪个节点高度差大于1呢?
因此应该在节点中多定义一个整数
来记录当前节点的左右高度差!
AVL树的节点结构体:
template struct AVLTreeNode //高度平衡二叉搜索树 { AVLTreeNode(const pair& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_kv(kv) ,_bf(0) {} //用三叉链,方便更新祖先的平衡因子 AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; pair _kv; //存储的数据 int _bf; //balance factor平衡因子 };有了节点的结构体后,定义一下
AVL树的基本结构吧:
template struct AVLTree { typedef AVLTreeNode Node; private: Node* _root;//定义一个根节点 };4. AVL树插入函数深度剖析
AVL数的插入有三个步骤:
- 按照二叉搜索树规则插入节点
- 插入完成后更新平衡因子
- 若平衡因子不正确需要采取措施
所以当前目标就是把这三步搞清楚
更新平衡因子规则:
-
新增在右,父亲的bf加一
新增在左,父亲的bf减一
-
更新完成后,父亲的bf==1/-1,说明
父亲插入前的bf一定是0,并且插入后
一边高一边低,需要继续向上更新
- 更新完成后,父亲的bf==0,说明父亲
在插入前的bf是1/-1,并且插入后两边高度
一致,就不需要继续往上更新了!
- 更新完成后,父亲的bf==2/-2,打破
了平衡,父亲所在的子树要旋转处理
由于旋转处理的过程比较复杂
所以先将除了旋转的所有代码写出来
后再去讨论旋转的话题!
5. AVL树插入代码剖析(无旋转)
话不多说,直接上手!
bool insert(const pair& kv)//第一步:按照二叉搜索树的方式插入值,第二步:调整平衡因子后旋转 { if (_root == nullptr)//插入第一个节点时 { _root = new Node(kv); return true; } Node* cur = _root; Node* parent = nullptr; while (cur)//找到要插入节点的位置和它的父亲 { if (cur->_kv.first _right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else return false; } //走到这一步后,已经找到了位置,开空间后插入 cur = new Node(kv); if (parent->_kv.first _right = cur; else parent->_left = cur; //此时new出来的节点的parent还指向空 cur->_parent = parent; //插入完成后,此时需要查看平衡因子来控制平衡 //沿着插入的位置往上更新平衡因子 while (parent)//由于parent需要不断向上更新,所以要使用循环! { if (cur == parent->_right) parent->_bf++; else parent->_bf--; if (parent->_bf == 0)//不用向上更新了 break; else if (parent->_bf == 1 || parent->_bf == -1)//若高度出现变化,需要往上更新 { parent = parent->_parent; cur = cur->_parent; } else if (abs(parent->_bf) == 2)//说明parent所在的子树不平衡了,需要旋转处理 { //后面再处理这个过程...... } } }关于代码的解释都在注释中,请耐心查看!
6. AVL树的旋转操作深度剖析(一)
首先,旋转一共由四种情况,不管是
哪一种情况,我们的目的都是将原本
不平衡的树变成符合规则的AVL树!
先看两个最简单的例子:
左单选和右单旋:
大概了解了它的规则后,再来看泛型的:
- 右单旋
- 左单旋:
7. AVL树的旋转操作深度剖析(二)
当你了解了前两种最简单的情况后
就可以来看看"双旋"操作了!
还是先看看最简单的例子:
先左旋再右旋
先右旋再左旋
了解了最简单了例子后,直接上手!
8. AVL树旋转的代码实现
void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* ppNode = parent->_parent; subR->_left = parent; parent->_parent = subR; if (_root == parent) { _root = subR; subR->_parent = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; subR->_parent = ppNode; } subR->_bf = parent->_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 (_root == parent) { _root = subL; subL->_parent = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; subL->_parent = ppNode; } subL->_bf = parent->_bf = 0; } void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); subLR->_bf = 0; if (bf == 1) { parent->_bf = 0; subL->_bf = -1; } else if (bf == -1) { parent->_bf = 1; subL->_bf = 0; } else if (bf == 0) { parent->_bf = 0; subL->_bf = 0; } else assert(false); } void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); subRL->_bf = 0; if (bf == 1) { subR->_bf = 0; parent->_bf = -1; } else if (bf == -1) { subR->_bf = 1; parent->_bf = 0; } else if (bf == 0) { parent->_bf = 0; subR->_bf = 0; } else assert(false); }你问我我怎么写出代码的?
那是一段痛苦的回忆,代码的验证就交给你们了
代码中对于平衡因子的更新有细节!
9. 总结以及所有代码
AVL树的模拟实现属于了解的内容
并不需要完全掌握,所以同学了只需
理解了AVL树的旋转即可,不要求手撕代码!
(当然前几年有学长面试时被要求手撕了doge)
AVL树模拟实现全部代码:
我的gitee仓库
🔎 下期预告:红黑树树深度剖析 🔍
