0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看技术视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

二叉排序树AVL如何实现动态平衡

算法与数据结构 来源:bigsai 作者:bigsai 2021-10-28 17:02 次阅读

什么是AVL树

大家好,我是bigsai,好久不见,甚是想念,今天给大家讲讲AVL树。

对于树这种数据结构,想必大家也已经不再陌生,我们简单回顾一下。

在树的种类中,通常分成二叉树和多叉树,我们熟悉的二叉树种类有二叉搜索(排序、查找)树、二叉平衡树、伸展树、红黑树等等。而熟悉的多叉树像B树、字典树都是经典多叉树。

普通的二叉树,我们研究其遍历方式,因为其没啥规则约束查找和插入都很随意所以很少有研究价值。

但是二叉树结构上很有特点:左孩子和右孩子,两个不同方向的孩子对应二进制的01,判断的对错,比较的大小,所以根据这个结构所有树左侧节点比父节点小,右侧节点比父节点大,这时候就诞生了二叉搜索(排序)树。二叉搜索(排序)树的一大特点就是查找效率提高了,因为查找一个元素位置或者查看元素是否存在通过每遇到一个节点直接进行比较就可以一步步逼近结果的位置。

但二叉搜索(排序树)有个很大的问题就是当插入节点很有序,很可能成为一棵斜树或者深度很高,那么这样的一个查找效率还是趋近于线性O(n)级别,所以这种情况二叉搜索(排序)树的效率是比较低的。

所以,人们有个期望:对一棵树来说插入节点,小的还在左面,大的还在右面方便查找,但是能不能不要出现那么斜的情况?

这不,平衡二叉搜索(AVL)树就是这么干的,AVL在插入的时候每次都会旋转自平衡,让整个树一直处于平衡状态,让整个树的查询更加稳定(logN)。我们首先来看一下什么是AVL树:

  • AVL树是带有平衡条件的二叉搜索树,这个平衡条件必须要容易保持,而且要保证它的深度是O(logN)。

  • AVL的左右子树的高度差(平衡因子)不大于1,并且它的每个子树也都是平衡二叉树。

  • 对于平衡二叉树的最小个数,n0=0;n1=1;nk=n(k-1)+n(k-2)+1;(求法可以类比斐波那契)

难点:AVL是一颗二叉排序树,用什么样的规则或者规律让它能够在复杂度不太高的情况下实现动态平衡呢?

不平衡情况

如果从简单情况模型看,其实四种不平衡情况很简单,分别是RR,LL,RL,LR四种不平衡情况。

然后将其平衡的结果也很容易(不考虑其附带节点只看结果),将中间大小数值移动最上方,其他相对位置不变即可:

当然,这个仅仅是针对三个节点情况太过于理想化了,很多时候让你找不平衡的点,或者我们在解决不平衡的时候,我们需要的就是找到第一个不平衡(从底往上)的点将其平衡即可,下面列举两个不平衡的例子:

上述四种不平衡条件情况,可能出现在底部,也可能出现在头,也可能出现在某个中间节点导致不平衡,而我们只需要研究其首次不平衡点,解决之后整棵树即继续平衡,在具体的处理上我们使用递归的方式解决问题。

四种不平衡情况处理

针对四种不平衡的情况,这里对每种情况进行详细的讲解。

RR平衡旋转(左单旋转)

这里的RR指的是节点模型的样子,其含义是需要左单旋转(记忆时候需要注意一下RR不是右旋转)!

出现这种情况的原因是节点的右侧的右侧较深这时候不平衡节点需要左旋,再细看过程。

  • 在左旋的过程中,root(oldroot)节点下沉,中间节点(newroot)上浮.而其中中间节点(newroot)的右侧依然不变。

  • 它上浮左侧所以需要指向根节点(oldroot)(毕竟一棵树)。但是这样newroot原来左侧节点H空缺。而我们需要仍然让整个树完整并且满足二叉排序树的规则

  • 而刚好本来oldroot右侧指向newroot现在结构改变oldroot右侧空缺,刚好这个位置满足在oldroot的右侧,在newroot的左侧,所以我们将H插入在这个位置。

  • 其中H可能为NULL,不过不影响操作!

其更详细流程为:

而左旋的代码可以表示为:

privatenodegetRRbanlance(nodeoldroot){//右右深,需要左旋
//TODOAuto-generatedmethodstub
nodenewroot=oldroot.right;
oldroot.right=newroot.left;
newroot.left=oldroot;
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原来的root的高度需要从新计算
returnnewroot;
}

LL平衡旋转(右单旋转)

而右旋和左旋相反,但是思路相同,根据上述进行替换即可!


代码:

privatenodegetLLbanlance(nodeoldroot){//LL小,需要右旋转
//TODOAuto-generatedmethodstub
nodenewroot=oldroot.left;
oldroot.left=newroot.right;
newroot.right=oldroot;
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原来的root的高度需要从新金酸
returnnewroot;
}

