平衡搜索树-AVL树 图文详解 (万字长文)
目录[*]AVL树
[*]AVL树的概念
[*]AVL树节点的定义：
[*]AVL树的插入
[*]基本情况分析
[*]平衡因子对应的操作
[*]旋转操作
[*]分析需要旋转的情况
[*]结论
[*]4种旋转操方法与特性
[*]6种双旋平衡因子特性
[*]代码实现
[*]四种旋转实现
[*]插入操作实现
[*]树高度与是否平衡树判断实现
[*]其他实现
[*]插入验证
[*]BenchMark
[*]环境
[*]测试工具和方法
[*]测试结果：
AVL树
AVL树的概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而淘汰平均搜索长度。
一棵AVL树大概是空树，大概是具有以下性质的二叉搜索树：
[*]它的左右子树都是AVL树
[*]左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162857493-884752224.png
(默认平衡因子=右子树高度-左子树高度)
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在$O(log_2 n)$，搜索时间复杂度O($log_2 n$)。
AVL树是由BST二叉搜索树改进而来,基本概念参考BST篇,本篇文章不再具体描述.
AVL树节点的定义：
template<class K, class V>
struct AVLTreeNode
{
//三叉链: left right parent
AVLTreeNode* _left; // 该节点的左孩子
AVLTreeNode* _right; // 该节点的右孩子
AVLTreeNode* _parent; // 该节点的双亲
std::pair<K,V> _kv; // 键值对
int _bf; // 该节点的平衡因子 balance factor
AVLTreeNode(const std::pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};AVL树的插入
基本情况分析
AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：
[*]按照二叉搜索树的方式插入新节点
[*]调整节点的平衡因子
a. 更新父结点平衡因子
b. 根据父结点的平衡因子进行相应的操作
对于平衡因子
插入新结点后,起首可能会影响父结点的平衡因子,迭代往上,可能还会影响部分或全部(到根节点)祖先结点的平衡因子.
具体地说,即插入新结点后,需要根据父结点平衡因子的情况,决定是否继续往上对祖结点进行更新平衡因子,最多到达根结点.
平衡因子对应的操作
父结点平衡因子如何决定是否继续往上更新? 取决于更新后parent->_bf的值
[*]若parent->_bf == 1 || parent->_bf == -1 ,阐明插入前的父结点一定是左右子树高度相等,即_bf为0.新增结点后父结点所在子树高度一定发生变化,爷爷结点所在子树也可能发生变化,因此需要进行迭代更新祖先平衡因子.
不可能是2或-2变成1或-1,因为这是AVL树的插入,至少先保证是AVL树才能插入
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162858281-1928190458.png
[*]若parent->_bf == 2 || parent->_bf == -2 ,阐明插入前的父结点所在子树一边高一边低,之后新结点恰好插入到了高的一边,导致不平衡,需要做旋转操作,调整平衡.
[*]parent->_bf == 0,插入后父结点的平衡因子平衡,阐明原先父结点的左右子树是一边高一边低,然后插入刚好插到了低的一边,使其平衡.插入结束.
旋转操作
分析需要旋转的情况
起首，要针对AVL子树，找出/抽象出可能发生旋转的情况。
一棵可能发生旋转的树至少高度差为1，即两个结点以上。（前提）
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162858945-246946983.png
（可能会发生旋转的子树至少两个结点以上）
其中a,b,c是三棵AVL子树
[*]当子树高度h==0时,即a、b、c都为空树
[*]当子树高度h==1时,a、b、c都是叶子结点
[*]当子树高度h==2时,a、b、c分别有三种情况
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162859514-996371186.png
此时这个AVL子树有3*3*3=27种情况：a为x/y/z，b为x/y/z，c为x/y/z。
[*]云云往下，还有更多的情况，但全部形状都可以用图中模型来取代。
以h==2为例，只有当b或c为z情况时，插入到b或c子树会影响到根结点（30），并使其发生旋转。
其他情况都无法使其发生旋转。因此，当前可以总结出2种需要旋转的情况：
[*]c为z时，插到c中（左左）
[*]b为z时，插到b中（左右）
左左：较高的子树是左孩子（60）所在子树，插到左孩子（60）的左子树上（c）引发根（30）旋转的情况叫“左左”。
顺口：插在较高左子树的左孩子上。
同理，水平镜像翻转的AVL子树也同理
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162900046-458989986.png
[*]c为z时，插到c中（右右）
[*]b为z时，插到b中（右左）
结论
合并起来总共4种需要旋转的情况，验证其他高度也同样云云。
其中插入b子树使30结点发生旋转的情况：a为x/y/z，b为z，c为x/y/z，总共3*3=9种
其中插入c子树使30结点发生旋转的情况：a为x/y/z，b为x/y/z，c为z，总共3*3=9种
特例的数量非常多，无法穷举。
4种旋转操方法与特性
[*]新节点插入较高左子树的左侧---左左：右单旋
[*]特性
父：-2
子：-1
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162900638-1350195205.png
最左边高，旧根的左孩子变成新根，旧根成为新根的右孩子，同时领养新根的旧右孩子。
儿子上位 -- 儿子当根
右单旋（主角是儿子）：老爹在我的右上方，让老爹以我为轴，旋转到我的右下方
[*]新节点插入较高右子树的右侧---右右：左单旋
[*]特性
父：2
子：1
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162901451-1383026311.png
最右边高，旧根的右孩子变成新根，旧根成为新根的左孩子，同时领养新根的旧左孩子。
[*]新节点插入较高左子树的右侧---左右：先左单旋再右单旋
[*]特性
父：-2
子：1
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162902033-1684257975.png
[*]旧根的左儿子的右孩子（简称右孙子）高：让右孙子成为旧根的左孩子，旧左孩子变成孙子的左孩子，同时领养孙子的左孩子。 -- 对右孙子做左旋操作
[*]右孙子成为旧根的新左儿子，再对新作儿子做右旋操作即可。
孙子上位 --- 孙子当根
感性描述：先左单旋再右单旋（孙子是主角）：我在孙子左边，我的老爹在孙子右边，然后让孙子的爹（我）左旋下来，孙子成为我的爹，我的旧爹成为孙子的爹；末了再让孙子的新爹右旋下来。
描述2： 两次旋转分别用途： 1. 转化成标准单旋； 2.标准单旋
[*]新节点插入较高右子树的左侧---右左：先右单旋再左单旋
[*]特性
父：2
子：-1
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162902975-1867527890.png
总共4种旋转的情况：
[*]右旋（左左）
[*]左旋（右右)
[*]先左旋再右旋（左右）
[*]先右旋再左旋（右左）
简要图：
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162903566-747857239.png
6种双旋平衡因子特性
容易发现单旋平衡因子都是0（高度差为0），而双旋平衡因子较为复杂，观察规律总结出一共6种情况。
[*]左右左（h>0)
[*]旧（特性）
孙：-1
[*]新
父：1
子：0
孙：0
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162904092-970686812.png
[*]左右右(h>0)
[*]旧（特性）
孙：1
[*]新
父：0
子：-1
孙：0
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162904764-1829130190.png
[*]右左右（h>0）
[*]旧（特性）
孙：1
[*]新
父：-1
子：0
孙：0
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162905337-908681529.png
[*]右左左（h>0）
[*]旧（特性）
孙：-1
[*]新
父：0
子：1
孙：0
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162905914-1277671262.png
[*]左右，特例（h==0)
[*]旧（特性）
孙：0
[*]新
父：0
子：0
孙：0
https://img2023.cnblogs.com/blog/2921710/202408/2921710-20240823162906516-192776534.png
[*]右左（h==0)，与5相同
[*]旧（特性）
孙：0
[*]新
父：0
子：0
孙：0
代码实现
四种旋转实现
//1. 右右
void RotateL(Node* parent) {
//. 记录爷爷(父亲的父亲)
//. 我是父的右儿子(我是主角)
//. 记录下我的左子树(托管)
//旋转(爷、父、子关系重新调整）
// 成为爷爷的右儿子 (如果没有爷爷,则跳过;且说明父是根,更新我成为根)
// 把我的左子树托管给父成为他的右孩子
// 旧父成为我的左儿子,旧父的父更新成我
//. 更新平衡因子
//. 记录爷爷(父亲的父亲)
//. 我是父的右儿子
//. 记录下我的左子树
Node* pparent = parent->_parent;
Node* cur = parent->_right;
Node* leftchild = cur->_left;
//旋转
//. 成为爷爷的右儿子 (如果没有爷爷,则跳过;且说明父是根,更新我成为根)
if (pparent) { //有爷爷
if(parent == pparent->_left)
pparent->_left = cur;
else {
pparent->_right = cur;
}
cur->_parent = pparent; //三叉链维护
}
else { //没有爷爷,父亲是根
cur->_parent = nullptr;
_root = cur;
}
//. 父子地位交换
parent->_right = leftchild;
if (leftchild) { //三叉链维护
leftchild->_parent = parent;
}
cur->_left = parent;
parent->_parent = cur;
//旋转 【end】
//更新平衡因子
cur->_bf = 0;
parent->_bf = 0;
}
//2. 左左
void RotateR(Node* parent) {
//. 记录爷爷
//. 我是父的左儿子
//. 记录下我的右子树
Node* pparent = parent->_parent;
Node* cur = parent->_left;
Node* rightChild = cur->_right;
//旋转
//. 成为爷爷的左儿子 (如果没有爷爷,则跳过;且说明父是根,更新我成为根)
if (pparent) { //有爷爷
if (parent == pparent->_left)
pparent->_left = cur;
else {
pparent->_right = cur;
}
cur->_parent = pparent; //三叉链维护
}
else { //没有爷爷,父亲是根
cur->_parent = nullptr;
_root = cur;
}
//. 父子地位交换
parent->_left = rightChild;
if (rightChild) { //三叉链维护
rightChild->_parent = parent;
}
cur->_right = parent;
parent->_parent = cur;
//旋转 【end】
//更新平衡因子
cur->_bf = 0;
parent->_bf = 0;
}
//3. 左右
void RotateLR(Node* parent) {
//我是儿子,但是主角是孙子
//记录下孙子
//记录下孙子的平衡因子(特征)
//对孙子进行左单旋,再右旋
//更新平衡因子
Node* cur = parent->_left;
Node* grandson = cur->_right;
int bf = grandson->_bf;
RotateL(cur);
RotateR(grandson->_parent);
//三种情况
if (bf == 0) {
parent->_bf = 0;
cur->_bf = 0;
grandson->_bf = 0;
}
else if (bf == 1) {
parent->_bf = 0;
cur->_bf = -1;
grandson->_bf = 0;
}
else if (bf == -1) {
parent->_bf = 1;
cur->_bf = 0;
grandson->_bf = 0;
}
else {
assert(false); //错误检查
}
}
//4. 右左
void RotateRL(Node* parent) {
//我是儿子(父的右孩子),但是主角是孙子
//记录下孙子(我的左孩子)
//记录下孙子的平衡因子(特征)
//对孙子进行右单旋,再左单旋
//更新平衡因子
Node* cur = parent->_right;
Node* grandson = cur->_left;
int bf = grandson->_bf;
RotateR(cur); //将孙子的爹,就是我,进行右单旋
RotateL(grandson->_parent); //将儿子的新爹进行左单旋
//三种情况
if (bf == 0) {
parent->_bf = 0;
cur->_bf = 0;
grandson->_bf = 0;
}
else if (bf == 1) {
parent->_bf = -1;
cur->_bf = 0;
grandson->_bf = 0;
}
else if (bf == -1) {
parent->_bf = 0;
cur->_bf = 1;
grandson->_bf = 0;
}
else {
assert(false);
}
}插入操作实现
bool Insert(const std::pair<K,V> kv) {
//第一个结点做根
if (_root == nullptr) {
_root = new Node(kv);
_size++;
return true;
}
//搜索
Node* parent = _root;
Node* cur = _root;
while (cur) {
//大于往右走
if (kv.first > cur->_kv.first) {
parent = cur;
cur = cur->_right;
}
//小于往左走
else if (kv.first < cur->_kv.first) {
parent = cur;
cur = cur->_left;
}
//找到了,存在相同的key
else {
return false;
}
} //循环搜索...
//不存在,可以插入
cur = new Node(kv); //new后,cur值发生改变,之后都不能使用地址进行比较
if (cur->_kv.first < parent->_kv.first) {
parent->_left = cur;
}
else {
parent->_right = cur;
}
cur->_parent = parent; //三叉链链上父结点
_size++;
//调整平衡因子 : 最多到根,根的parent为nullptr
while (parent) {
//更新平衡因子
if (cur->_kv.first < parent->_kv.first) {
parent->_bf--;
}
else {
parent->_bf++;
}
//看是否需要调整
if (parent->_bf == 1 || parent->_bf == -1) {
cur = parent;
parent = parent->_parent;
}
else if(parent->_bf == 0){
break;
}
else if(parent->_bf == 2 || parent->_bf == -2){
if (parent->_bf == -2 && cur->_bf == -1) { //左左
RotateR(parent);
}
else if (parent->_bf == 2 && cur->_bf == 1) { //右右
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1) {//左右
RotateLR(parent);
}
else if(parent->_bf == 2 && cur->_bf == -1){ //右左
RotateRL(parent);
}
else { //错误检查
assert(false);
}
break;
}
else {
assert(false);
}
}
return true;
}树高度与是否平衡树判断实现
size_t Hight() {
return _Hight(_root);
}
bool IsBalance() {
return _IsBalance(_root);
}
size_t _Hight(Node* root) {
if (root == 0) return 0; //空
size_t leftH = _Hight(root->_left);
size_t rightH = _Hight(root->_right);
return std::max(leftH, rightH) + 1; //+1:自己高度为1
}
bool _IsBalance(Node* root) {
if (root == nullptr) return true;
int leftH = _Hight(root->_left);
int rightH = _Hight(root->_right);
int bf = rightH-leftH;
returnbf == root->_bf //平衡因子
&& (bf > -2 && bf < 2) //高度差
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}其他实现
#include#include#includetemplatestruct AVLTreeNode { //三叉链 AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; int _bf; //balance factor std::pair _kv; AVLTreeNode(const std::pair& kv) :_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv) {}};templateclass AVLTree {public: using Node = AVLTreeNode; AVLTree() :_root(nullptr) ,_size(0) {}public: void InOrder() { _InOrder(_root); std::cout
页:
[1]