传统艺能😎
小编是双非本科大一菜鸟不赘述，欢迎各位指点江山（期待~）（QQ：1319365055）
此前博客点我！点我！请搜索博主 【知晓天空之蓝】
🎉🎉非科班转码社区诚邀您入驻🎉🎉
小伙伴们，打码路上一路向北，彼岸之前皆是疾苦
一个人的单打独斗不如一群人的砥砺前行
这是和梦想合伙人组建的社区，诚邀各位有志之士的加入！！
社区用户好文均加精（“标兵”文章字数2000+加精，“达人”文章字数1500+加精）
直达： 社区链接点我
概念🤔
AVL 树由两位数学家G.M.A delson-Velskii 和 E.M.Landis 发明，AVL 取自这二位名字中的字母。
AVL 树本质上就是一个二叉搜索树，原来的二叉搜索树虽然可以提高搜索效率，但是如果树中的数据是有序或者接近有序的，树就会退回成一个单支树（顺序表），但是在顺序表中数据的查找效率又会变得低下。因此 AVL 树的出现就是为了弥补这个缺陷。
AVL 树可以是空树，而非空树需要具备以下条件才可以：
- 左右子树高度差（即平衡因子）绝对值不超过 1；因为只有满二叉树才能做到每个结点左右子树高度之差均为0 ，既然无法做到维持 0 的高度差即退而求其次维持为 1。
- 左右子树都是 AVL 树
比如下面就是一个 AVL 树：
而下面这个就是非 AVL 树：
如果一棵二叉搜索树的高度是平衡的，即树中每个结点左右子树高度之差的绝对值不超过 1。它就是AVL树。如果它有n个结点，其高度可保持在O (log N)，搜索时间复杂度也是O (log N)。
AVL 树结构定义🤔
这里使用 BSTree 里面的 kv 模型，简单的 k 模型不再演示，为了方便后续旋转以及节点之间关系的联立，我们需要建立一个三叉链结构，为了维护高度差为 1 ，每个节点代入 _bf 平衡因子进行即时迭代。
template<class K，class V>
struct AVLTreeNode
{
//构造函数将根节点平衡因子初始化为0
AVLTreeNode(const T& data = T())
: _pLeft(nullptr)
, _pRight(nullptr)
, _pParent(nullptr)
, _data(data)
, _bf(0)
{}
AVLTreeNode<T,V>* _pLeft;
AVLTreeNode<T,V>* _pRight;
AVLTreeNode<T,V>* _pParent;//左右双亲节点组成的三叉链结构
pair<K,V> _kv;//存储键值对
int _bf; // 节点的平衡因子
};
AVL 树每个节点维护平衡因子并不是必须的，只是不使用此方法更为麻烦，比如可以维护一个高度函数每次进行递归计算。
数据插入🤔
插入还是先找到需要插入的点，方法和二叉搜索树一样，比根节点小的往左走，比根节点大的往右走，相等节点判定为插入失败，插入完成后更新平衡因子
和二叉搜索树插入不同的就是 AVL 树需要时刻更新平衡因子，当平衡因子绝对值超过 1 就会触发旋转。
我们要明白插入节点后对该节点的祖先节点的影响是最大的，因此平衡因子的更新也不单单是一个节点，他会引发自下而上的一连串更新。正因为是自下而上的更新，因此我们最开始定义的是三叉链，方便通过父指针找到当前 parent 节点的父节点，来进行迭代更新，当然不使用三叉链结构可以考虑用栈存储树的路径，但是这样比较麻烦
为了给平衡因子赋予方向权重去区别左子树和右子树，平衡因子的变化规则就是： 新增节点在右子树则 _bf ++，新增节点在左子树则 _bf –
更新完节点后再对此时的平衡因子值做判断，细分为 3 种情况：
- _bf = 0 ，说明之前平衡因子只能是 1 或者 -1，有一边高的情况下加入新节点使树回归平衡
- _bf = 1 或 -1，说明之前平衡因子只能是 0，因为是 2 或 -2 不满足树的结构，树从平衡变得一边高
- _bf = 2 或 -2，说明之前平衡因子只能是 1 或 -1，由一边高变得一边更高
我们说过新节点加入可能会引发第自下而上的一系列更新，上面 3 种判断分别对应以下情况：
- 第一种情况我们不需要做任何更新，parent 节点的平衡因子任然是 0
- 第二种情况新节点插入改变了以 parent 为根结点的子树的高度，影响了 parent 父节点的平衡因子，需要进行向上更新
- 第三种情况高度差绝对值（平衡因子）已经超过 1 ，则破坏了 AVL 的结构，需要进行旋转矫正。
当然，最坏情况就是自下而上一直更新到根节点为止：
当出现平衡因子为 2、-2 的点就代表需要进行旋转处理，parent 是 当前 cur 节点的双亲节点，因此 parent 为2、-2 时此时 cur 的平衡因子只能是 1、-1，具体情况分为了 4 种：
- parent 节点为 2，cur 节点为 1，采用左单旋；
- parent 节点为 2 ，cur 节点为 -1，采用右左双旋；
- parent 节点为 -2，cur 节点为 1，采用左右双旋；
- parent 节点为 -2，cur 节点为 -1，采用右单旋；
具体插入功能代码如下：
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);//空树则插入结点直接作为根结点
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first < cur->_kv.first) //左子树寻找
{
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first) //右子树寻找
{
parent = cur;
cur = cur->_right;
}
else //key值相等冗余，插入失败
{
return false;
}
}
//插入到树中
cur = new Node(kv); //根据所给值构造一个新结点
if (kv.first < parent->_kv.first) //左子树插入
{
parent->_left = cur;
cur->_parent = parent;
}
else //右子树插入
{
parent->_right = cur;
cur->_parent = parent;
}
//更新平衡因子
while (cur != _root) //最坏情况一直更新到根节点
{
if (cur == parent->_left) //parent的左子树增高
{
parent->_bf--; //parent的平衡因子--
}
else if (cur == parent->_right) //parent的右子树增高
{
parent->_bf++; //parent的平衡因子++
}
//对当前平衡因子情况进行判定
if (parent->_bf == 0)
{
break; //parent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子
}
else if (parent->_bf == -1 || parent->_bf == 1)
{
//parent树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == -2 || parent->_bf == 2)
{
//需要进行旋转（此时parent树已经不平衡了）
if (parent->_bf == -2)
{
if (cur->_bf == -1)//左子树高了
{
RotateR(parent); //触发右单旋
}
else //cur->_bf == 1
{
RotateLR(parent); //左右双旋
}
}
else //parent->_bf == 2
{
if (cur->_bf == -1)//右子树高了
{
RotateRL(parent); //右左双旋
}
else //cur->_bf == 1
{
RotateL(parent); //左单旋
}
}
break; //旋转后一定平衡，无需继续往上更新平衡因子(旋转后树高度变为插入之前的)
}
else
{
assert(false); //虽然所有情况判断完了，但是为了逻辑严谨这里断言一下false
}
}
return true; //插入成功
}
AVL 树旋转🤔
左单旋😎
左单旋对应为右边偏高，需要向左调整因此叫做左单旋（这里的红色长方形代表着一个子树）：
上图还是诠释的蛮生动的，但是没有过程演示大家细品一下。 60 的左子树 h 一定是比 60 小的，但是 h 在 30 的右子树那么他一定比 30 大，因此我首先将 h 节点旋转到 30 节点的右子树此时依然满足 ＞ 30 && ＜ 60 的条件，在将 30 接在此时空出来 60 的左子树此时依然满足左子树小于 60，在不破坏树原本结构的同时，顺利的将各节点的平衡因子化为了 0
得到上图后开始进行左单旋，具体左单旋就总结为 4 步：
- subR 左子树作为 parent 右子树
- parent 作为 subR 左子树
- 将 subR 定位新的根节点
- 更新平衡因子
代码表示为：
void RotateL(Node* parent)
{
Node* SubR = parent->_right;
Node* SubRL = SubR->_left;
parent->_right = SubRL;//SubR 左子树作为 parent 右子树
if (SubRL)//注意SubRL可能为空！
{
SubRL->_parent = parent;
}
parent->_parent = SubR;//parent 作为 subR 左子树
SubR->_left = parent;
Node* Tparent = parent->_parent;//建立Tparent和subR之间的关系
SubR->_parent = Tparent;
if (nullptr == Tparent)
{
_root == SubR;
SubR->_parent = nullptr;
}
else//Tparent 有意义则需改变父指针指向
{
if (parent == Tparent->_left)
Tparent->_left = SubR;
else
Tparent->_right = SubR;
}
SubR->_bf = parent->_bf = 0;//更新平衡因子
}
右单旋😎
和左单旋一样，得到上图后开始进行右单旋，具体右单旋就总结为 4 步：
- 将 SubL 右子树变成 parent 左子树；
- parent 变成 SubL 右子树 ；
- 将 SubL 作为现在的根节点；
- 更新平衡因子；
具体代码如下：
void RotateR(Node* parent)
{
Node* SubL = parent->_left;
Node* SubLR = SubL->_right;
parent->_right = SubLR;//将 SubL 右子树变成 parent 左子树
if (SubLR)
{
SubLR->_parent = parent;
}
SubL->_right = parent;//parent 变成 SubL 右子树
parent->_parent = SubL;
Node* Tparent = parent->_parent;
SubL->_parent = Tparent;
if (Tparent == nullptr)
{
_root = SubL;
SubL->_parent = nullptr;
}
else//Tparent 有意义则需改变父指针指向
{
if (parent = Tparent->_left)
Tparent->_left = SubL;
else
Tparent->_right = SubL;
}
parent->_bf = SubL->_bf = 0;//更新平衡因子
}
左右双旋😎
接下来两次旋转是先左旋后右旋，== 左旋==：
右旋：
具体步骤总结为 3 步：
- 以 SubL 为中心进行左旋
- 以 parent 为中心进行右旋
- 更新平衡因子
在双旋后会出现以下三种情况，他们都会回到插入前的高度，因此无序再向上更新平衡因子！
虽然情况复杂了，但是代码可以直接套用左单旋和右单旋的接口，还是非常简单的，具体代码如下：
void RotateLR(Node* parent)
{
Node* SubL = parent->_left;
Node* SubLR = SubL->_right;
int bf = SubLR->_bf;//subLR不可能为nullptr，因为subL的平衡因子是1
RotateL(parent->_left);//以 SubL 为中心进行左旋
RotateR(parent);//以 parent 为中心进行右旋
//更新平衡因子
//区别开三种情况的判断依据就是 SubLR 节点的平衡因子
if (-1 == bf)
parent->_bf = 1;
else if (1 == bf)
SubL->_bf = -1;
else if(0 == bf)
{
SubL->_bf = 0;
parent->_bf = 0;
SubLR->_bf = 0;
}
else
{
assert(false); //在旋转前平衡因子就有问题
}
}
右左双旋😎
接下来两次旋转是先右旋后左旋，== 右旋==：
左旋：
右左双旋总结一下就是三步：
- 以 SubR 为中心进行右旋
- 以 parent 为中心进行左旋
- 更新平衡因子
和左右双旋一样分为 3 种情况，但是都不需要进行向上更新：
具体代码如下：
void RotateRL(Node* parent)
{
Node* SubR = parent->_right;
Node* SubRL = SubR->_left;
int bf = pSubRL->_bf;
RotateR(parent->_right);//以 SubR 为中心进行右旋
RotateL(parent);//以 parent 为中心进行左旋
// 更新部分节点的平衡因子同左右双旋
if (bf == -1)
SubR->_bf = 1;
else if (bf == 1)
parent->_bf = -1;
else if(0 == bf)
{
SubL->_bf = 0;
parent->_bf = 0;
SubLR->_bf = 0;
}
else
{
assert(false); //在旋转前平衡因子就有问题
}
}
验证 AVL 树🤔
借二叉搜索树的经验，走一波中序遍历看是否得到一个有序序列：
void _InOrder(Node* pRoot)
{
if (pRoot)
{
_InOrder(pRoot->_pLeft);
cout << pRoot->_data << " ";
_InOrder(pRoot->_pRight);
}
}
但是中序遍历依然只能证明他是个能跑的二叉搜索树，最重要的是对 AVL 树的特性——平衡性进行验证！
bool _IsAVLTree(Node* pRoot)
{
if (nullptr == pRoot)
return true;
int leftHeight = _Height(pRoot->_pLeft);
int rightHeight = _Height(pRoot->_pRight);
//检查该树是否平衡（高度差）
if (abs(rightHeight - leftHeight) > 1 ||
rightHeight - leftHeight != pRoot->_bf)//检查节点平衡因子
return false;
return _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
}
size_t _Height(Node* pRoot)
{
if (nullptr == pRoot)
return 0;
size_t leftHeight = _Height(pRoot->_pLeft);//递归左树
size_t rightHeight = _Height(pRoot->_pRight);//递归右数
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;//返回AVL树最大高度
}
查找🤔
查找就和二叉搜索树别无二样了：
- 若树为空树，则查找失败，返回nullptr。
- 若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
- 若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
- 若key值等于当前结点的值，则查找成功，返回对应结点。
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_kv.first)
{
cur = cur->_left; //key值小于该结点的值,左子树当中查找
}
else if (key > cur->_kv.first)
{
cur = cur->_right; //key值大于该结点的值,右子树当中查找
}
else
{
return cur;
}
}
return nullptr; //查找失败
}
删除🤔
其实 AVL 树的删除比插入还要难还要复杂，出于市面上 99.9% 的公司 99.9% 不会考到的东西，这里就不当砖家去搬弄了，当然我也仔细学习了删除，这里推荐大佬的详细删除方法，有兴趣的自取：
AVL树的删除
aqa 芭蕾 eqe 亏内，代表着开心代表着快乐，ok 了家人们。