文档章节

平衡二叉树

frank21
 frank21
发布于 2016/12/07 20:41
字数 1231
阅读 31
收藏 2
点赞 0
评论 0

平衡二叉树

##定义 二叉树的左子树的深度和右子树的深度差不超过2,左子树和右子树本身也是平衡二叉树

##结点的高度 本文假设二叉树的叶子结点的高度为1,父结点的高度等于较高子结点的高度加1,也就是如下公式:

输入图片说明

我们用h(left)h(right)表示结点左右子树的高度,h(b_left)表示b的左孩子结点的高度,如果左孩子结点为NULL,则返回0,其他表示类似。

##结点的旋转

  • 左旋转

输入图片说明

  • 右旋转

输入图片说明

  • 旋转的意义

从上面两种旋转的图可以看到,旋转的会使左右子树的高度发生变化,以左旋转为例,旋转之前左右子树的高度为:

输入图片说明

输入图片说明

旋转之后左右子树的高度为:

输入图片说明

输入图片说明

通过公式可以看出,左子树的高度至少提升1,右子树的高度至少降低1,所以左旋会使右子树的高度降低,相反, 右旋会使左子树的高度降低。明白了这个道理,后面对于平衡二叉树的增加和删除结点后的再平衡,就很好处理了,因为二叉树的再平衡实际上就是调整左右子树的高度而已。但是有一种情况我们必须避免,就是h(left)- h(right)==2的情况经过旋转之后出现h(right)- h(left)==2,这样就没有达到再平衡的效果,只是从一个极端到另一个极端,下面我们分析下什么时候会出现这种情况,假设加入某结点导致某个结点的左右子树高度差等于2了。未旋转之前如下:

输入图片说明

整理可以得到:

输入图片说明                ①

旋转之后的情况如下:

输入图片说明

整理可以得到:

输入图片说明                 ②

如果h(b_left) > h(b_right),等式①如下:

  • h(b_left) = h(a_left) + 1 代入等式②, 如下:
  • max(h(a_left) + 1, h(a_left)) = h(b_right) + 1 ==>h(a_left) + 1 = h(b_right) + 1

最终得到

输入图片说明                                                            ③

如果h(b_left) <= h(b_right) 会得到如下等式

  • max(h(b_left), h(a_left)) =h(a_left) + 2

可以看到如果h(b_left) > h(a_left) ==> h(b_left) - h(a_left) =2 这样导致添加结点前二叉树就不是一个平衡二叉树了,所以这种情况忽略;如果h(a_left) > h(b_left) ==> h(a_left) - h(a_left) =2, 这种个情况更不存在,所以最终我们得到等式③,如果最初的条件是h(right) - h(left) == 2, 我们还会得到下面的等式

输入图片说明                                                          ④

所以在h(a_left) = h(b_right) 或者 h(b_left) = h(a_right)时会出现我们提到的极端情况,请记住③④公式,下面我们介绍平衡二叉树增删结点时会解释这两个公式的意义。

##平衡二叉树增加结点 我们先从最简单的平衡二叉树开始,最简单的平衡二叉树有如下两种形式,他们在插入结点时,可能导致二叉树失衡。

结点的二叉树

导致二叉树失衡不外乎下面四种情况:

输入图片说明

图中的a结点都是失衡结点,a、b两种情况可以通过旋转失衡结点来达到再平衡的目的,而c、d却不行,其根本原因就是它符合我们上面得出的③④两个公式,导致直接旋转失衡结点不能达到再平衡的目的,简单的办法就是通过把c、d转化为a、b两种形式,再进行处理,仔细观察可以看到,通过旋转b结点可以分别将c、d转换为a、b两种形式,这样再旋转失衡结点a就可以达到再平衡的目的。至于做何种旋转,通过上面的分析很容易就可以得到:

  • a情况当然是右旋转(右旋转可以降低左子树的高度,增加右子树的高度)
  • b情况当然是左旋转 (左旋转可以降低右子树的高度,增加左子树的高度)
  • c当然是要转换为a情况,所以要先把b结点左旋转,然后再处理a情况
  • d当然是要转换为b情况,所以要先把b结点右旋转,然后再处理b情况

通过上面的分析,可以得到下面简单的伪代码

