目录
AVL树是一种自平衡的平衡二叉查找树,它是一种高效的数据结构,可以在插入和删除节点时保持树的平衡,从而保证树的操作时间复杂度能够达到O(log n)。
所谓平衡就是保证每个节点的左右子树的高度差不能超过1。例如
对AVL树进行插入或删除操作时,可能会导致某些节点的高度差超过1,即不再平衡。这时就需要进行旋转操作来恢复AVL树的平衡性。所以,AVL树的核心内容就是旋转。
一般来讲,我们将旋转类型分为两大类。左-左、右-右类型的为单旋转,左-右、右-左类型的为双旋转。下面是这四种旋转的操作方式。
AVL树的单旋转指的是在树的某个节点上进行的一种旋转操作,通过左旋或右旋使该节点成为旋转后的子树的根节点,并使树保持平衡状态。在单旋转过程中,节点的左右子树高度变化不超过1,旋转操作其实是把子树的位置进行调整,使得整棵树的平衡因子尽可能地符合平衡树的要求。
具体来说,如果在某个节点的左子树中插入了一个新节点导致该节点的左子树高度比右子树高度多2,那么就需要在该节点进行一次右旋转操作。右旋转将该节点的左子节点变为子树的根节点,该节点的原父节点成为子树的新根节点的右子节点,子树的其他节点位置不变。
同理,如果在某个节点的右子树中插入了一个新节点导致该节点的右子树高度比左子树高度多2,那么就需要在该节点进行一次左旋转操作。左旋转将该节点的右子节点变为子树的根节点,该节点的原父节点成为子树的新根节点的左子节点,子树的其他节点位置不变。
具体的图解如下:
单旋转的过程可以概况为如下的三个步骤(以下图为模型,以单左旋为例):
1、让k2原本指向k1的指针现在指向k1内侧的节点
2、让k1原本指向内侧的指针现在指向k2
3、让原来指向k2的指针现在改为指向k1,并更新各节点的高度
AVL树的双旋转是指在某个节点的子树中进行两次旋转操作以保持平衡的一种树旋转方式。双旋转包含两种情况:左旋-右旋和右旋-左旋。
具体来说,假设在AVL树的某个节点的左子树中插入了一个新节点,导致该节点的左子树高度比右子树高度多2,但是进行一次右旋转不能转换成平衡状态,此时需要进行左旋-右旋操作。该操作可以分解为两步:
对该节点的左子节点进行一次左旋转。
对该节点进行一次右旋转。
左旋转操作会使得该节点的左子节点变为子树的根节点,同时该节点成为新根节点的右子节点,然后对该节点进行右旋转时,子树的根节点发生了变化,新的根节点是之前的左子节点,原本的根节点成为新节点的右子节点,最后使得整棵树重新平衡。
同样的,假如在AVL树的某个节点的右子树中插入了一个新节点,导致该结点的右子树高度比左子树高度多2,但进行一次左旋转不能转换成平衡状态,此时需要进行右旋-左旋操作。该操作可以分成两步:
对该节点的右子节点进行一次右旋转。
对该节点进行一次左旋转。
右旋转操作会使得该节点的右子节点变为子树的根节点,同时该节点成为新根节点的左子节点,然后对该节点进行左旋转时,子树的根节点发生了变化,新的根节点是之前的右子节点,原本的根节点成为新节点的左子节点,最后使得整棵树重新平衡。
具体图解如下:
双旋转其实就是两次单旋转,先将内侧的节点通过单旋转“移出来”到外侧。然后再用一次单旋转,最终成为我们想要的平衡状态。
AVL树动画演示
也可以自己尝试:
AVL Tree Visualzation (usfca.edu)https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
AVL树一个最直接的方式就是每个节点的信息中增加了一个高度信息(Height),每个节点在插入后向上回溯到根,进行高度信息的调整更新,并判断是否要进行旋转。这种实现方式比较直观好想,每次判断是否需要进行旋转的时候就直接判断高度差即可。
如下是一种实现方式(C语言实现,以递归的方式进行插入和回溯,每个节点只有左右孩子两个指针,维护平衡条件的信息是节点的高度),仅供参考。
/* 忽略了相关头文件 */
typedef char ElementType; //暂定节点内容只有单个字符
typedef struct AvlTreeNode
{
ElementType Data;
int Height;
struct AvlTreeNode* Left;
struct AvlTreeNode* Right;
}AvlTree;
int Height(AvlTree* Node)
{
if (Node == NULL)
return -1;
return Node->Height;
}
AvlTree* SingleLeftRotate(AvlTree* k2) //单左旋,LL旋转(k2的由来详见数据结构与算法分析P94)
{
//旋转节点
AvlTree* k1 = k2->Left;
k2->Left = k1->Right;
k1->Right = k2;
//更新高度
k2->Height = max(Height(k2->Left), Height(k2->Right)) + 1;
k1->Height = max(Height(k1->Left), Height(k1->Right)) + 1;
//返回
return k1;
}
AvlTree* SingleRightRotate(AvlTree* k2) //单右旋,RR旋转(k2的由来详见数据结构与算法分析P94)
{
//旋转节点
AvlTree* k1 = k2->Right;
k2->Right = k1->Left;
k1->Left = k2;
//更新高度
k2->Height = max(Height(k2->Left), Height(k2->Right)) + 1;
k1->Height = max(Height(k1->Left), Height(k1->Right)) + 1;
//返回
return k1;
}
AvlTree* DoubleLRRotate(AvlTree* k3) //双左右旋,LR旋转(k3的由来详见数据结构与算法分析P95)
{
/*一次双旋转等于两次单旋转。
可以理解为先将需要旋转的移至同一方向(即左左、右右这种),然后再用单旋转的方式处理*/
k3->Left = SingleRightRotate(k3->Left);
return SingleLeftRotate(k3);
}
AvlTree* DoubleRLRotate(AvlTree* k3) //双右左旋,RL旋转(k3的由来详见数据结构与算法分析P95)
{
/*一次双旋转等于两次单旋转。
可以理解为先将需要旋转的移至同一方向(即左左、右右这种),然后再用单旋转的方式处理*/
k3->Right = SingleLeftRotate(k3->Left);
return SingleRightRotate(k3);
}
AvlTree* InsertElement(AvlTree** root, ElementType data)
{
//走到空节点(即插入位置),执行插入操作
if ((*root) == NULL)
{
//开辟空间并赋值
*root = (AvlTree*)calloc(1, sizeof(AvlTree));
//成功开辟空间
if ((*root) != NULL)
(*root)->Data = data;
//开辟空间失败
else
puts("heap area is full!");
}
//根节点无内容(值为0),说明为空树,则直接将data插入到根节点
else if ((*root)->Data == 0)
{
(*root)->Data = data;
}
//data比节点内容小,在左侧插入
else if (data < (*root)->Data)
{
//向左走,并更新左子树内容
(*root)->Left = InsertElement(&(*root)->Left, data);
//判断是否需要旋转
if (Height((*root)->Left) - Height((*root)->Right) == 2)
{
//如果data小于左子树的data,说明是data插入到左子树的左节点,符合单旋转的情况(3个节点都在左侧)
if (data < (*root)->Left->Data)
*root = SingleLeftRotate(*root); //左侧单旋转,并更新节点内容
//如果data不小于左子树的data,说明是插入到左子树的右节点,是LR型的双旋转情况
else
*root = DoubleLRRotate(*root); //左右双旋转,并更新节点内容
}
}
//data比节点内容大,在右侧插入
else if (data > (*root)->Data)
{
//向右走,并更新左子树内容
(*root)->Right = InsertElement(&(*root)->Right, data);
//判断是否旋转
if (Height((*root)->Right) - Height((*root)->Left) == 2)
{
//如果data大于右子树的data,说明是data插入到右子树的右节点,符合单旋转的情况(3个节点都在右侧)
if (data > (*root)->Right->Data)
*root = SingleRightRotate(*root); //右侧单旋转,并更新节点内容
//如果data不大于右子树的data,说明是插入到右子树的左节点,是RL型的双旋转情况
else
*root = DoubleRLRotate(*root);
}
}
//data与节点内容值相同
else { /*暂定如果插入的元素内容相同,则什么都不做*/ }
//最后更新节点高度
(*root)->Height = max(Height((*root)->Left), Height((*root)->Right)) + 1;
//返回
return *root;
}
相比通过高度的直观,平衡因子就有些复杂了。这里的平衡因子指的是右子树的高度减左子树的高度,每个节点都有一个平衡因子信息,初始化为0。每次插入节点后也是向上回溯,进行平衡因子的更新调整与判断是否需要旋转,不过这种方式不一定要走到根,如果更新后的平衡因子信息为0,就说明不用再往上调了。
如下是一种实现方式(C++实现,通过迭代循环的方式进行插入和回溯,为了能够不通过递归进行回溯操作,除了基准的左右儿子指针,这种实现方式为每一个节点还为维护了一个双亲指针,维护平衡条件的信息是平衡因子),仅供参考。
/* 忽略了相关头文件 */
// 节点类型
template<typename T>
struct AVLNode
{
AVLNode(const T& val)
: _val(val)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{}
T _val; // 数据内容
int _bf; // 平衡因子:右高度减左高度
AVLNode<T>* _left;
AVLNode<T>* _right;
AVLNode<T>* _parent;
};
// 树的类型
template<typename T>
class AVLtree
{
AVLNode<T>* _root = nullptr; // 根节点
public:
bool insert(const T& val)
{
/* 初始情况,树为空 */
if (_root == nullptr)
{
_root = new AVLNode<T>(val);
return true;
}
/* 一般情况,插入数据 */
AVLNode<T>* pre = nullptr;
AVLNode<T>* cur = _root;
// 先找到对应位置
while (cur)
{
// 要插入数据已存在 - 插入失败
if (val == cur->_val)
return false;
// 要插入数据不存在,继续寻找
pre = cur;
if (val > cur->_val)
cur = cur->_right;
else if (val < cur->_val)
cur = cur->_left;
}
// cur找到了插入位置,new一个新节点并插入
cur = new AVLNode<T>(val);
if (val > pre->_val)
pre->_right = cur;
else
pre->_left = cur;
cur->_parent = pre;
/* 向上回溯,随之更新平衡因子,并进行旋转调整 */
while (pre != nullptr)
{
// 根据cur的位置,更新父节点的平衡因子信息
if (cur == pre->_right)
pre->_bf++;
else
pre->_bf--;
// bf为0或者正负2的情况都退出,所以就合并处理了
// 因为2这里给限制死了,所以不会出现abs(bf)大于等于3的情况
if (abs(pre->_bf) != 1)
{
if (abs(pre->_bf) == 2)
rotatenode(pre, cur->_bf);
break;
}
// 没遇到特殊情况,继续向上回溯
cur = pre;
pre = cur->_parent;
}
return true;
}
private:
// 需要旋转节点的情况 - 旋转的4种情况
void rotatenode(AVLNode<T>* parent, int cur_bf)
{
if (parent->_bf == 2)
{
if (cur_bf == 1)
rotateRR(parent);
else if (cur_bf == -1)
rotateRL(parent);
}
else if (parent->_bf == -2)
{
if (cur_bf == 1)
rotateLR(parent);
else if (cur_bf == -1)
rotateLL(parent);
}
}
/* 旋转的4个函数 */
// 左左单旋(节点都在左侧的情况)
void rotateLL(AVLNode<T>* parent)
{
// 调整节点位置及父子关系
AVLNode<T>* cur = parent->_left;
AVLNode<T>* rchild = cur->_right;
parent->_left = rchild;
if (rchild != nullptr)
rchild->_parent = parent;
cur->_right = parent;
// 进行旋转
AVLNode<T>* super = parent->_parent;
cur->_parent = super;
parent->_parent = cur;
AVLNode<T>*& port = super == nullptr ? _root : (super->_left == parent ? super->_left : super->_right);
port = cur;
// 调节平衡因子
cur->_bf = 0;
parent->_bf = 0;
}
// 右右单旋(节点都在右侧的情况)
void rotateRR(AVLNode<T>* parent)
{
// 调整节点位置及父子关系
AVLNode<T>* cur = parent->_right;
AVLNode<T>* lchild = cur->_left;
parent->_right = lchild;
if (lchild != nullptr)
lchild->_parent = parent;
cur->_left = parent;
// 进行旋转
AVLNode<T>* super = parent->_parent;
cur->_parent = super;
parent->_parent = cur;
AVLNode<T>*& port = super == nullptr ? _root : (super->_left == parent ? super->_left : super->_right);
port = cur;
// 调节平衡因子
cur->_bf = 0;
parent->_bf = 0;
}
// 左右双旋
void rotateLR(AVLNode<T>* parent)
{
// 先把里面的节点旋出来,再按照单旋转处理
AVLNode<T>* cur = parent->_left;
AVLNode<T>* sub = cur->_right;
int bf = sub->_bf;
rotateRR(cur);
rotateLL(parent);
// 调整平衡因子
if (bf == 1)
cur->_bf = -1;
else if (bf == -1)
parent->_bf = 1;
}
// 右左双旋
void rotateRL(AVLNode<T>* parent)
{
// 先把里面的节点旋出来,再按照单旋转处理
AVLNode<T>* cur = parent->_right;
AVLNode<T>* sub = cur->_left;
int bf = sub->_bf;
rotateLL(cur);
rotateRR(parent);
// 调整平衡因子
if (bf == 1)
parent->_bf = -1;
else if (bf == -1)
cur->_bf = 1;
}
};
文章浏览阅读8.4k次,点赞4次,收藏17次。QR码生成原理(一)一、什么是QR码QR码属于矩阵式二维码中的一个种类,由DENSO(日本电装)公司开发,由JIS和ISO将其标准化。QR码的样子其实在很多场合已经能够被看到了,我这还是贴个图展示一下:这个图如果被正确解码,应该看到我的名字和邮箱。二、QR码的特点说到QR码的特点,一是高速读取(QR就是取自“Quick Response”的首字母),对读取速度的体验源自于我..._二维码qr编码算法是什么
文章浏览阅读4.9k次,点赞2次,收藏2次。初步解析小程序前端框架vant-ui源码本学期的系统分析课程要求我们做一个小项目,我们以微信小程序为框架进行了项目的前端搭建,在UI上以开源组件库vant-ui为基础进行了设计,其中用到了许多该开源库的设计,对于项目前端起到了很大的帮助。组件库的使用教程在 https://youzan.github.io/vant-weapp/#/intro ,介绍说明比较详细且简单,因此这里不再赘述,这里..._微信小程序vantpopup源码
文章浏览阅读3.2k次。树状数组+二分考虑一个简单的问题,维护一个数组,支持每次修改一个数的值,保证每时每刻每个数都为非负数。每次查询求前缀和kkk lower_bound 的值。对于修改,可以用树状数组、线段树等数据结构维护。二分查找可以在[l,r][l,r][l,r]的范围上二分答案,mid=⌊l+r2⌋mid = \lfloor \frac{l+r}{2} \rfloormid=⌊2l+r⌋,验证midmidmid的前缀和是否大于kkk,并调整midmidmid。时间复杂度O(log22n)O(log^2_2n)O_树状数组上二分
文章浏览阅读3.4k次,点赞8次,收藏47次。S;串的组成1length用length记录串的长度是为了减少后期的遍历串获取串长度的时间复杂度。如果不设置length的话,每一次获取字符串长度都需要一次循环,时间复杂度为O(n),如果设置了length的话,给串新增字符的过程中就记录当前串的长度,未来需要串的长度的时候直接获取length就可以了,时间复杂度降低为O(1)。2chch是串里的字符串。......_串的初始化
文章浏览阅读2.3k次。pom文件的依赖无版本号的可能原因_android studio dependencies里没有版本信息
文章浏览阅读2.8k次,点赞4次,收藏7次。在IoT物联网时代,我们经常会遇到从传感器采集数据的情况。这些传感器,可以上传物联网数据,比如温度,湿度。通常这些传感器带有自己的ID,但是它并不具有像地理位置等这样的信息。当物联网数据传到我们的数据平台时,我们希望对采集上来的数据进行数据的丰富,比如我们对物联网的数据加上它所在的位置等信息,这将对我们的数据分析非常有用。这些需要丰富的数据通常会存放于一个关系数据库的表格中,比如MySQL的数据库..._logstash jdbc_streaming
文章浏览阅读138次。程序代码和数据。对所有的进程来说,代码是从同一固定地址开始,紧接着的是和C 全局变量相对应的数据位置。堆。代码和数据区在进程一开始运行时就被指定了大小,与此不同,当调用像 malloc 和 free 这样的 C 标准库函数时,堆可以在运行时动态地扩展和收缩。共享库。大约在地址空间的中间部分是一块用来存放像 C 标准库和数学库这样的共享库的代码和数据的区域。栈。位于用户虚拟地址空间顶部的是用户栈,编译器用它来实现函数调用。和堆一样,用户栈在程序执行期间可以动态地扩展和收缩。特别地,每次我们调用..._matlab2010 虚拟内存
文章浏览阅读6.5k次。如果你百度了很多方法都没有解决的话,请用管理员权限打开cmd,然后再输入npm安装命令试一试。反正我解决了_npm run dev error: eexist: file already exists, mkdir 'c:\windows\system32\c
文章浏览阅读108次。物联网(Internet of Things,IoT)是指通过互联网连接各种设备和物品,使它们能够相互通信和交换数据的网络。在这个数字化时代,物联网已经成为了企业数字化转型的重要驱动力。通过物联网技术,企业可以实现对企业数据的实时监控、数据分析和智能化决策,从而提高企业的效率和效益,实现更高的商业价值。下面,我们将介绍一些成功的物联网应用案例,以帮助您更好地了解物联网的潜力。
文章浏览阅读1.7k次。本发明涉及一种基于包络提取的高精度无键相信号阶次跟踪方法及系统,属于故障诊断技术与信号处理分析技术领域。背景技术:传统的阶次齿轮箱故障信号特征提取针对的是恒定转速运转下的测试信号,但对于工程机械等现代大型复杂机械装备中,恶劣的工作环境导致其运行工况复杂,转速和负荷等工况参数的变化将导致其振动信号具有明显的非平稳性,因此其采集的振动信号不直接满足傅里叶变换的平稳性要求。针对此问题出现了阶次跟踪方法,..._matlab阶次跟踪
文章浏览阅读205次。什么是推导式:推导式是用来快速的生成数据1、推导式类型2、字典推导式推导式结合条件语句语法:dict = { key:value for i in xxx if 条件}推导式结合三元运算符语法:dict = { key:value if 条件 else key2:value2 for i in xxx}3、字典推导式原则4、注意事项5、集合推导式......_字典推导式 key自增怎么写
文章浏览阅读1.5k次,点赞6次,收藏18次。C语言经典编程之字符串:按特定顺序输出压缩,IP地址判断是否合法,字符串压缩、解压、排序,查找相同的字串,单词升序排列,统计单词个数,Objective-C和C++命名之争,字符串删除、插入、替换、抽取、交换、拼接、分割,统计字母在字符串中出现的次数等。_char ch : input