【C++进阶】AVL树的介绍及实现
🥕个人主页：开敲🍉
🔥所属专栏：C++🥭
🌼文章目录🌼
1. AVL的介绍
2. AVL树的实现
2.1 AVL树的结构
2.2 AVL树的插入
2.2.1 插入一个值的大概过程
2.2.2 平衡因子的更新
2.2.3 插入节点及更新平衡因子的代码实现
2.3 旋转
2.3.1 旋转的原则
2.3.2 右单旋
2.3.3 右单旋实现代码
2.3.4 左单旋
2.3.5 左单旋实现代码
2.3.6 左右双旋
2.3.7 左右双旋实现代码
2.3.8 右左双旋
2.3.9 右左双旋实现代码
2.4 AVL树的查找
2.5 AVL树的平衡检测
1. AVL的介绍
① AVL树是最早发明的自平衡二叉搜索树，AVL或是一颗空树，或是一颗具备以下性质的二叉搜索树：它的左右子树都是AVL树，且左右子树的高度差不超过1。AVL树是一颗高度平衡搜索二叉树，通过控制高度差来控制平衡。
② AVL树的名字来源于它的发明者G. M. Adelson-Velsky 和 E. M. Landis，他们是两位前苏联的科学家，而AVL树就是它们在 1962 年的论文《An algorithm for the organization on information》中发表的。
③ 本篇文章中AVL的实现我们引入平衡因子的概念，树中的每个节点都有一个平衡因子，平衡因子 ＝ 右子树的高度 - 左子树的高度，结合着第 ① 条概念我们可以知道，平衡因子的值只能是 0/1/-1。AVL树不是一定要有平衡因子，还有其他方法可以代替，但是使用平衡因子让我们观察树是否平衡变得方便。
④ 为什么AVL要求高度差不超过1呢？直接将高度差限制死为0不是更平衡吗？道理很简单：一棵树不一定是满二叉树。如果将高度差限制死为0，则默认这棵树就是满二叉树，这显然是不符合实际的。那为什么要限制为1，不限制为2呢？因为任何不满的树，都可以通过变换、旋转等操作将它的每个节点高度差控制在1以内，既然可以控制到1以内，那自然1是最好的。
⑤ AVL树整体的节点数量和分布与完全二叉树类似，因此高度可以控制在log N，因此查找的效率也就是 O(log N) ，而普通的二叉搜索树在极端情况下，如插入节点：1，2、3、4、5、6，则二叉搜索树会退化为单链，查找效率也就退化为了 O(N)。因此AVL树的效率比起普通二叉搜索树提升了一个档次。
2. AVL树的实现
2.1 AVL树的结构
对于AVL中的每个节点，都有：_val变量，用于存放节点的值； _left 和 _right 指针，用于链接左孩子和右孩子；parent指针，用于指向其父节点，这个指针的作用是为了方便我们修改平衡因子，因为孩子平衡因子的改变可能会导致其父节点甚至祖宗节点平衡因子的改变，有了 _parent 就方便我们去到父节点修改平衡因子；_bf变量，用于存放平衡因子的值。
对于AVL树本体：实现AVL树中的增删查改等功能。
下面是AVL树节点和本体的大体框架：
template <class T>
class AVLTreeNode
{
public:
AVLTreeNode(const T val)//AVL构造函数
:_val(val)
,_left(nullptr)
,_right(nullptr)
,parent(nullptr)
,_bf(0)//每个新节点的左右子树都为空，因此平衡因子默认为0
{}
T _val;
AVLTreeNode<T>* _left;
AVLTreeNode<T>* _right;
AVLTreeNode<T>* parent;
int _bf;
};
template <class T>
class AVLTree
{
public:
AVLTree()
:_root(nullptr)
{}
private:
AVLTreeNode<T>* _root;//根节点
}
2.2 AVL树的插入
2.2.1 插入一个值的大概过程
① 插入值时按照二叉搜索树的规则插入：比当前节点值小走左边；反之走右边；相同走哪边都行。
② 新增节点以后，会影响其父亲甚至祖先节点的高度，因此在新插入一个值后需要改变新插入位置父节点以及祖先节点的平衡因子，但是更新也分为多种情况，最坏的情况会更新到根，一般情况更新到某个位置就会停止。具体情况我们在下面分析。
③ 如果更新平衡因子的过程中没有问题，则插入结束。那么什么是没问题，什么又是有问题呢？在下面分析。
④ 如果更新平衡因子后导致平衡因子 == 2 || == -2，则当前子树出现了问题，不再平衡，我们通过旋转操作将其重新变平衡。
2.2.2 平衡因子的更新
平衡因子 = 右子树高度 - 左子树高度（当然这里也可以 左子树高度 - 右子树高度，随你喜欢）
更新原则：
① 只有子树高度变化才会影响平衡因子。
② 插入节点一定会导致高度变化。如果节点插入在 parent 左边，则平衡因子--；如果节点插入在 parent 右边，则平衡因子++。
③ 以 parent 为根节点的子树的高度是否变化，决定了是否要继续向上更新平衡因子。
更新停止条件：
① 更新后 parent 的平衡因子 ＝ 0，说明 parent 的平衡因子的变化为 1 -> 0 或者 -1 -> 0，说明parent 之前的平衡因子为 1 或者 -1，也就说明更新前 parent 的左右子树一边高一边低，更新后左右高度相同，此时不会影响 parent 的父亲或者祖宗节点，更新完 parent 就结束：
② 更新后 parent 的平衡因子 ＝ 1 或者 -1，说明 parent 的平衡因子的变化为 0 -> 1 或者 0 -> -1，说明更新前 parent 的左右子树高度相同，更新后出现了一边高一边低的情况，此时更新完 parent 的平衡因子后还要继续向上更新：
③ 更新后 parent 的平衡因子 ＝ 2 或者 -2，此时破坏了AVL树的结构，需要通过旋转操作将 parent 所在子树旋转平衡。旋转后 parent 所在子树高度平衡，不需要再向上更新：
2.2.3 插入节点及更新平衡因子的代码实现
bool Insert(const T& val)
{
Node* parent = nullptr;
Node* cur = _root;
if (!_root) _root = new Node(val);//如果是第一个插入的节点，则作为根
else
{
while (cur)//二叉搜索树插入规则
{
if (cur->_val > val)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_val < val)
{
parent = cur;
cur = cur->_right;
}
else assert(0);
}
cur = new Node(val);
if (parent->_val > val) parent->_left = cur;
else if (parent->_val < val) parent->_right = cur;
else assert(false);
cur->parent = parent;
while (parent)
{
//更新平衡因子：如果节点插入在 parent 左边，则平衡因子--；反之，平衡因子++
if (parent->_left == cur)
parent->_bf--;
else if (parent->_right == cur)
parent->_bf++;
else assert(false);
if (parent->_bf == 0) return true;//不需要继续向上更新
else if (parent->_bf == 1 || parent->_bf == -1)//需要继续向上更新
{
cur = parent;//向上更新
parent = parent->parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)//此时不平衡了，进行旋转操作
{
//旋转
//旋转操作在后面
return true;
}
}
}
return true;
}2.3 旋转
2.3.1 旋转的原则
① 保证旋转后整棵树还是二叉搜索树
② 让旋转的子树从不平衡到平衡，旋转共分为四种：右单旋、左单旋、左右双旋、右左双旋
2.3.2 右单旋
2.3.3 右单旋实现代码
//右单旋
void RotateR(Node* parent)
{
Node* Pparent = parent->parent;
Node* subL = parent->_left;
Node* subLR = subL->_right;
subL->parent = Pparent;
subL->_right = parent;
parent->_left = subLR;
parent->parent = subL;
if(subLR) subLR->parent = parent;
if (!Pparent) _root = subL;
else if (Pparent->_left == parent) Pparent->_left = subL;
else if (Pparent->_right == parent) Pparent->_right = subL;
else assert(0);
parent->_bf = subL->_bf = 0;
}2.3.4 左单旋
左单旋与右单旋是完全类似的，因此这里只画旋转的过程，不作详细解释：
2.3.5 左单旋实现代码
//左单旋
void RotateL(Node* parent)
{
Node* Pparent = parent->parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
subR->parent = Pparent;
subR->_left = parent;
parent->_right = subRL;
parent->parent = subR;
if (subRL) subRL->parent = parent;
if (!Pparent) _root = subR;
else if (Pparent->_left == parent) Pparent->_left = subR;
else if (Pparent->_right == parent) Pparent->_right = subR;
else assert(0);
parent->_bf = subR->_bf = 0;
}2.3.6 左右双旋
双旋对于单旋来说要麻烦不少，来看下面的图：
这个时候就要搬出我们的左右双旋：
至此，我们看似解决了这个问题，但真的是这样吗？
当然不是，双旋的最难点——平衡因子的问题我们还没解决呢？你可能会问，单旋不是帮我们处理好了吗？nonono，双旋的平衡因子问题单旋可没法解决，来看下面的图：
2.3.7 左右双旋实现代码
//右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
RotateR(subR);//右单旋
RotateL(parent);//左单旋
if (subRL->_bf == 0) parent->_bf = subR->_bf = 0;
else if (subRL->_bf == -1)
{
subR->_bf = 1;
parent->_bf = 0;
}
else if (subRL->_bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
}
else assert(0);
subRL->_bf = 0;
}2.3.8 右左双旋
右左双旋与左右双旋也是完全类似的，这里也是只画出过程图，不作详细解释：
2.3.9 右左双旋实现代码
//右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
RotateR(subR);//右单旋
RotateL(parent);//左单旋
if (subRL->_bf == 0) parent->_bf = subR->_bf = 0;
else if (subRL->_bf == -1)
{
subR->_bf = 1;
parent->_bf = 0;
}
else if (subRL->_bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
}
else assert(0);
subRL->_bf = 0;
}2.4 AVL树的查找
AVL树的查找就非常简单了，中序遍历：
//查找
const Node* find(Node* root,const T val)
{
if (!root) return nullptr;
if (root->_val == val) return root;
const Node* ret_left = find(root->_left, val);
if (ret_left) return ret_left;
return find(root->_right, val);
}2.5 AVL树的平衡检测
#include "AVLTree.h"
int main()
{
AVLTree<int> t;
常规的测试⽤例
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// 特殊的带有双旋场景的测试⽤例
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
t.Insert(e);
}
t.Printf();
t.Find(14);
t.Find(99);
return 0;
}创作不易，点个赞呗，蟹蟹啦~