RL平衡旋转(先右后左双旋转)

这个RL你可能有点懵圈,为啥RR叫左旋,LL叫右旋,这个RL怎么就叫先右后左旋转了?

别急别急,这个之所以先后后左,是因为具体需要中间节点右旋一次,然后上面节点左旋一次才能平衡,具体可以下面慢慢看。

首先产生这种不平衡的条件原因是:ROOT节点右侧左侧节点的深度高些,使得与左侧的差大于1,这个与我们前面看到的左旋右旋不同因为旋转一次无法达到平衡!

对于右左结构,中间(R)的最大,两侧(ROOT,R.L)的最小,但是下面(R.L)的比上面(ROOT)大(R.LROOT右侧)所以如果平衡的话,那么R.L应该在中间,而R应该在右侧,原来的ROOT在左侧。

这个过程节点的变化浮动比较大,需要妥善处理各个子节点的移动使其满足二叉排序树的性质!

这种双旋转具体实现其实也不难,不要被外表唬住,这里面双旋转我提供两种解答方法。


思路(标准答案)1:两次旋转RR,LL

这个处理起来非常容易,因为前面已经解决RR(左旋),LL(右旋)的问题,所以这里面在上面基础上可以直接解决,首先对R节点进行一次LL右旋,旋转一次之后R在最右侧,这就转化成RR不平衡旋转的问题了,所以这个时候以ROOT开始一次RR左旋即可完成平衡,具体流程可以参考下面这张图。

思路(个人方法)2:直接分析

根据初始和结果的状态,然后分析各个节点变化顺序=,手动操作这些节点即可。其实不管你怎么操作,只要能满足最后结构一致就行啦!

首先根据ROOT,R,R.L三个节点变化,R.L肯定要在最顶层,左右分别指向ROOT和R,那么这其中R.leftROOT.right发生变化(原来分别是R.L和R)暂时为空。而刚好根据左右大小关系可以补上R.L原来的孩子节点AB

代码为:(注释部分为方案1)

privatenodegetRLbanlance(nodeoldroot){//右左深
//nodenewroot=oldroot.right.left;
//oldroot.right.left=newroot.right;
//newroot.right=oldroot.right;
//oldroot.right=newroot.left;
//newroot.left=oldroot;
//oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
//newroot.right.height=Math.max(getHeight(newroot.right.left),getHeight(newroot.right.right))+1;
//newroot.height=Math.max(getHeight(oldroot.left),getHeight(newroot.right))+1;//原来的root的高度需要从新金酸
oldroot.right=getLLbanlance(oldroot.right);
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
returngetRRbanlance(oldroot);

}

LR平衡旋转(先左后右双旋转)

这个情况和RL情况相似,采取相同操作即可。

根据上述RL修改即可

这部分代码为

privatenodegetLRbanlance(nodeoldroot){
oldroot.left=getRRbanlance(oldroot.left);
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
returngetLLbanlance(oldroot);

}

代码实现

首先对于节点多个height属性。用于计算高度(平衡因子)

插入是递归插入,递归是一个来回的过程,去的过程进行插入,回的过程进行高度更新,和检查是否平衡。推荐不要写全局递归计算高度,效率太低下,事实上高度变化只和插入和平衡有关,仔细考虑即不会有疏漏!

代码写的比较早,如有命名不规范的情况,还请勿喷,如果有疏漏还请指出!

importjava.util.ArrayDeque;
importjava.util.Queue;

