文档章节

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

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

平衡二叉树的作用

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

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

平衡二叉树的定义

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

平衡因子

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

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

平衡二叉树的构造思路

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

最小不平衡子树

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

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

调整方法四种方式:

    1,单向右旋平衡处理:

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

    2,单向左旋平衡处理:

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

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

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

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

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


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



© 著作权归作者所有

共有 人打赏支持
嗜学如命的小蚂蚁
粉丝 139
博文 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

没有更多内容

加载失败,请刷新页面

加载更多

TypeScript基础入门之JSX(二)

转发 TypeScript基础入门之JSX(二) 属性类型检查 键入检查属性的第一步是确定元素属性类型。 内在元素和基于价值的元素之间略有不同。 对于内部元素,它是JSX.IntrinsicElements上的属性类型...

durban
48分钟前
1
0
AVA中CAS-ABA的问题解决方案AtomicStampedReference

了解CAS(Compare-And-Swap) CAS即对比交换,它在保证数据原子性的前提下尽可能的减少了锁的使用,很多编程语言或者系统实现上都大量的使用了CAS。 JAVA中CAS的实现 JAVA中的cas主要使用的是...

码代码的小司机
50分钟前
2
0
Android JNI开发系列(十三) JNI异常处理

JNI 异常处理 JNI异常与JAVA处理异常的区别 JAVA 有异常处理机制,而JNI没有 如果JAVA中异常没有捕获,后面的代码不会执行,JNI会执行 JAVA编译时的异常,是在方法显示的声明了某一个异常,编...

蔡小鹏
今天
2
0
简单介绍Java 的JAR包、EAR包、WAR包区别

WAR包 WAR(Web Archive file)网络应用程序文件,是与平台无关的文件格式,它允许将许多文件组合成一个压缩文件。War专用于Web方面。大部分的JAVA WEB工程,都是打成WAR包进行发布的。 War是...

Linux就该这么学
今天
3
0
Qt那些事0.0.7

在帮助文档(Overview - QML and C++ Integration)中随缘遇到一张图,是关于C++对象与QML整合介绍的,值得标记下来,虽然大部分功能也有所涉猎,但是还是留个记号,万一哪天我失忆了还想写Q...

Ev4n
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部