文档章节

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

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

平衡二叉树的作用

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

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

平衡二叉树的定义

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

平衡因子

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

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

平衡二叉树的构造思路

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

最小不平衡子树

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

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

调整方法四种方式:

    1,单向右旋平衡处理:

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

    2,单向左旋平衡处理:

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

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

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

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

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


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



© 著作权归作者所有

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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

spring 容器实现对bean的管理(注解方式解析,源码阅读)

因为最近在研究学习spring boot,所以这里想详细学习回顾了一下spring 容器对bean的一些管理方式和部分源码学习。 首先初始类AnnotationConfigApplicationContext,简单源码查看,支持两个参...

小海bug
19分钟前
0
0
数据结构:二分查找 java

二分查找的前提是有序存储,利用顺序存储和元素排序 /** * 二分查找,查找成功,返回下标记 * @param values * @param begin * @param end * @param key * @param <T> * @ret...

京一
36分钟前
0
0
@SpringBootApplication 注解

@SpringBootApplication注解是一个组合注解,包含以下注解 @Target(ElementType.TYPE) 注解的作用目标 @Retention(RetentionPolicy.RUNTIME) Reteniton的作用是定义被它所注解的注解保留多久,...

java.刘
49分钟前
0
0
sentinel自定义DataSource实战

序 本文主要研究一下如何自定义sentinel的DataSource,这里以jdbc为例。 maven <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-sen......

go4it
今天
1
0
xgboost/gbdt在调参时为什么树的深度很少就能达到很高的精度?

问题: 用xgboost/gbdt在在调参的时候把树的最大深度调成6就有很高的精度了。但是用DecisionTree/RandomForest的时候需要把树的深度调到15或更高。用RandomForest所需要的树的深度和Decisio...

tantexian
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部