publicclassAVLTree{

classnode
{
intvalue;
nodeleft;
noderight;
intheight;
publicnode(){

}
publicnode(intvalue)
{
this.value=value;
this.height=0;
}
publicnode(intvalue,nodeleft,noderight)
{
this.value=value;
this.left=left;this.right=right;
this.height=0;
}
}
noderoot;//根

publicAVLTree(){
this.root=null;
}

publicbooleanisContains(intx)//是否存在
{
nodecurrent=root;
if(root==null){
returnfalse;
}
while(current.value!=x&¤t!=null){
if(x< current.value) {
                current = current.left;
            }
            if(x>current.value){
current=current.right;
}
if(current==null){
returnfalse;
}//在里面判断如果超直接返回
}
//如果在这个位置判断是否为空会导致current.value不存在报错
if(current.value==x){
returntrue;
}
returnfalse;
}

publicintgetHeight(nodet)
{
if(t==null){return-1;}//
returnt.height;
//return1+Math.max(getHeight(t.left),getHeight(t.right));这种效率太低
}
publicvoidcengxu(nodet){//层序遍历
Queueq1=newArrayDeque();
if(t==null)
return;
if(t!=null){
q1.add(t);
}
while(!q1.isEmpty()){
nodet1=q1.poll();
if(t1.left!=null)
q1.add(t1.left);
if(t1.right!=null)
q1.add(t1.right);
System.out.print(t1.value+"");
}
System.out.println();
}
publicvoidzhongxu(nodet)//中序遍历中序遍历:左子树--->根结点--->右子树
{//为了测试改成中后都行
if(t!=null)
{
zhongxu(t.left);
System.out.print(t.value+"");//访问完左节点访问当前节点
zhongxu(t.right);
//System.out.print(t.value+"");//访问完左节点访问当前节点
}
}
publicvoidqianxu(nodet)//前序递归前序遍历:根结点--->左子树--->右子树
{
if(t!=null){
System.out.print(t.value+"");//当前节点
qianxu(t.left);
qianxu(t.right);}
}
publicvoidinsert(intvalue){
root=insert(value,root);
}
publicnodeinsert(intx,nodet)//插入t是root的引用
{
nodea1=newnode(x);
//if(root==null){root=a1;returnroot;}
if(t==null){returna1;}
//插入操作。递归实现
elseif(t!=null)
{
if(xelse
{t.right=insert(x,t.right);}
}
/*
*更新当前节点的高度,因为整个插入只有被插入的一方有影响,
*所以递归会更新好最底层的,上层可直接调用
*/
t.height=Math.max(getHeight(t.left),getHeight(t.right))+1;//不要写成递归,递归效率低
returnbanlance(t);//因为java对象传参机制,需要克隆,不可直接t=xx否则变换
}

privatenodebanlance(nodet){
//TODOAuto-generatedmethodstub
//if(t==null)returnnull;
intlefthigh=getHeight(t.left);
intrighthigh=getHeight(t.right);
if(Math.abs(lefthigh-righthigh)<=1)//不需要平衡滴
{returnt;}
elseif(lefthigh//右侧大
{
if(getHeight(t.right.left)//RR需要左旋
{
returngetRRbanlance(t);
}
else{
returngetRLbanlance(t);
}
}
else{
if(getHeight(t.left.left)>getHeight(t.left.right))//ll左左
{
returngetLLbanlance(t);
}
else{
returngetLRbanlance(t);
}
}
}
/*
*oldroot(平衡因子为2,不平衡)==>newroot
*//
*Bnewroot(平衡因子为1)oldrootD
*//
*CDBCE
*
*E
*/

privatenodegetRRbanlance(nodeoldroot){//右右深,需要左旋
//TODOAuto-generatedmethodstub
nodenewroot=oldroot.right;
oldroot.right=newroot.left;
newroot.left=oldroot;
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原来的root的高度需要从新计算
returnnewroot;
}
/*
*右旋同理
*/
privatenodegetLLbanlance(nodeoldroot){//LL小,需要右旋转
//TODOAuto-generatedmethodstub
nodenewroot=oldroot.left;
oldroot.left=newroot.right;
newroot.right=oldroot;
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原来的root的高度需要从新金酸
returnnewroot;
}

privatenodegetLRbanlance(nodeoldroot){
oldroot.left=getRRbanlance(oldroot.left);
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
returngetLLbanlance(oldroot);

}

/*(不平衡出现在右左节点)
*oldroot==>newroot
*//
*ABoldrootB
*///
*newrootDAEFD
*/
*EF
*/

privatenodegetRLbanlance(nodeoldroot){//右左深
//nodenewroot=oldroot.right.left;
//oldroot.right.left=newroot.right;
//newroot.right=oldroot.right;
//oldroot.right=newroot.left;
//newroot.left=oldroot;
//oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
//newroot.right.height=Math.max(getHeight(newroot.right.left),getHeight(newroot.right.right))+1;
//newroot.height=Math.max(getHeight(oldroot.left),getHeight(newroot.right))+1;//原来的root的高度需要从新金酸
oldroot.right=getLLbanlance(oldroot.right);
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
returngetRRbanlance(oldroot);

}
}

测试情况:

af7e133c-37a8-11ec-82a8-dac502259ad0.png

AVL的理解需要时间,当然笔者的AVL自己写的可能有些疏漏,如果有问题还请各位一起探讨!

当然,除了插入,AVL还有删除等其他操作,(原理相似。删除后平衡)有兴趣可以一起研究。

责任编辑:haq
声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • AVL
    AVL
    +关注

    关注

    0

    文章

    14

    浏览量

    10040
  • 二叉树
    +关注

    关注

    0

    文章

    74

    浏览量

    12324

原文标题:这个树,怎么一下就平衡了?

文章出处:【微信号:TheAlgorithm,微信公众号:算法与数据结构】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    时间复杂度为 O(n^2) 的排序算法

    , O(n2) 的排序算法可能会比 O(nlogn) 的排序算法执行效率高。不过随着数据规模增大, O(nlogn) 的排序算法是不选择。本篇我们主要对 O(n2) 的
    的头像 发表于 10-19 16:31 1150次阅读
    时间复杂度为 O(n^2) 的<b class='flag-5'>排序</b>算法

    平衡阀正确安装使用方法介绍

    平衡阀是在水力工况下,起到动态、静态平衡调节的阀门。平衡阀可分为三种类型:静态平衡阀、动态平衡
    的头像 发表于 10-10 16:37 1034次阅读
    <b class='flag-5'>平衡</b>阀正确安装使用方法介绍

    TPS54120排序和跟踪

    电子发烧友网站提供《TPS54120排序和跟踪.pdf》资料免费下载
    发表于 10-10 10:54 0次下载
    TPS54120<b class='flag-5'>排序</b>和跟踪

    什么是默克尔(Merkle Tree)?如何计算默克尔根?

    01 默克尔的概念 默克尔(Merkle Tree)是一种特殊的二叉树,它的每个节点都存储了一个数据块的哈希值。哈希值是一种可以将任意长度的数据转换为固定长度的字符串的算法,它具有唯一性和不可
    的头像 发表于 09-30 18:22 861次阅读
    什么是默克尔<b class='flag-5'>树</b>(Merkle Tree)?如何计算默克尔根?

    指电极上覆盖敏感材料的阻值计算

    覆盖的敏感材料厚度超出指厚度时计算电阻,是否可以视作指电极指间电阻多个周期串联后与超出指厚度部分敏感材料电阻并联
    发表于 07-05 14:48

    指MOSFET器件静电防护鲁棒性提升技巧

    栅极接地NMOS是一种广泛应用的片上ESD器件结构,为达到特定ESD防护等级,一般会采用多指版图形式来减小器件占用的芯片面积。但是,多指栅极接地NMOS在ESD应力作用下,各个指难于做到均匀
    的头像 发表于 06-22 00:50 518次阅读
    多<b class='flag-5'>叉</b>指MOSFET器件静电防护鲁棒性提升技巧

    手把手教你排序算法怎么写

    今天以直接插入排序算法,给大家分享一下排序算法的实现思路,主要包含以下部分内容:插入排序介绍插入排序算法
    的头像 发表于 06-04 08:03 687次阅读
    手把手教你<b class='flag-5'>排序</b>算法怎么写

    极管的静态特性和动态特性详解

    极管,作为电子威廉希尔官方网站 中的基础元件,其性能的好坏直接影响到整个威廉希尔官方网站 的稳定性和效率。极管的特性可以大致分为静态特性和动态特性两大类。静态特性主要描述了极管在直流或低频交流信号作用下的性
    的头像 发表于 05-28 14:26 2239次阅读

    用FPGA实现双调排序的方法(2)

    典型的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔
    的头像 发表于 03-21 10:28 638次阅读
    用FPGA<b class='flag-5'>实现</b>双调<b class='flag-5'>排序</b>的方法(2)

    FPGA实现双调排序算法的探索与实践

    双调排序(BitonicSort)是数据独立(Data-independent)的排序算法,即比较顺序与数据无关,特别适合并行执行。在了解双调排序算法之前,我们先来看看什么是双调序列。
    发表于 03-14 09:50 645次阅读
    FPGA<b class='flag-5'>实现</b>双调<b class='flag-5'>排序</b>算法的探索与实践

    想听听48和大对数光缆的排序

    48芯光缆和大对数光缆都是光缆中的一种,它们的区别在于芯数不同。48芯光缆指的是光缆中包含48根光纤,而大对数光缆则是指光缆中芯数超过了48芯。 在实际的光缆应用中,不同芯数的光缆需要进行不同的排序
    的头像 发表于 03-12 10:44 614次阅读

    什么是动态线程池?动态线程池的简单实现思路

    因此,动态可监控线程池一种针对以上痛点开发的线程池管理工具。主要可实现功能有:提供对 Spring 应用内线程池实例的全局管控、应用运行时动态变更线程池参数以及线程池数据采集和监控阈值报警。
    的头像 发表于 02-28 10:42 643次阅读

    C语言实现经典排序算法概览

    冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。
    的头像 发表于 02-25 12:27 448次阅读
    C语言<b class='flag-5'>实现</b>经典<b class='flag-5'>排序</b>算法概览

    基于分类构建代码动态测试用例(VCT)#代码动态测试

    代码分类
    北汇信息POLELINK
    发布于 :2024年01月27日 15:29:34

    什么是白平衡?白平衡的作用

    平衡是指调整相机或摄像机的色温设置,以使图像中的白色与实际场景中的白色看起来一致。 在摄影和摄像中,白平衡的作用非常重要。由于不同光源的色温不同,相机在不同光源下拍摄的照片或视频会呈现出不同的偏色
    的头像 发表于 01-22 15:31 1895次阅读