您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

数据结构之AVL树(平衡二叉树)的理解

一.右旋和左旋

1.右旋(有右孩子则抛弃右孩子)

<1>平平无奇的右旋

 

上图就是一个平平无奇的右旋,简单来说就是:

  • 断开D和B的联系
  • 将B的右子树指向D,即D作为B的右子树(因为D比B大

  • 用B代替原先D的位置

<2>鸠占鹊巢的右旋(B本身有右子树)

若B本身有右子树,如:

此时B本身是有右子树的,对以D为结点的此最小平衡树进行右旋:

  • 将D的左子树指向B的右子树(B和D断开,把B的右子树作为D的左子树
  • 将B的右子树指向D(B和C断开,把D作为B的右子树
  • 用B代替原先D的位置

<3>通用右旋操作

<1>和<2>右旋合并到一种情况:

  • Step1:将D的左子树指向B的右子树(B的右子树成为D的左子树

      ①对于平平无奇的右旋,B的右子树为NULL,则D的左子树指向NULL

      ②对于鸠占鹊巢的右旋,B的右子树为C,则D的左子树指向C

  • Step2:将B的右子树指向D(D成为B的右子树

      ①对于平平无奇的右旋,B的右子树指向D

      ②对于鸠占鹊巢的右旋,B的右子树指向D

  • Step3:将B顶替原先D的位置(B成为新的中心

两者完全可以归并到一种情况,因此代码为:

//AVL树通用右旋操作
void R_Rotate(BiTree *P)
{
	BiTree L;
	L = (*P)->lchild;			    //定义L为P的左结点
	(*P)->lchild = L->rchild;		    //Step1:*P的左子树指向L的右子树(将L的右子树挂为*P的左子树)
	L->rchild = (*P);		            //Step2:L的右子树指向*P(将P挂为L的右子树)
	*P = L;					    //Step3:代替原有*P的位置
}

2.左旋(有左孩子则抛弃左孩子)

<1>平平无奇的左旋

 

上图就是一个平平无奇的左旋,简单来说就是:

  • 断开B和D的联系
  • 将D的左子树指向B,即B作为D的左子树(因为B比D小

  • 用D代替原先B的位置

<2>鸠占鹊巢的左旋(D本身有左子树)

若D本身有左子树,如:

此时D本身是有左子树的,对以B为结点的此最小平衡树进行右旋:

  • 将B的右子树指向D的左子树(B和D断开,把D的左子树作为B的右子树
  • 将D的左子树指向B(D和C断开,把B作为D的左子树
  • 用D代替原先B的位置

<3>通用左旋操作

<1>和<2>左旋合并到一种情况:

  • Step1:将B的右子树指向D的左子树(D的左子树成为B的右子树

      ①对于平平无奇的左旋,D的左子树为NULL,则B的右子树指向NULL

      ②对于鸠占鹊巢的左旋,D的左子树为C,则B的右子树指向C

  • Step2:将D的左子树指向B(B成为D的左子树

      ①对于平平无奇的左旋,D的左子树指向B

      ②对于鸠占鹊巢的左旋,D的左子树指向B

  • Step3:将D顶替原先B的位置(D成为新的中心

两者完全可以归并到一种情况,因此代码为:

//AVL树通用左旋操作
void L_Rotate(BiTree *P)
{
	BiTree R;
	R = (*P)->rchild;				//定义R为P的右结点
	(*P)->rchild = R->lchild;		        //Step1:*P的右子树指向R的左子树(将R的左子树挂为P的右子树)
	R->lchild = (*P);				//Step2:R的左子树指向*P(将P挂为R的左子树)
	(*P) = L;					//Step3:代替原有*P的位置
}

二.AVL有且只有的四种情况(LL,LR,RL,RR)

1.LL(Left-Left):单右旋

LL即Left-Left,这时候要进行:单右旋

LL型顾名思义,即插入A结点的L结点的L结点下(可以是LL的左或右都行,下图New为LL下的左子树)引起的不平衡,这种情况,要进行单右旋操作

此时的单右旋操作因为B本身有右结点,因此属于在一中介绍的右旋之鸠占鹊巢右旋

 

 拓展:

问题Q

LL类型本质上是在中心结点(A)Left--Left后的结点(上图结点7)后插入一个New结点,导致二叉树失衡

解决A

只需要对以结点(A)为中心的二叉树进行一次(单次)右旋操作,即可恢复平衡性

FAQ:

那么,上图中是在结点7之后的左结点插入了New,构成了LL-L,导致了二叉树的失衡,

实际上,在结点7之后的右结点插入New,构成LL-R,也会也会导致二叉树的失衡。

但是,我们都将其归结到LL型,因为这两种类型都是其子类型,且这两种类型都可以通过对:以结点(A)为中心的二叉树进行一次(单次)右旋操作恢复平衡性。

Summary总结:只要是LL型,那么对中心结点二叉树进行一次单右旋操作就可恢复平衡性


2.RR(Right-Right):单左旋

RR即Right-Right,这时候要进行:单左旋

RR型顾名思义,即插入A结点的R结点的R结点下(可以是RR的左或右都行,下图New为RR下的右子树)引起的不平衡,这种情况,要进行单左旋操作

此时的单左旋操作因为B本身有左结点,因此属于在一中介绍的左旋之鸠占鹊巢左旋

 

 拓展:

问题Q

RR类型本质上是在中心结点(A)Right-Right后的结点(上图结点7)后插入一个New结点,导致二叉树失衡

解决A

只需要对以结点(A)为中心的二叉树进行一次(单次)左旋操作,即可恢复平衡性

FAQ:

那么,上图中是在结点7之后的右结点插入了New,构成了RR-R下图),导致了二叉树的失衡

实际上,在结点7之后的左结点插入New,构成RR-L(下图),也会也会导致二叉树的失衡。

但是,我们都将其归结到RR型,因为这两种类型都是其子类型,且这两种类型都可以通过对:以结点(A)为中心的二叉树进行一次(单次)左旋操作恢复平衡性。

Summary总结:只要是RR型,那么对中心结点二叉树进行一次单左旋操作就可恢复平衡性


3.LR(Left-Right):双旋(先L后R)

LR即Left-Right型,这时候要进行:双旋(先对A的左子树进行L旋转,后对A为中心的全部R旋转)

LR型顾名思义,即插入A结点的L结点的R结点下(可以是LR下的L结点或R结点,也可以在LR下接着拓展L/R等,上图New为LR下的左子树)引起的不平衡,这种情况,要进行双旋操作

第一旋:对以A的左子树为根节点的树(即L后面结点,B-9-New)进行左旋

第二旋:再对以A为根节点的树(即全部结点)进行右旋

以上图为例,详细展开来说即为:

 

 

第一旋:对A的左子树(L结点后面的树B)进行左旋,因为结点9本身有左结点,因此这属于鸠占鹊巢的左旋;

旋转后就从L-R型变为了L-L型

第二旋:第一旋后的结果为L-L型,因此以A为根节点,进行单右旋,旋转后二叉树平衡

拓展:

问题Q

LR类型本质上是在中心结点(A)Left-Right后的结点后插入一个New结点,导致二叉树失衡

解决A

只需要对以结点A的左子树为根节点的二叉树进行一次左旋操作,再对A为根节点的二叉树进行一次右旋操作,即可恢复平衡性

FAQ:

那么,上图中是在结点9之后的左结点插入了New,构成了LR-L下图),导致了二叉树的失衡

实际上,在结点9之后的右结点插入New,构成LR-R(下图),也会也会导致二叉树的失衡。

其实可以更复杂一点,甚至可以衍生出:

LR-LL类(LR-LL,LR-LLL,LR-LLLL.....)

LR-LR类(LR-LR,LR-LRR,LR-LRRR...)

LR-RR类(LR-RR.LR-RRR,LR-RRRR...)

LR-RL类(LR-RL.LR-RLL,LR-RLLL...)

等等等等各种类型

但是我们都将其归结到LR型,因为都是其子类型,要明白:

  1. 只要是LR型,不论怎么衍生,其本质是不变的;

  2. 只要是LR型,就一定可以通过:Step1对中心节点左子树进行左旋,Step2对中心结点整体进行右旋恢复平衡;

Summary总结:只要是LR型,那么对中心结点左子树的二叉树进行一次左旋,再对中心结点二叉树进行一次右旋操作就可恢复平衡性


4.RL(Right-Left):双旋(先R后L)

RL即Right-Left型,这时候要进行:双旋(先对A的右子树进行R旋转,后对A为中心的二叉树进行L旋转)

RL型顾名思义,即插入A结点的R结点的L结点下(可以是RL下的L结点或R结点,也可以在RL下接着拓展L/R等,上图New为RL下的左子树)引起的不平衡,这种情况,要进行双旋操作

第一旋:对以A的右子树为根节点的树(即R后面结点,B-13-10-New)进行右旋

第二旋:再对以A为根节点的树(即全部结点)进行左旋

以上图为例,详细展开来说即为:

 

 

第一旋:对A的右子树(R结点后面的树B)进行单右旋,因为结点10本身无右结点,因此这属于平平无奇的右旋;

旋转后就从R-L型变为了R-R型

第二旋:第一旋后的结果为R-R型,因此以A为根节点,进行单左旋,旋转后二叉树平衡

拓展:

问题Q

RL类型本质上是在中心结点(A)Right-Left后的结点后插入一个New结点,导致二叉树失衡

解决A

只需要对以结点A的右子树为根节点的二叉树进行一次右旋操作,再对A为根节点的二叉树进行一次左旋操作,即可恢复平衡性

FAQ:

其实可以更复杂一点,甚至可以衍生出:

RL-LL类

RL-LR类

RL-RR类

RL-RL类

等等等等各种类型

但是我们都将其归结到RL型,因为都是其子类型,要明白:

  1. 只要是RL型,不论怎么衍生,其本质是不变的;

  2. 只要是RL型,就一定可以通过:Step1对中心节点右子树进行右旋,Step2对中心结点整体进行左旋恢复平衡;

Summary总结:只要是RL型,那么对中心结点右子树的二叉树进行一次右旋,再对中心结点二叉树进行一次左旋操作就可恢复平衡性

 

 

 

 

 

 

 

 

 

 

 

 

 

 


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进