文档章节

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

嗜学如命的小蚂蚁
 嗜学如命的小蚂蚁
发布于 2016/02/09 20:06
字数 523
阅读 205
收藏 6
点赞 1
评论 0

平衡二叉树的作用

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

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

平衡二叉树的定义

    若一个二叉树中每个结点的左右子树的高度至多相差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

数据结构课程主页-2016级

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

sxhelijian ⋅ 2017/08/30 ⋅ 0

算法-数据结构

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

掘金官方 ⋅ 2017/12/14 ⋅ 0

小蚂蚁学习数据结构(32)——二叉排序树的概念

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

嗜学如命的小蚂蚁 ⋅ 2016/02/07 ⋅ 0

小蚂蚁学习数据结构(17)——树、二叉树性质、储存方式

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

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

爱喝啤酒的程序员如何学习数据结构

如果在相亲时你说你是程序员,对方——一般是女的——会投来异样的眼光。程序员在其他人的眼中的形象一般是思维逻辑有问题,或木纳,或有点儿轴,或是书呆子。但凡事都在变化,程序员也在变化...

oschina ⋅ 2012/11/05 ⋅ 54

小蚂蚁学习数据结构(20)——线索二叉树的概述

线索二叉树 遍历二叉树,实质上是对一个非线性结构进行线性化操作,使得每个节点在这些线性序列中有且仅有一个直接前驱和直接后驱。 线索:指向前驱或后继节点的指针被称为线索。 线索二叉树...

嗜学如命的小蚂蚁 ⋅ 2016/01/20 ⋅ 0

javascript算法之二叉搜索树

什么是二叉树 二叉树就是树的每个节点最多只能有两个子节点 什么是二叉搜索树 二叉搜索树在二叉树的基础上,多了一个条件,就是二叉树在插入值时,若插入值比当前节点小,就插入到左节点,否...

光哥很霸气 ⋅ 2017/09/11 ⋅ 0

优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆 ⋅ 2011/12/03 ⋅ 0

当我们在聊TreeMap(一)——红黑树详解Java代码实现

本文出自:https://blog.csdn.net/DT235201314/article/details/80661157 一丶概述 上一篇讲HashMap,避开了红黑树,这边讲TreeMap,好好说一下红黑树。 二丶概述目录图 三丶聊聊TreeMap 数据...

天一方蓝 ⋅ 06/13 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

行政区划代码转为字典形式

原数据为: http://www.mca.gov.cn/article/sj/xzqh/2018/201804-12/201804-06041553.html 手动替换了一下格式,并使用下面的代码处理. # 输入格式s = """110000:北京市110101:东城区1101...

漫步海边小路 ⋅ 14分钟前 ⋅ 0

android apk 签名

创建key,需要用到keytool.exe (位于C:\Program Files\Java\jdk1.6.0_10\bin目录下),使用产生的key对apk签名用到的是jarsigner.exe (位于C:\Program Files\Java\jdk1.6.0_10\bin目录下),把...

国仔饼 ⋅ 22分钟前 ⋅ 0

springcloud+jps+mybatis多数据库配置

多数据库配置 配置我们目录结构设置: config ---datasource ----jpa ----mybatis ----redis Datasource中是数据的相关配置 Jap中是springDatajpa的相关配置 Mybatis中是mybatis的相关配置 ...

大-智-若-愚 ⋅ 29分钟前 ⋅ 0

Spring mvc HandlerMapping 实现机制

概述 当DispatcherServlet接受到客户端的请求后,SpringMVC 通过 HandlerMapping 找到请求的Controller。 HandlerMapping 在这里起到路由的作用,负责找到请求的Controller。 Spring MVC 默认...

轨迹_ ⋅ 33分钟前 ⋅ 0

JavaScript零基础入门——(十)JavaScript的DOM基础

JavaScript零基础入门——(十)JavaScript的DOM基础 欢迎大家回到我们的JavaScript零基础入门,上一节课,我们了解了JavaScript中的函数,这一节课,我们来了解一下JavaScript的DOM。 第一节...

JandenMa ⋅ 今天 ⋅ 0

Weex起步

本教程假设你已经在你的本地环境安装了node 其实weex起步教程在 https://github.com/lilugirl/incubator-weex 项目说明文件中都已经有了,但为了有些同学看到英文秒变文盲,所以这里我重新写...

lilugirl ⋅ 今天 ⋅ 0

Jenkins实践1 之安装

1 下载 http://mirrors.jenkins.io/war/latest/jenkins.war 2 启动 java -jar jenkins.war 前提:安装jdk并配置环境变量 启动结果节选: ************************************************......

晨猫 ⋅ 今天 ⋅ 0

组合数学 1-2000 中,能被6或10整除的数的个数

1--2000 中,能被6或10整除的数的个数 利用集合的性质 能被6整除的个数 2000/6 = 333 能被10整除的个数 2000/10 = 200 能被6和10整除的个数 2000/30 = 66 能被6或10整除的个数 333+200-66 =...

阿豪boy ⋅ 今天 ⋅ 0

一篇文章学懂Shell脚本

Shell脚本,就是利用Shell的命令解释的功能,对一个纯文本的文件进行解析,然后执行这些功能,也可以说Shell脚本就是一系列命令的集合。 Shell可以直接使用在win/Unix/Linux上面,并且可以调用...

Jake_xun ⋅ 今天 ⋅ 0

大数据工程师需要精通算法吗,要达到一个什么程度呢?

机器学习是人工智能的一个重要分支,而机器学习下最重要的就是算法,本文讲述归纳了入门级的几个机器学习算法,加大数据学习群:716581014一起加入AI技术大本营。 1、监督学习算法 这个算法由...

董黎明 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部