注册
登录

您现在的位置是:首页 > 学无止境

平衡二叉排序树|AVL树 左旋右旋到底是啥?

木木彡82 2022-09-06 16:42:34 0人围观
平衡二叉排序树|AVL树 左旋右旋到底是啥?

转载自:https://zhuanlan.zhihu.com/p/488480370

二叉树平衡遵循原则

平衡的原则公式:|左子树高度-右子树高度| < 2

也就是说,如果一棵二叉树中,只要有任何子树,它的左子树高度减去右子树高度(绝对值)只要大于或者等于2,那么这棵二叉树就不是平衡的。就需要进行旋转操作使之变成平衡。

非平衡二叉树的种类

非平衡二叉树主要分为四种:LL类、RR类、LR类、RL类。

下面画图分别说明其特点:(Lleft表示左子树高度,Lright表示右子树高度)

第1类—LL型:

特点:根节点的左孩子的左孩子引起的树不平衡。可能是左孩子的左孩子加进来。或者左孩子的左孩子又加了一个孩子进来,导致左子树的高度过高,违反了|Lleft-Lright|<2的原则。这种就是LL型。

第2类—RR型:

特点:根节点的右孩子的右孩子引起的树不平衡。可能是右孩子的右孩子加进来;或者右孩子的右孩子又加了一个孩子进来,导致右子树的高度过高,违反了|Lleft-Lright|<2的原则。这种就是RR型。

第3类—LR型:

特点:根节点的左孩子的右孩子引起的树不平衡。可能是左孩子的右孩子加进来;或者左孩子的右孩子又加了一个孩子进来,导致左子树的高度过高,违反了|Lleft-Lright|<2的原则。这种就是LR型。

第4类—RL型:

特点:根节点的右孩子的左孩子引起的树不平衡。可能是右孩子的左孩子加进来;或者右孩子的左孩子又加了一个孩子进来,导致右子树的高度过高,违反了|Lleft-Lright|<2的原则。这种就是RL型。

非平衡二叉树的旋转法

LL型:根节点右旋;

RR型:根节点左旋;

LR型:先左旋再右旋;(1、根节点不动,让左节点去解决;2、小弟左旋到其右孩子的左边,这时树演化成了LL型;3、LL型则将根节点右旋)

RL型:先右旋再左旋;(1、根节点不动,让右节点去解决;2、小弟右旋到其左孩子的右边,这时树演化成了RR型;3、RR型则将根节点左旋)

下面以画图方式对四种非平衡树的旋转解法详细剖析:

1、LL型

示例1:

示例2:

示例3:

2、RR型

示例1:

示例2:

示例3:

3、LR型

示例1:

示例2:

日本蓬松去油控油修复毛糙分叉防脱洗发水

¥268.00

已失效 

示例3:

4、RL型

示例1:

示例2:


示例3:

非平衡到平衡的秘籍大法

综合上述案例分析,总结出4类非平衡树如何旋转成平衡树的以下秘笈(敲黑板划重点!!!):

  • LL型:右旋无阻碍则直接右旋;右旋有阻碍则鸠占鹊巢,然后鹊归位;

  • RR型:左旋无阻碍则直接左旋;左旋有阻碍则鸠占鹊巢,然后鹊归位;

  • LR型:先左旋(小弟)再右旋(根节点),若旋转有阻碍则鸠占鹊巢然后鹊归位;

  • RL型:先右旋(小弟)再左旋(根节点),若旋转有阻碍则鸠占鹊巢然后鹊归位;

文章评论

  • 登录后评论

点击排行