sub_tree = taller_child(unbalance_node) //taller_child表示获取结点的较高孩子结点
sub_sub_tree = taller_child(sub_tree)
if (sub_tree == left(unbalance_node) && sub_sub_tree == left(sub_tree))
   //a情况
   left_rotate(unbalance_node)
else if (sub_tree == right(unbalance_node) && sub_sub_tree == right(sub_tree))
  //b情况
  right_rotate(unbalance_node)
else if (sub_tree == left(unbalance_node) && sub_sub_tree == right(sub_tree))
  //c情况
  right_rotate(sub_tree)
  left_rotate(unbalance_node)
else
  //d情况
  left_rotate(sub_tree)
  right_rotate(unbalance_node)

##平衡二叉树删除结点

删除结点首先是按照二叉树删除结点的方法删除指定结点,然后从删除结点的父节点寻找失衡结点 按照增加结点处理失衡结点的方法处就可以了。

© 著作权归作者所有

共有 人打赏支持
frank21
粉丝 11
博文 15
码字总数 15213
作品 0
浦东
高级程序员

暂无相关文章

一篇文章学懂Shell脚本

Shell脚本,就是利用Shell的命令解释的功能,对一个纯文本的文件进行解析,然后执行这些功能,也可以说Shell脚本就是一系列命令的集合。 Shell可以直接使用在win/Unix/Linux上面,并且可以调用...

Jake_xun ⋅ 24分钟前 ⋅ 0

大数据工程师需要精通算法吗,要达到一个什么程度呢?

机器学习是人工智能的一个重要分支,而机器学习下最重要的就是算法,本文讲述归纳了入门级的几个机器学习算法,加大数据学习群:716581014一起加入AI技术大本营。 1、监督学习算法 这个算法由...

董黎明 ⋅ 57分钟前 ⋅ 0

Kylin 对维度表的的要求

1.要具有数据一致性,主键值必须是唯一的;Kylin 会进行检查,如果有两行的主键值相同则会报错。 2.维度表越小越好,因为 Kylin 会将维度表加载到内存中供查询;过大的表不适合作为维度表,默...

无精疯 ⋅ 今天 ⋅ 0

58到家数据库30条军规解读

军规适用场景:并发量大、数据量大的互联网业务 军规:介绍内容 解读:讲解原因,解读比军规更重要 一、基础规范 (1)必须使用InnoDB存储引擎 解读:支持事务、行级锁、并发性能更好、CPU及...

kim_o ⋅ 今天 ⋅ 0

代码注释中顺序更改 文件读写换行

`package ssh; import com.xxx.common.log.LogFactory; import com.xxx.common.log.LoggerUtil; import org.apache.commons.lang3.StringUtils; import java.io.*; public class DirErgodic ......

林伟琨 ⋅ 今天 ⋅ 0

linux实用操作命令

参考 http://blog.csdn.net/qwe6112071/article/details/50806734 ls [选项] [目录名 | 列出相关目录下的所有目录和文件 -a 列出包括.a开头的隐藏文件的所有文件-A 同-a,但不列出"."和"...

简心 ⋅ 今天 ⋅ 0

preg_match处理中文符号 url编码方法

之前想过直接用符号来替换,但失败了,或者用其他方式,但有有些复杂,这个是一个新的思路,亲测可用 <?php$str='637朗逸·超速新风王(300)(白光)'; $str=iconv("UTF-8","GBK",$s...

大灰狼wow ⋅ 今天 ⋅ 0

DevOps 资讯 | PostgreSQL 的时代到来了吗 ?

PostgreSQL是对象-关系型数据库,BSD 许可证。拼读为"post-gress-Q-L"。 作者: Tony Baer 原文: Has the time finally come for PostgreSQL?(有删节) 近30年来 PostgreSQL 无疑是您从未听...

RiboseYim ⋅ 今天 ⋅ 0

github太慢

1:用浏览器访问 IPAddress.com or http://tool.chinaz.com 使用 IP Lookup 工具获得github.com和github.global.ssl.fastly.net域名的ip地址 2:/etc/hosts文件中添加如下格式(IP最好自己查一...

whoisliang ⋅ 今天 ⋅ 0

非阻塞同步之 CAS

为解决线程安全问题,互斥同步相当于以时间换空间。多线程情况下,只有一个线程可以访问同步代码。这种同步也叫阻塞同步(Blocking Synchronization). 这种同步属于一种悲观并发策略。认为只...

长安一梦 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部