文档章节

平衡二叉树

frank21
 frank21
发布于 2016/12/07 20:41
字数 1231
阅读 32
收藏 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
浦东
高级程序员

暂无文章

day92-20180918-英语流利阅读-待学习

健身最大的敌人不是懒惰,而是逞强 Daniel 2018-09-19 1.今日导读 还记得 2008 年北京奥运会运动员刘翔的退赛风波吗?那天几乎所有中国人都将视线聚焦在了鸟巢体育馆 110 米栏的项目上,迫不...

飞鱼说编程
31分钟前
2
0
70.shell的函数 数组 告警系统需求分析

20.16/20.17 shell中的函数 20.18 shell中的数组 20.19 告警系统需求分析 20.16/20.17 shell中的函数: ~1. 函数就是把一段代码整理到了一个小单元中,并给这个小单元起一个名字,当用到这段...

王鑫linux
今天
3
0
分布式框架spring-session实现session一致性使用问题

前言:项目中使用到spring-session来缓存用户信息,保证服务之间session一致性,但是获取session信息为什么不能再服务层获取? 一、spring-session实现session一致性方式 用户每一次请求都会...

WALK_MAN
今天
6
0
C++ yield()与sleep_for()

C++11 标准库提供了yield()和sleep_for()两个方法。 (1)std::this_thread::yield(): 线程调用该方法时,主动让出CPU,并且不参与CPU的本次调度,从而让其他线程有机会运行。在后续的调度周...

yepanl
今天
4
0
Java并发编程实战(chapter_3)(线程池ThreadPoolExecutor源码分析)

这个系列一直没再写,很多原因,中间经历了换工作,熟悉项目,熟悉新团队等等一系列的事情。并发课题对于Java来说是一个又重要又难的一大块,除非气定神闲、精力满满,否则我本身是不敢随便写...

心中的理想乡
今天
57
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部