您现在的位置是:首页 > 学无止境
平衡二叉排序树|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型:先右旋(小弟)再左旋(根节点),若旋转有阻碍则鸠占鹊巢然后鹊归位;
文章评论
- 登录后评论
点击排行
-
php-fpm安装、配置与优化
转载自:https://www.zybuluo.com/phper/note/89081 1、php中...
-
centos下postgresql的安装与配置
一、安装(以root身份进行)1、检出最新的postgresql的yum配置从ht...
-
Mysql的大小写敏感性
MYSQL在默认的情况下查询是不区分大小写的,例如:CREATE TABLE...
-
关于URL编码
转载自:http://www.ruanyifeng.com/blog/2010/02/url_encoding....
-
header中的Cache-control
网页的缓存是由HTTP消息头中的“Cache-control”来控制的,常见的...