文档章节

小蚂蚁学习数据结构(34)——平衡二叉树的概念

嗜学如命的小蚂蚁
 嗜学如命的小蚂蚁
发布于 2016/02/09 20:06
字数 523
阅读 211
收藏 6

平衡二叉树的作用

    由于二叉排序树的结构可能不平衡,导致对树的运算的时间复杂度增加。

    调整二叉排序树的结构,使其始终成为平衡的状态——平衡二叉树。

平衡二叉树的定义

    若一个二叉树中每个结点的左右子树的高度至多相差1,则称此树为平衡树

平衡因子

    二叉树中的每个结点的左子树高度减去右子树高度。

    平衡树中的每个结点的平衡因子只能是:1、0、-1

平衡二叉树的构造思路

    在构造平衡二叉树的过程中,每当插入一个结点时,首先检查是否因为插入而破坏了树的平衡性,若是,则找出其中最小不平衡子树,在保持排序树特性的前提下,调整最小不平衡子树中个结点之间的链接关系,以达到新的平衡。

最小不平衡子树

    以离插入结点最近,且平衡因子绝对值大于1的结点作为根的子树。

需要对最小不平衡树进行调整

调整方法四种方式:

    1,单向右旋平衡处理:

        在左子树根节点的左子树上插入结点,可以进行一次向右的顺时针旋转操作。

    2,单向左旋平衡处理:

        在右子树根节点的右子树上插入结点,可以进行一次向左的逆时针旋转操作。

    3,双向旋转(先左后右)

        在左子树的右子树上插入结点,先进行一次左的逆时针旋转,再进行一次向右的顺时针旋转。

    4,双向旋转(先右后左)

        在右子树的左子树上插入结点,先进行一次右的顺时针旋转,再进行一次向左的逆时针旋转。


    学PHP的小蚂蚁 博客 http://my.oschina.net/woshixiaomayi/blog



© 著作权归作者所有

共有 人打赏支持
嗜学如命的小蚂蚁
粉丝 142
博文 161
码字总数 100864
作品 0
郑州
程序员
私信 提问
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb
05/08
0
0
数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian
2017/08/30
0
0
小蚂蚁学习数据结构(32)——二叉排序树的概念

二叉排序树,定义: 1,若左子树非空,则左子树上所有节点的关键字均小于根节点关键字。 2,若右子树非空,则右子树上所有节点的关键字均大于根节点关键字。 3,左右子树本身又是一颗二叉树。...

嗜学如命的小蚂蚁
2016/02/07
112
0
算法-数据结构

时间复杂度 O(log n) 意味着什么? 写给小白的时间复杂度指南 查找算法的 Java 实现 查找算法的 Java 实现 两个有序数组合并成一个有序数组 用拉链法和线性探测法解决哈希冲突 用拉链法和线性...

掘金官方
2017/12/14
0
0
小蚂蚁学习数据结构(17)——树、二叉树性质、储存方式

树 是一类非线性数据结构,是以分支关系定义的层次结构。 特点: 至少有一个节点——根,只有根的树成为最小树 树中各子树是互不相交的集合 术语(略) 二叉树 特点: 每个节点最多有二颗子树...

嗜学如命的小蚂蚁
2016/01/17
66
0

没有更多内容

加载失败,请刷新页面

加载更多

新手也能看懂,消息队列其实很简单

该文已加入开源项目:JavaGuide(一份涵盖大部分Java程序员所需要掌握的核心知识的文档类项目,Star 数接近 16k)。地址:https://github.com/Snailclimb/JavaGuide. 本文内容思维导图: 消息...

阿里云官方博客
44分钟前
5
0
如何在Chrome浏览器中启动deviceready事件(尝试调试phonegap项目)?

我正在开发PhoneGap应用程序,我希望能够在Chrome中调试它,而不是在电话上调试。但是,我在onGetReady()函数中初始化我的代码,该函数在PhoneGap触发“deviceready”事件时触发。由于Chr...

kisshua
今天
10
0
nginx中部署vue打包后的静态文件

如何在nginx中部署静态资源就不描述了, 请看我的这篇博客 将vue脚手架项目打包后的静态文件放到nginx上, 发现有个问题, 即url上有#, 怎么去掉这个#呢. 1 项目中router的mode 路由的mode要为h...

克虏伯
今天
13
0
JS容易理解错误的地方

在这端代码执行的末尾,你会不会hi变量回事函数中的hi了?你会不会认为这不是按引用传递了? 对值传递和引用传递产生质疑了? 1 var hi = {};2 function sayHello(hi) { ...

器石_
今天
10
0
Java开发学习--MongoDB

之前只学过sql,第一次使用非关系型数据库。以前对于关系型数据库与非关系型数据库的概念很模糊,通过这次的学习对这两者有了一个清晰的概念。 主键 在MongoDB中,主键名叫"_id",如果在生成...

微笑向暖wx
今天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部