文档章节

平衡二叉树

frank21
 frank21
发布于 2016/12/07 20:41
字数 1231
阅读 35
收藏 2

平衡二叉树

##定义 二叉树的左子树的深度和右子树的深度差不超过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
粉丝 12
博文 15
码字总数 15213
作品 0
浦东
高级程序员
私信 提问

暂无文章

MySQL主从配置——双主

MySQL主从配置——双主 本人是测试环境,准备了两台安装好mysql的服务器(masterA和masterB),可以保证没数据写入,否则需要先将两台服务器上的数据一致,然后再进行主从配置,步骤是:先m...

弓正
26分钟前
9
0
centos下如何使用 beyond compare 对比工具

我这里的环境是centos7桌面版 三条命令安装beyond compare wget http://www.scootersoftware.com/bcompare-4.2.3.22587.x86_64.rpmrpm --import http://www.scootersoftware.com/RPM-GPG-K......

linuxprobe16
30分钟前
6
0
http协议请求头的意义

GET /day31_Http_306/index.jsp HTTP/1.1: GET请求,请求服务器路径为/hello/index.jsp,协议为1.1 请求头 1.Host:localhost:请求的主机名为localhost2.User-Agent:Mozilla/5.0(Windows NT......

潇潇程序缘
今天
9
0
Netty 简单服务器 (三)

经过对Netty的基础认识,设计模型的初步了解,来写个测试,试试手感 上篇也说到官方推荐我们使用主从线程池模型,那就选择这个模型进行操作 需要操作的步骤: 需要构建两个主从线程组 写一个服务器...

_大侠__
今天
19
0
day02:管道符、shell及环境变量

1、管道符:"|" 用于将前一个指令的输出作为后一个指令的输入,且管道符后面跟的是命令(针对文档的操作):cat less head tail grep cut sort wc uniq tee tr split sed awk等) [root@localho...

芬野de博客
今天
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部