作者：@小萌新
专栏：@数据结构进阶
作者简介：大二学生 希望能和大家一起进步！
本篇博客简介：介绍高阶数据结构:AVL树
AVL树的概念
首先抛出一个问题 为什么AVL树会诞生呢？
还记不记得我们在学习二叉搜索树最后总结的时候说的一句话
在二叉搜索树是完全二叉树的情况下效率最高 此时的效率是 LogN
在二叉搜索时是单边树的情况下效率最差 此时效率退化至 N
为了解决这个退化的效率问题 AVL树诞生了
AVL树是由两位俄国科学家G.M. Adelson-Velsky和E.M.Landis在1962年发明的。他们在一篇论文中提出了AVL树这一概念，并将其命名为"AVL树"，以纪念他们的姓氏的首字母。
AVL树是一种自平衡二叉搜索树，它能够保证插入、删除和查找操作的时间复杂度都是O(log n)，因此在很多场合下都很有用。
AVL树可以是一颗空树 也可以是具有以下性质的一颗二叉搜索树
- 它的左右子树都是AVL树
- 树的左右子树高度差不超过一 （以下样例均为右子树减左子树）
上面就是一棵AVL树
蓝色数字表示的是左右子树的高度差值(以下简称平衡因子) 它们都是不超过1的
红色的数字表示储存数据的值 符合二叉搜索树的性质
我们可以发现 当一颗二叉搜索树是AVL树的时候 假设它一共有N个节点 那么它的高度非常接近LogN 同样的搜索效率也接近LogN
这也就解决了单边树的低效问题
AVL树节点类的定义
我们这里使用KV模型来实现AVL树
为了方便后续的操作 使用三叉链结构来完成它
一个节点除了指向它的左右两个子节点之外还指向它的父节点 一共三个指针 所以称为三叉链
此外 我们还增加一个int类型的数据 来记录平衡因子
代码表示如下
template<class K, class V>
struct AVLTreeNode
{
// 三叉连
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
// 平衡因子
int _bf;
// 储存的键值对
pair<K, V> _kv;
// 构造函数
AVLTreeNode(const pair<K , V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_bf(0) //因为构造出来之后没有左右子树 所以说平衡因子为0
{
}
};
AVL树的插入
AVL树的插入满足下面几个步骤
- 遵循二叉搜索树的插入原则 找到待插入位置
- 找到插入位置之后 插入节点
- 更新平衡因子 如果平衡因子不满足AVL树的条件 则使之满足
第一步第二步很简单 如果还有不明白的同学可以参考这篇博客
接下来我们重点学习第三步
由于我们插入一个节点之后 只有可能是这个节点的父节点的高度受到影响
所以说我们只需要更新它的祖先节点 这也是我们为什么设计成三叉链结构的原因 - 方便找祖先节点
（这个图稍微有点漏洞 我们这里假设新增的节点是6.5 前面的节点都是浮点数）
新增节点之后我们开始更新平衡因子 遵循下面的规则
- 如果新增节点在父节点的右边 则平衡因子++
- 如果新增节点在父节点的左边 则平衡因子–
这里我们可以发现 如果有一个父节点的平衡因子更新成了0 则无需向上继续更新了
怎么解释这个现象呢？
我们都知道 平衡因子是根据父节点左右子树的高度来确定的
如果父节点的平衡因子被更新成了0 那么肯定就说明 原来有一边的高度是大于另一边的 而且是大于1
插入一个新的节点之后两边的高度差就被填平了
那么对于父节点的父节点来说 这边子树的高度并没有变化 所以说我们不需要向上更新了
所以说我们有具体的规则如下
- 如果父节点的平衡因子更新之后结果为1或者-1 则需要继续向上更新祖先节点的平衡因子
- 如果父节点的平衡因子更新之后结果为0 则不需要继续向上更新祖先节点的平衡因子
- 如果父节点的平衡因子更新之后结果为2或者-2 则需要进行旋转操作来处理异常
我们假设目前的节点是cur 它的父节点是parent
因为我们执行的是插入操作 所以说我们的节点肯定是增加的 就看增加的是父节点的左子树还是右子树
因为我们不能确定是左子树还是右子树 所以要执行判断
- 如果cur是parent的左节点 则平衡因子–
- 如果cur是parent的右节点 则平衡因子++
但是到这里还没完 我们要需要继续向上更新 执行下面的代码
cur = parent;
parent = parent->_parent;
最差的情况下 我们一直要更新到根节点
按照上面的规则 我们写出代码
bool insert(const pair <K,V>& kv)
{
if (_root == nullptr) // 如果AVL树为空 则直接为其根节点
{
_root = new Node(kv);
return true;
}
// 如果不为空 则按照二叉树的插入方式 通过key值 即first来比较
Node* cur = _root; // cur确定当前位置
Node* parent = nullptr; // parent最后连接用
while (cur) // 当cur不为空的时候一直走
{
if (kv.first > cur->_kv.first) // 如果插入值大于当前节点 向右移
{
cur = cur->_right;
parent = cur;
}
else if (kv.first < cur->_kv.first) // 如果插入值小于当前节点 向右移
{
cur = cur->_left;
parent = cur;
}
else // 到这里这种情况说明等于 则插入失败 返回false
{
return false;
}
}
// 将待插入节点插入到树中
cur = new Node(kv);
// 根据kv的key值来分辨插入的是左子树还是右子树
if (kv.first > parent->_kv.first)
{
parent->_right = cur;
cur->_parent = parent; // 因为是三叉链 所以要更新父节点
}
else // 因为走到这里了kv的key值不可能相等 所以说else就表示小于
{
parent->_left = cur;
cur->_parent = parent; // 因为是三叉链 所以要更新父节点
}
// 更新平衡因子
while (cur != _root) // 最坏的情况 一直更新到根节点 但是cur不可能到根节点
{
// 如果是右则平衡因子++ 反之则--
if (cur = parent->_left)
{
parent->_bf--;
}
else if (cur = parent->_right)
{
parent->_bf++;
}
// 平衡因子更新完毕 此时开始查看父亲节点的平衡因子是多少 是否结束 是否需要旋转
if (parent->_bf == 0) // 如果父亲的平衡因子是0 则停止更新 直接返回
{
return true;
}
else if (parent->_bf == 1 || parent->_bf == -1) // 如果父亲的平衡因子是1或-1 则继续往上更新
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) // 如果父亲的平衡因子是2或-2 则进行旋转操作
{
// 旋转
}
}
}
省略了旋转操作的插入代码就在上面 接下来我们重点研究下AVL的旋转操作
AVL树的旋转
首先我们要明确一点 当parent节点的平衡因子是2或者-2时候 cur的平衡因子必然是1或者-1
因为如果cur的平衡因子是0 有两种情况
- cur为新增节点 这个时候由于我们插入的是AVL树 所以其父节点只有可能是1 -1 或者0
- cur为更新后的节点 此时cur为其子节点的父节点 其平衡因子更新到了0 不会继续向上更新 所以cur的父节点一定是有正常的平衡因子 1 -1 或者0
所以说我们这里就有四种情况
- parent的平衡因子是2 cur的平衡因子是1
- parent的平衡因子是2 cur的平衡因子是-1
- parent的平衡因子是-2 cur的平衡因子是1
- parent的平衡因子是-2 cur的平衡因子是-1
然后我们根据这四种情况来讨论如何旋转
左单旋
从上图我们可以观察发现 parent的平衡因子被更新为了2 此时肯定要触发旋转
旋转后的图片大概是这样子
经过旋转后 平衡因子全部恢复正常 并且此时将这颗二叉树作为一个整体 它的高度还是h+2
所以不用继续往上更新平衡因子了
那么我们具体来看看实现左单旋要分几步
- 让 subr 左子树 subrl 成为 parent 的右子树
- 让 parent 成为 subr 的左子树
- 让 subr 作为整个子树的根 （如果parent不是根节点的话）
- 更新平衡因子
此时 subr 和 parent 的平衡因子都更新为0
而由于二叉搜索树的性质 所有的节点是从小到大排列的 我们这个旋转并没有改变这个性质 所以说这个旋转是完全合法的
此外 观察第一张图我们可以知道
左单旋对应着 parent的平衡因子是2 cur的平衡因子是1 这种情况
我们左单旋的代码表示如下
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* grandparent = parent->_parent;
// 建立subR和parent的联系
subR->_left = parent;
parent->_parent = subR;
// 建立parent和subRL的联系
parent->_right = subRL;
if (subRL) // 有可能subRL为空
{
subRL->_parent = parent;
}
// 建立grandparent和sunR的联系
// 这里要分grandparent是否存在以及parent是grandparent的左还是右
if (grandparent) // 如果进去了 则说明grandparent存在
{
// 如果存在 要分清楚parent在左边还是右边
if (grandparent->_left == parent)
{
grandparent->_left = subR;
}
else
{
grandparent->_right = subR;
}
subR->_parent = grandparent;
}
// 否则就是不存在 我们更新_root 并且将subR的父节点置空
else
{
_root = subR;
subR->_parent = nullptr;
}
// 更新平衡因子
subR->_bf = 0;
parent->_bf = 0;
}
只要按照上面的步骤一行行写 应该是不难理解的
这里尤其要注意的是 我们使用的是不熟悉的三叉链结构
右单旋
从上图我们可以观察发现 parent的平衡因子被更新为了-2 此时肯定要触发旋转
旋转后的图片大概是这样子
经过旋转后 平衡因子全部恢复正常 并且此时将这颗二叉树作为一个整体 它的高度还是h+2
所以不用继续往上更新平衡因子了
那么我们具体来看看实现右单旋要分几步
- 让 subl 的右子树 sublr 成为 parent 的左子树
- 让 parent 成为 subl 的左子树
- 让 subr 作为整个子树的根 （如果parent不是根节点的话）
- 更新平衡因子
此时 subl 和 parent 的平衡因子都更新为0
而由于二叉搜索树的性质 所有的节点是从小到大排列的 我们这个旋转并没有改变这个性质 所以说这个旋转是完全合法的
此外 观察第一张图我们可以知道
右单旋对应着 parent 的平衡因子是-2 cur 的平衡因子是-1 这种情况
我们右单旋的代码表示如下
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* grandparent = parent->_parent;
// 建立subL和parent之间的联系
subL->_right = parent;
parent->_parent = subL;
// 建立parent和subLR之间的联系
parent->_left = subLR;
if (subLR) // subLR可能不存在
{
subLR->_parent = parent;
}
// 建立grandparent和subl之间的联系
// 这里要分grandparent是否存在以及parent是grandparent的左还是右
if (grandparent)
{
// 如果存在 要分清楚parent在左边还是右边
if (grandparent->_left == parent)
{
grandparent->_left = subL;
}
else
{
grandparent->_right = subL;
}
subL->_parent = grandparent;
}
else // 这里就是表示parent就是根节点
{
_root = subL;
subL->_parent = nullptr;
}
// 更新平衡因子
subL->_bf = 0;
parent->_bf = 0;
}
左右双旋
左右双旋一般分三步走 图片表示如下
第一步 插入新增节点 触发旋转机制
第二步 以30为旋转点进行左单旋
第三步 以90为旋转点进行右单旋
左右双旋的步骤如下
- 以subL为旋转点进行左单旋
- 以parent为旋转点进行右单旋
- 更新平衡因子
而由于二叉搜索树的性质 所有的节点是从小到大排列的 我们这个旋转并没有改变这个性质 所以说这个旋转是完全合法的
此外 观察第二张图我们可以知道
左右双旋对应着 parent 的平衡因子是-2 cur 的平衡因子是1 这种情况
左右双旋后 平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况
- 当sublr的平衡因子是-1时 左右双旋后parent subl sublr的平衡因子分别更新为 1 0 0
- 当sublr的平衡因子是 1时 左右双旋后parent subl sublr的平衡因子分别更新为 0 -1 0
- 当sublr的平衡因子是 0时 左右双旋后parent subl sublr的平衡因子分别更新为 0 0 0
产生这三种情况的原因分别是
插入的节点可能是sublr 的左子树 右子树 或者是sublr本身
代码表示如下
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = parent->_left->_right;
int bf = subLR->_bf;
// 以subL作为旋转点左单旋
RotateL(subL);
// 以parent作为旋转点右单旋
RotateR(parent);
// 平衡因子
if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
右左单旋
右左双旋一般分三步走 图片表示如下
第一步 插入新增节点 触发旋转机制
第二步 以90作为节点进行右单旋
第三步 以30作为节点进行左单旋
右左双旋的步骤如下
- 以subR为旋转点进行右单旋
- 以parent为旋转点进行左单旋
- 更新平衡因子
而由于二叉搜索树的性质 所有的节点是从小到大排列的 我们这个旋转并没有改变这个性质 所以说这个旋转是完全合法的
此外 观察第二张图我们可以知道
右左双旋对应着 parent 的平衡因子是2 cur 的平衡因子是-1 这种情况
右左双旋后 平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况
- 当subrl的平衡因子是-1时 左右双旋后parent subr subrl的平衡因子分别更新为 1 0 0
- 当subrl的平衡因子是-1时 左右双旋后parent subr subrl的平衡因子分别更新为 0 -1 0
- 当subrl的平衡因子是-1时 左右双旋后parent subr subrl的平衡因子分别更新为 0 0 0
产生这三种情况的原因分别是
插入的节点可能是subrl 的左子树 右子树 或者是subrl本身
代码表示如下
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
// 以subR为轴进行右单旋
RotateR(subR);
// 以parent为轴进行左单旋
RotateL(parent);
// 更新平衡因子
if (bf == 1)
{
subRL->_bf = 0;
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{
subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 1;
}
else if (bf == 0)
{
subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 0;
}
else
{
assert(false);
}
}
AVL树的验证
首先AVL树是一颗二叉搜索树 所以说它满足中序遍历后是有序的这个原则 我们可以使用中序遍历来验证
代码表示如下
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << root->_kv.first << " ";
_Inorder(root->_right);
}
void Inorder()
{
_Inorder(_root);
}
但是中序遍历只能证明这棵树是二叉搜索树 要证明它是AVL树我们必须还要证明它的平衡因子全部无异常
我们可以从根节点开始 往上遍历每个子树来判断它是否是AVL树 如果全部是AVL树 则可以验证
如果有一颗不是 则证明不是AVL树
//判断是否为AVL树
bool IsAVLTree()
{
int hight = 0; //输出型参数
return _IsBalanced(_root, hight);
}
//检测二叉树是否平衡
bool _IsBalanced(Node* root, int& hight)
{
if (root == nullptr) //空树是平衡二叉树
{
hight = 0; //空树的高度为0
return true;
}
//先判断左子树
int leftHight = 0;
if (_IsBalanced(root->_left, leftHight) == false)
return false;
//再判断右子树
int rightHight = 0;
if (_IsBalanced(root->_right, rightHight) == false)
return false;
//检查该结点的平衡因子
if (rightHight - leftHight != root->_bf)
{
cout << "平衡因子设置异常：" << root->_kv.first << endl;
}
//把左右子树的高度中的较大值+1作为当前树的高度返回给上一层
hight = max(leftHight, rightHight) + 1;
return abs(rightHight - leftHight) < 2; //平衡二叉树的条件
}
AVL树的查找
AVL树的查找方式与二叉搜索树相同
- 如果树为空树 则查找失败 返回nullptr
- 如果key值小于当前节点 则进入当前节点的子树查找
- 如果key值大于当前节点 则进入当前节点的子树查找
- 如果key值等于当前节点 则返回当前节点
代码表示如下
Node* find(const K& key)
{
Node* cur = _root;
while (cur) // 一直查找到空为止
{
if (key < cur->_kv.first) // 小于
{
cur = cur->_left;
}
else if (key < cur->_kv.first) // 大于
{
cur = cur->_right;
}
else // 等于
{
return cur
}
}
// 走到这里就是没找到
return nullptr;
}
AVL树的修改
我们所说的修改一般是值对于value值的修改
一般步骤如下
- 找到对应的key值的结点
- 对其value值进行修改
代码表示如下
bool Modify(const K& key, const V& value)
{
Node* ret = find(key);
// 有可能不存在
if (ret == nullptr)
{
return false;
}
ret->_kv.second = value;
return true;
}
AVL树的删除
AVL树的删除满足下面几个步骤
- 遵循二叉搜索树的删除原则 找到待删除位置
- 找到删除位置之后 删除节点
- 更新平衡因子 如果平衡因子不满足AVL树的条件 则使之满足
由于我们学习AVL树主要是为了后面的红黑树做铺垫 需要重点掌握的是AVL树的插入
并且AVL树的删除在平时的笔试面试中考察的很少 或者说几乎没有考察 所以同学们可以跳过这一部分的学习
AVL树的性能
AVL树是一颗近乎完全二叉树的二叉搜索树 所以说它查询的时间复杂度非常低 为Log N
但是如果要对于AVL树做一些结构修改的操作 它的性能就会十分低下 比如在插入和删除时 可能要经过大量的旋转操作
因此 如果是需要一种查询高效的数据结构 AVL树是十分合适的
但是 如果它经常要被修改 AVL树的性能就可能不太匹配了
转载：https://blog.csdn.net/meihaoshy/article/details/128597344