C++ AVL 树全解析！4 种旋转 + 插入实现 + 平衡检测，一篇吃透平衡二叉树
·
文章目录
前言：
前文C++ 二叉搜索树全解析！增删查改 + key/value 场景 + 完整代码，一篇通关，我们已经深入了解了搜索二叉树的定义 ，本篇我们将详解 搜索二叉树的变形- > 平衡搜索二叉树即AVL 树
正文：
1. AVL的概念
- AVL树是最先发明的⾃平衡⼆叉查找树，AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：它的左右⼦树都是AVL树，且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树，通过控制⾼度差去控制平衡
- AVL树实现这⾥我们引⼊⼀个平衡因⼦(balance factor)的概念，每个结点都有⼀个平衡因⼦，任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度，也就是说任何结点的平衡因⼦等于0/1/-1，AVL树并不是必须要平衡因⼦，但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡，就像⼀个⻛向标⼀样
- AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在 ，那么增删查改的效率也可以控制在logN ，相⽐⼆叉搜索树有了本质的提升
上面的数字即每个结点的平衡因子
显然该树不是稳定的AVL 树
2. AVL树的实现
2.1 AVL树的结构
namespace twg
{
//AVLTree 的节点
template<class K, class V>
struct AVLTreeNode
{
//数据
K _key;
V _val;
int _bf;//平衡因子 绝对值不大于1
AVLTreeNode* left;//左孩子
AVLTreeNode* right;//右孩子
AVLTreeNode* parent;
//默认构造
AVLTreeNode(const K& key = K(), const V& val = V())
:_key(key),
_val(val),
_bf(0),
left(nullptr),
right(nullptr),
parent(nullptr)
{
}
};
//AVLTree 适配器
template<typename K, typename V>
class AVLTree
{
typedef AVLTreeNode<typename K, typename V> Node;
public:
//
private:
Node* _root = nullptr;//根
}
}
2.2 AVL树的插⼊
【过程】：
- 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。
- 新增结点以后，只会影响祖先结点的⾼度，也就是可能会影响部分祖先结点的平衡因⼦，所以更新从新增结点->根结点路径上的平衡因⼦，实际中最坏情况下要更新到根，有些情况更新到中间就可以停⽌了，具体情况我们下⾯再详细分析
- 更新平衡因⼦过程中没有出现问题，则插⼊结束
- 更新平衡因⼦过程中出现不平衡，对不平衡⼦树旋转，旋转后本质调平衡的同时，本质降低了⼦树的⾼度，不会再影响上⼀层，所以插⼊结束
2.3 平衡因⼦更新
更新原则：
- 平衡因⼦ = 右⼦树⾼度-左⼦树⾼度
- 只有⼦树⾼度变化才会影响当前结点平衡因⼦
- 插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在parent的左⼦树，parent平衡因⼦–
- parent所在⼦树的⾼度是否变化决定了是否会继续往上更新
更新停⽌条件：
- 更新后parent的平衡因⼦等于0，更新中parent的平衡因⼦变化为-1->0 或者 1->0，说明更新前parent⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后parent所在的⼦树⾼度不变，不会影响parent的⽗亲结点的平衡因⼦，更新结束。
- 更新后parent的平衡因⼦等于1 或 -1，更新前更新中parent的平衡因⼦变化为0->1 或者 0->-1，说明更新前parent⼦树两边⼀样⾼，新增的插⼊结点后，parent所在的⼦树⼀边⾼⼀边低，parent所在的⼦树符合平衡要求，但是⾼度增加了1，会影响parent的⽗亲结点的平衡因⼦，所以要继续向上更新。
- 更新后parent的平衡因⼦等于2 或 -2，更新前更新中parent的平衡因⼦变化为1->2 或者 -1->-2，说明更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：1、把parent⼦树旋转平衡。2、降低parent⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新，插⼊结束。
- 不断更新，更新到根，跟的平衡因⼦是1或-1也停⽌了。
总结什么时候更新：
- 当新插入的结点影响子树高度变化时，就要向上更新从而判断是否旋转
- 当父节点的平衡因子达到2或者-2 时就要执行旋转逻辑 具体怎么旋转要根据场景判断
- 旋转完后 就不用向上更新 ，因为旋转的本质是维护局部子树的平衡，使其恢复到未插入新结点前该局部子树的高度 。
【结合图例】：
更新到10结点，平衡因⼦为2，10所在的⼦树已经不平衡，需要旋转处理
更新到中间结点，3为根的⼦树⾼度不变，不会影响上⼀层，更新结束
最坏更新到根停⽌
【插⼊结点及更新平衡因⼦的代码实现】：
//增 -> 插入
bool Insert(const K& key, const V& val)
{
//找新插入节点的位置
if (_root == nullptr)
{
//空树
_root = new Node(key, val);
return true;
}
//局部插入
//双指针循环找位置
Node* cur = _root;//从根开始向下找
Node* parent = nullptr;
while (cur)
{
//根据搜索二叉树的规则找
//根绝key
if (cur->_key <= key)
{
//右子树处
parent = cur;
cur = cur->right;
}
else if (cur->_key > key)
{
//左子树
parent = cur;
cur = cur->left;
}
}
//找到了新节点的位置
cur = new Node(key, val);
cur->parent = parent;
if (parent->_key>cur->_key)
{
//左孩子
parent->left = cur;
}
else
{
//右孩子
parent->right = cur;
}
//更新平衡因子
while (parent)
{
//插入的过程中更新平衡因子
if (parent->left == cur)
{
//左孩子 平衡因子--
parent->_bf--;
}
else if (parent->right == cur)
{
//右孩子 平衡因子++
parent->_bf++;
}
//根据parent的平衡因子 来执行不同的控平操作
if (parent->_bf == 0)
{
//完全平衡
//新节点的加入没有影响 二叉树的高度
break;
}
else if ((parent->_bf == -1) || (parent->_bf == 1))
{
//新节点的加入影响了 二叉树的高度
//向上寻找grandparent的平衡因子是否为 -2 || 2 从而进行旋转操作
cur = parent;
parent = parent->parent;
}
else
{
// 旋转
//根据情况来决定单旋还是双旋
//单旋
//左左-> 右单旋
if ((parent->_bf == -2) && (cur->_bf == -1))
{
RotateR(parent);
break;
}
//右右 -> 左单旋
else if ((parent->_bf == 2) && (cur->_bf == 1))
{
RotateL(parent);
break;
}
//双旋
//左右双旋
else if ((parent->_bf == -2) && (cur->_bf == 1))
{
//左右双旋
RotateLR(parent);
break;
}
//右左双旋
else if ((parent->_bf == 2) && (cur->_bf == -1))
{
//右左双旋
RotateRL(parent);
break;
}
}
}
}
这里的旋转不用管 下面我们会具体将如何旋转
2.3 旋转
2.3.1 旋转的原则
- 保持搜索树的规则
- 让旋转的树从不满⾜变平衡，其次降低旋转树的⾼度
旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。
树旋转是各子树的形态数不胜数 但是只要满足以下旋转的条件即可执行相应的旋转逻辑
右单旋
这里以抽象图为例，抽象图可代表所有有单旋的情况
- 本图1展⽰的是10为根的树，有a/b/c抽象为三棵⾼度为h的⼦树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树，是⼀种概括抽象表⽰，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体图2/图3/图4/图5进⾏了详细描述
- 在a⼦树中插⼊⼀个新结点，导致a⼦树的⾼度从h变成h+1，不断向上更新平衡因⼦，导致10的平衡因⼦从-1变成-2，10为根的树左右⾼度差超过1，违反平衡规则。10为根的树左边太⾼了，需要往右边旋转，控制两棵树的平衡。
- 旋转核⼼步骤，因为5 < b⼦树的值 < 10，将b变成10的左⼦树，10变成5的右⼦树，5变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的⾼度恢复到了插⼊之前的h+2，符合旋转原则。如果插⼊之前10整棵树的⼀个局部⼦树，旋转后不会再影响上⼀层，插⼊结束了
【右单旋代码实现】：
//左左 - > 右单旋
void RotateR(Node* root)
{
//右单旋 影响四个节点
Node* SubL = root->left;
Node* SubLR = SubL->right;
Node* grandparent = root->parent;
//先将 SubL的右孩子 即SubLR 链接到root 的左孩子处
root->left = SubLR;
//更新 SubLR 的父亲
if (SubLR)
{
SubLR->parent = root;
}
//再将 root 链接到 SubL 的右孩子处
SubL->right = root;
root->parent = SubL;
//更新SubL 的父亲
//判断root 是否为根
if (grandparent == nullptr)
{
//root 原为根
_root = SubL;
SubL->parent = nullptr;
}
else
{
//root 原 不为根
//SubL 替代root 的位置
SubL->parent = grandparent;
//更新grandparent 的孩子
if (grandparent->left == root)
{
grandparent->left = SubL;
}
else
{
grandparent->right = SubL;
}
}
//更新 root 和 SubL 的平衡因子
root->_bf = SubL->_bf = 0;
}
左单旋
- 本图6展⽰的是10为根的树，有a/b/c抽象为三棵⾼度为h的⼦树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树，是⼀种概括抽象表⽰，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体跟上⾯左旋类似。
- 在a⼦树中插⼊⼀个新结点，导致a⼦树的⾼度从h变成h+1，不断向上更新平衡因⼦，导致10的平衡因⼦从1变成2，10为根的树左右⾼度差超过1，违反平衡规则。10为根的树右边太⾼了，需要往左边旋转，控制两棵树的平衡
- 旋转核⼼步骤，因为10 < b⼦树的值 < 15，将b变成10的右⼦树，10变成15的左⼦树，15变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的⾼度恢复到了插⼊之前的h+2，符合旋转原则。如果插⼊之前10整棵树的⼀个局部⼦树，旋转后不会再影响上⼀层，插⼊结束了。
【左单旋代码实现】：
////旋转
//右右 -> 左单旋
void RotateL(Node* root)
{
//旋转影响四个节点 root SubR SubRL grandparent
Node* SubR = root->right;
Node* SubRL = SubR->left;
Node* grandparent = root->parent;
//先将SubR 的左孩子 即SubRL 链接到 root 的右孩子处
root->right = SubRL;
//更新SubRL 的父亲
if (SubRL)
{
SubRL->parent = root;
}
//再将 root 链接到SubR 的左孩子处
SubR->left = root;
root->parent = SubR;
//更新SubR 的父亲
//判断root 原来是否为根
if (grandparent == nullptr)
{
//root 原先为根，现在更新二叉搜索树的根
_root = SubR;
SubR->parent = nullptr;
}
else
{
//root 原先不为根 正常将SubR 替代root 的位置
SubR->parent = grandparent;
//更新grandparent 的孩子
if (grandparent->left == root)
{
grandparent->left = SubR;
}
else
{
grandparent->right = SubR;
}
}
//更新平衡因子
root->_bf = SubR->_bf = 0;//抽象图的结果 可以涵盖所有左单旋后树
}
左右双旋
- 场景1：h >= 1时，新增结点插⼊在e⼦树，e⼦树⾼度从h-1并为h并不断更新8->5->10平衡因⼦，引发旋转，其中8的平衡因⼦为-1，旋转后8和5平衡因⼦为0，10平衡因⼦为1。
- 场景2：h >= 1时，新增结点插⼊在f⼦树，f⼦树⾼度从h-1变为h并不断更新8->5->10平衡因⼦，引发旋转，其中8的平衡因⼦为1，旋转后8和10平衡因⼦为0，5平衡因⼦为-1。
- 场景3：h == 0时，a/b/c都是空树，b⾃⼰就是⼀个新增结点，不断更新5->10平衡因⼦，引发旋转，其中8的平衡因⼦为0，旋转后8和10和5平衡因⼦均为0。
【左右双旋代码实现】：
//左右双旋
void RotateLR(Node* root)
{
//借助两次单旋 完成双旋
//本函数只是用来根据 SubLR 的 平衡因子 的多少 来更新平衡因子
Node* SubL = root->left;
Node* SubLR = SubL->right;
int bf = SubLR->_bf;
//先左单旋
RotateL(root->left);//SubL
//再右单旋
RotateR(root);
if (bf == 0)
{
//这种情况 下的双旋 一定是向上寻找是否双旋才会出现的
//因为 新节点的插入导致的左右双旋 bf 必定为 1 或者 -1
//因此两次单旋更改的平衡因子 不用动
SubLR->_bf = 0;
root->_bf = 0;
SubL->_bf = 0;
}
else if (bf == 1)
{
SubLR->_bf = 0;
root->_bf = 0;
SubL->_bf = -1;
}
else if(bf==-1)
{
SubLR->_bf = 0;
root->_bf = 1;
SubL->_bf = 0;
}
else
{
//走到这就报错
assert(false);
}
}
右左双旋
- 场景1：h >= 1时，新增结点插⼊在e⼦树，e⼦树⾼度从h-1变为h并不断更新12->15->10平衡因⼦，引发旋转，其中12的平衡因⼦为-1，旋转后10和12平衡因⼦为0，15平衡因⼦为1。
- 场景2：h >= 1时，新增结点插⼊在f⼦树，f⼦树⾼度从h-1变为h并不断更新12->15->10平衡因⼦，引发旋转，其中12的平衡因⼦为1，旋转后15和12平衡因⼦为0，10平衡因⼦为-1。
- 场景3：h == 0时，a/b/c都是空树，b⾃⼰就是⼀个新增结点，不断更新15->10平衡因⼦，引发旋转，其中12的平衡因⼦为0，旋转后10和12和15平衡因⼦均为0。
【右左双旋代码实现】：
//右左双旋
void RotateRL(Node* root)
{
// 借助两次单旋
//本函数 只 根据 SubRL 的 平衡因子 的多少 更新相应的情况下的平衡因子
Node* SubR = root->right;
Node* SubRL = SubR->left;
int bf = SubRL->_bf;
//先右旋
RotateR(root->right);//SubR
//再左旋
RotateL(root);
if (bf == 0)
{
//这种情况 下的双旋 一定是向上寻找是否双旋才会出现的
//因为 新节点的插入导致的右左双旋 bf 必定为 1 或者 -1
//因此两次单旋更改的平衡因子 不用动
SubRL->_bf = 0;
root->_bf = 0;
SubR->_bf = 0;
}
else if (bf == 1)
{
SubRL->_bf = 0;
root->_bf = -1;
SubR->_bf = 0;
}
else if (bf == -1)
{
SubRL->_bf = 0;
root->_bf = 0;
SubR->_bf = 1;
}
else
{
assert(false);
}
}
2.4 AVL树的查找
那⼆叉搜索树逻辑实现即可，搜索效率为 O(logN)
【代码实现】：
//AVL 树的查找
Node* Find(const K& key)
{
//AVL本身就是平衡搜索二叉树 按照二叉搜索树的逻辑寻找即可
//循环指针
Node* cur = _root;//从根往下找
while (cur)
{
if (cur->_key < key)
{
//走右子树
cur = cur->right;
}
else if (cur->_key > key)
{
//走左子树
cur = cur->left;
}
else
{
//找到了
return cur;
}
}
//没找到
return nullptr;
}
2.5 AVL树平衡检测
我们实现的AVL树是否合格，我们通过检查左右⼦树⾼度差的的程序进⾏反向验证，同时检查⼀下结点的平衡因⼦更新是否出现了问题。
【代码实现】：
//AVL 树的判断
//通过检查AVL 树的左右子树的高度差，和平衡因子的检测 来判断是否为AVL 树
//检查高度
int _Height(const Node* root)
{
//空树为 0
if (root == nullptr)
{
return 0;
}
int leftHeight = _Height(root->left);
int rightHeight = _Height(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool Check(const Node* root)
{
//递归出口
if (root == nullptr)
{
//空树 也是AVL 树
return true;
}
//高度检测
//左右子树的高度差不能超过2
int leftHeight = _Height(root->left);
int rightHeight = _Height(root->right);
int diff = rightHeight - leftHeight;//左右子树的高度差
if (abs(diff) >= 2)//
{
//高度检测不通过
cout << "高度检测不通过 该树不是AVL 树" << endl;
return false;
}
//高度检测通过 若是 局部树内某平衡因子有错呢？
//检测平衡因子是否非法
if (root->_bf != diff)
{
//该树平衡因子非法
cout << " 平衡因子非法" << endl;
return false;
}
//递归
//左右子树也是合法才行
return Check(root->left) && Check(root->right);
}
结语：
AVL 树以 “平衡因子 + 旋转” 为核心，将二叉搜索树的性能稳定在 logN 级，四种旋转操作更是平衡调整的精髓。掌握插入后平衡因子更新逻辑与旋转场景适配，便抓住了 AVL 树的核心。它虽旋转频繁，但为红黑树等平衡树奠定基础
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
54
0- 0
已为社区贡献1条内容
所有评论(0)