文档章节

数据结构—树

多弗哥
 多弗哥
发布于 2017/09/09 20:49
字数 3736
阅读 20
收藏 0
点赞 0
评论 0

 

一、树的定义

    树(tree)也叫树状图,它是一种数据结构,由n(n>=1)个节点(node)构成的一个具有层次关系的有穷集合。我们把没有父节点(parent)的节点称为根节点(root),没有子节点(child)的节点称为叶子节点(leaf),每个节点之间的连线称为边(edge),树中节点的最大层次称为深度(depth)。空集合也是树,称为空树,空树中没有结点。

    

    我们可以看到,树具有这么几个特点:

  1. 整个树是由根结点和若干颗子树构成的;
  2. 每一个非根节点有且只有一个父节点;
  3. 每个子节点可以分为多个不相交的子树;

    这种树状图的数据结构,很明显的指出:每个节点除用于储存元素外,还拥有指向子节点集或父节点的指针,这通常包含了一个边。所以,我们用以递归方式来展开树时,使用到了树自身,这也就是树的递归特征。

    我们还能够发现,与树的展开和搜索相比,增删节点的操作更能带来大的内存消耗,因为这可能会让子树发生大量变化。

    我们一般见到的计算机文件系统大多是树的结构,尤其是目录树。每个目录(文件夹)都可以看做是一个节点,盘符看做是一个根节点,文件或空文件夹是叶子节点;目录中有指向父节点和子节点的指针。另外,Git的版本管理也很类似,用以表示整个系统的版本变化。

 

 

二、树的分类

    按节点性质和之间的关系,我们可以把树分为:无序树,有序树,二叉树等。下面,我们重点来讲二叉树这种树结构。

 

2.1  二叉树

    二叉树是一种特殊的树,它指代每个节点至多有两课子树的树结构。二叉树的子树有左右之分,次序不能颠倒。它满足如下的等式:

  • 第i层最多有 2^{i-1} 个结点;
  • 深度为k的二叉树最多有 2^k-1 个结点;

    二叉树在性质上又分为:满二叉树和完全二叉树。

  • 满二叉树:所有非叶子结点均有两个子结点。当节点数达到最大值,所有叶子结点必须在同一层上。
  • 完全二叉树:除最后一层外,其它各层的结点数都达到最大个数,且最后一层所有结点都连续集中在最左边。

    

    完全二叉树是一种效率很高的树结构,比如堆就是一种近似完全二叉树。它通常被称为二叉堆。它有两种:

  • 最大堆,即父节点的值总是大于或等于任意子节点的值;
    特点是,最大的元素在顶端,每个元素都比它的父节点小,或者相等;
  • 最小堆,父节点的值小于或等于任意子节点的值;
    特点是,最小的元素在顶端,每个元素都比它的父节点大,或者相等;

    二叉堆这种存储方式,是为了便於寻找父节点和子节点。

 

2.2  二叉查找树

    它也叫 BST(Binary Search Tree,它不是B Tree,很多人会混淆!),是一种特殊的二叉树。二叉查找树要求:没有键值相等的节点;每个节点比它左子树的任意节点要大,且比它右子树任意节点要小。比如:

       

    二叉查找树可以很方便的实现搜索算法:

  1. 从根节点开始,如果搜索的关键字与节点键值相等,那么直接命中;
  2. 如果查询的关键字小于节点键值,那么就搜索左子树;
  3. 如果查询的关键字大于节点键值,那么就搜索右子树;
  4. 如果节点的指针为空,则报告找不到相应的关键字。

    相对于插入节点而言,二叉查找树的删除节点比较复杂:

  1. 若目标节点z为叶子节点,则直接删除该节点,并修改其父节点指向子节点的指针;
  2. 若目标节点z为单支节点(即只有左子树或右子树),则其子树与其父节点相连,删除该节点,并删除其父节点指向子节点的指针和其子树根节点指向父节点的指针;
  3. 若目标节点z左右子树均不为空,则找到该节点的后继y,因为y一定没有左子树,所以修改y父节点指针,用y节点替换z节点;或者,找到z节点的前驱x,因为x一定没有右子树,所以修改x父节点指针,用x节点替换z节点。

    删除节点比较复杂,有一种简单的方法被称为“懒惰删除”。我们并不真正从二叉查找树中删除节点,而是将该节点标记为“已删除”,也就是逻辑删除。如果有相同元素插入时,我们可以将该节点找到,并取消删除标记。但这个方法带来维护上的复杂性,尤其是目标节点拥有左右子树时,所以该方法只适用于叶子节点的简单复用。

    我们可以注意到,二叉查找树搜索时的操作次数最多与树的深度相等,而且,n个节点的二叉查找树深度最多为n,最少为log(n)。log以2为基底,log(n)是指深度的量级。我们将处于同一深度的节点归为一层,如果除最后一层外的其他层都被节点填满时,二叉树拥有最小深度log(n)。

    如果二叉查找树的所有非叶子结点的左右子树结点数均保持差不多(平衡),那么二叉查找树的搜索性能逼近二分查找。但它比连续内存空间的二分查找的优点是,改变树结构时(插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销;但在经过多次插入与删除后,二叉查找树有可能退化成近似链结构,其操作的时间复杂度已经是线性的了。这就是所谓“平衡”问题。

    

    我们实际使用二叉查找树都是会加上平衡算法,以保持树结点均匀分布,即“平衡二叉树”。平衡算法是一种在B树中插入和删除结点的策略,这在下面介绍平衡二叉树时会提到。

 

2.3  多叉查找树

    分为B+树、B-树和B*树。

2.3.1  B-树

    B-树(B Tree即B树,叫B-树是为了和B+树、B*树区别开来)的定义:

  1. 所有叶子结点位于同一层;
  2. 每个结点存储M/2到M个关键字(M>2),非叶子结点存储指向关键字范围的子结点;
  3. 所有关键字在整颗树中有且只出现一次;
  4. 非叶子结点可以直接命中;

    

    B-树由于限制了除根结点以外的非叶子结点至少含有M/2个子节点,保证了结点的至少利用率。所以B-树的性能等价于二分查找,没有B树平衡的问题。也是由于M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占M/2的结点,而在删除结点时,需将两个不足M/2的兄弟结点进行合并。

2.3.2  B+树

    B+树是B-树的变体,其定义基本与B-树同:

  1. 在B-树基础上,为叶子结点增加链表指针;
  2. 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字是有序的;
  3. 非叶子结点作为叶子结点的索引(稀疏索引),叶子结点相当于是存储数据的数据层;
  4. B+树总是到叶子结点才可以命中;

    

    B+树的性能也等价于在关键字全集做一次二分查找,它非常适合文件索引系统。B+树常用于数据库和操作系统的文件系统中,比如NTFS、BFS等文件系统都在使用B+树作为元数据索引。

    B+树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度(稠密索引+稀疏索引的特性)。B+树所有的叶子结点中包含了全部关键字信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接。而B树的叶子节点并没有包括全部需要查找的信息。B+树所有的非叶子结点可以看成是叶子结点的索引,结点中仅含有其子树根结点中最大或最小的关键字,这与B树是不同的。

    它与B-树的区别,除了在于是否直到叶子节点才命中,还有:

  1. B+树的有效内容均在叶子节点,B-树的有效内容不全在叶子节点上;
  2. B+树的头指针有两个,一个指向根节点,另一个指向关键字最小的元素,因此B+树有两种遍历的方式(从根节点开始随机查询,从最小关键词顺序查询),而B-树只有一种;

2.3.3  B*树

    B*树是B+树的变体,在B+树的基础上,为非叶子结点再增加指向兄弟的链表指针,将结点的最低利用率从1/2提高到2/3。

    

    B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2)。它与B+树的区别在于:

  • B+树的分裂:

    当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针。也就是说,B+树分裂时,只影响原节点和父节点,而不会影响到兄弟节点;

  • B*树的分裂:

    当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟节点也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。也就是说,B*树分裂时,可能会需要指向兄弟的指针,所以B*树分配新结点的概率比B+树要低,空间使用率更高;

2.3.4  小结

  • BST:二叉树,每个结点只存储一个关键字,等于则命中,小于则左结点,大于则右结点;
  • B-树:多叉查找树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点。所有关键字在整颗树中有且只出现一次,非叶子结点可以直接命中;
  • B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引,而且B+树总是到叶子结点才命中;
  • B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3;

    为什么说B+树比B-树更适合应用于操作系统的文件索引和数据库索引?

  1. B+树的磁盘读写代价更低
    B+树的内部节点并没有指向关键字具体信息的指针,因为其内部节点相对B-树更小。如果把所有同一内部节点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多,一次性读入内存中的关键字也就越多,相对来说IO读写次数也就降低了。当需要把内部节点读入内存中的时候,B-树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转的时间);
  2. B+树的查询效率更稳定
    由于被叶子节点并不是最终指向文件内容的节点,而只是叶子节点中关键字的索引。所以,任何关键字的查找必须走从根节点到叶子节点的路径。所有关键字查询的路径长度相同,也就意味着每一个数据的查询效率相当。

 

2.4  平衡二叉树

    也称为AVL树(有别于AVL算法),它是一种的二叉查找树,它要求:任意节点的左右两个子树的深度差不超过1,且左右子树都是平衡二叉树。

    我们在介绍BST时说过,深度越小,搜索所需的运算时间越小。有的时候树结构中的结点并不是均匀分布的,树的每一层都有很多空位。就算刚开始树是平衡的(Balance,就是节点分布均匀,而不是偏向某一侧),但在多次操作之后,由于在删除时,我们总是选择将待删除节点的后继代替它本身,这样就会造成右子树的节点数总是在减少,以至于树向左偏沉。能不能尽可能减少每一层的空位呢,或者相应的减少树的深度?有一种想法是先填满这一层,再去填下一层,这样就是一个完全二叉树。但这样的二叉树实现插入算法比较复杂,有一个比较容易实现的树状数据结构,就是AVL树。

    它调整平衡的基本思想,就是旋转。

  • 单旋转:

 

  • 双旋转:

 

 

2.4  红黑树

 

 

 

 

 

※ 附录:

参考:

© 著作权归作者所有

共有 人打赏支持
多弗哥
粉丝 6
博文 29
码字总数 106641
作品 0
杭州
高级程序员
游戏开发与程序设计知识总结02——数据结构

更新日志 每此对思维导图有改动或者在github中有了对应的实现,则增加一条更新日志。 2017.9.2: 确定更新为系列文章并持续维护 更新B树,B+树,红黑树的参考链接 更新了Huffman树的标注 前言...

kashiwa ⋅ 2017/08/31 ⋅ 0

数据结构—概述

数据结构概述: 程序设计 = 数据结构 + 算法 数据结构:数据元素之间存在所有特定关系的集合,数据结构可以分为物理结构和逻辑结构 逻辑结构: (1)集合结构——元素同属于一个集合 (2)线...

翼动动空 ⋅ 2016/05/08 ⋅ 0

一文掌握关于Java数据结构所有知识点(欢迎一起完善)

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

snailclimb ⋅ 05/08 ⋅ 0

实锤:写高质量代码,不然加密货币仍然可被攻击并篡改

策划|Tina编译|核子可乐区块链前哨导语: 我们知道区块链是一个个 Block 组成,而 Block 由校验值和实际数据组成,通常 Block 的头部存放着前一个 Block 的 Hash 校验值。适合编写区块链的...

雪花又一年 ⋅ 04/12 ⋅ 0

(转) 坚持完成这套学习手册,你就可以去 Google 面试了

C++ —— 不使用内建的数据类型。C++ —— 使用内建的数据类型,如使用 STL 的 std::list 来作为链表。Python —— 使用内建的数据类型(为了持续练习 Python),并编写一些测试去保证自己代...

wangxiaocvpr ⋅ 2016/10/12 ⋅ 0

数据结构课程主页-2016级

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

sxhelijian ⋅ 2017/08/30 ⋅ 0

基于Hadoop生态圈的数据仓库实践 —— 进阶技术(七)

七、递归 数据仓库中的关联实体经常表现为一种“父—子”关系。在这种类型的关系中,一个父亲可能有多个孩子,而一个孩子只能属于一个父亲。例如,一个人只能被分配到一个部门,而一个部门可...

wzy0623 ⋅ 2016/07/28 ⋅ 0

数据库领域即将迎来革命?Jeff Dean 带队用机器学习颠覆数据索引方法

  AI 科技评论按:伴随着机器学习理论和技术的发展、以及机器学习作为一门学科有越来越多的人关注以及参与,机器学习的落地应用场景也越来越多、越来越多样化。这两年的热门的应用大家都已...

AI科技评论 ⋅ 01/05 ⋅ 0

Android技能树 — 树基础知识小结(一)

前言: 现在安卓面试,对于数据结构的问题也越来越多了,也经常看到别人发的面试题都是问什么红黑树,二叉树查找等,所以我们虽然不会马上就会各种难的面试题,但起码树的基础知识还是要会的...

青蛙要fly ⋅ 05/04 ⋅ 0

数据结构——树

一、树的定义 树是n(n>=0)个结点的有限集。n=0时称为空树,在任意一颗非空树:1、有且仅有一个特定的根结点。2、当n>1时其余结点可分为m(m>0)个互不相交的有限集T1、T2、.....Tm,其中每一个...

lxq_xsyu ⋅ 2014/12/07 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Kubeflow实战系列:利用TFJob导出分布式TensorFlow模型

介绍 本系列将介绍如何在阿里云容器服务上运行Kubeflow, 本文介绍如何使用TfJob导出分布式模型训练模型。 第一篇:阿里云上使用JupyterHub 第二篇:阿里云上小试TFJob 第三篇:利用TFJob运行...

全部原谅 ⋅ 13分钟前 ⋅ 0

007. 深入JVM学习—老年代

老年代空间的主要目的是用于存储由Eden发送来的对象,一般在经历好几次“Minor GC”还会保存下来的对象,才会被复制到老年代,这样就可以存放更多的对象,同时在老年代中执行GC的次数也相对较...

影狼 ⋅ 14分钟前 ⋅ 0

常见的一些C#开源框架或者开源项目

原:https://blog.csdn.net/qq_27825451/article/details/70666044 Json.NET http://json.codeplex.com/ Json.Net 是一个读写Json效率比较高的.Net框架.Json.Net 使得在.Net环境下使用Json更......

whoisliang ⋅ 14分钟前 ⋅ 0

设计模式基本原理

刚开始接触编程这行的时候看过设计模式,当时感觉学这些模式没有太大的用处,当时也看不太懂。但是随着慢慢接触这一行,经过一段时间的编程以后,再回过头来看设计模式,发现设计模式的确是太...

王子城 ⋅ 18分钟前 ⋅ 0

阿里云全面支持IPv6!一文揽尽4位大咖精彩演讲

摘要: 自从去年11月以来,阿里巴巴高度重视数据中心的网络改造、云产品改造、应用及网络改造等多个维度,经过半年以来的建设,阿里云已经完成了域名解析等关键产品的分析,现在阿里云已经完...

传授知识的天使 ⋅ 28分钟前 ⋅ 0

windows Android sdk 配置

1、下载Android SDK,点击安装,直接默认路径即可! 下载地址:http://developer.android.com/sdk/index.html 2、默认路径安装后,安装完成,开始配置环境变量。 3、打开计算机属性——高级系...

阿豪boy ⋅ 31分钟前 ⋅ 0

bash shell script 简明教程

User <--> bash <--> kernel shell is not kernel or part of kernel various shells: tcsh, csh, bash, ksh find the using shell: echo $SHELL find all the shells: cat /etc/shells what......

mskk ⋅ 33分钟前 ⋅ 0

Service Mesh简史

William Morgan Service Mesh是一个相当新的概念,讲它的“历史”似乎有些勉强。就目前而言,Service Mesh已经在部分企业生产环境中运行了超过18个月,它的源头可以追溯到2010年前后互联网公...

好雨云帮 ⋅ 34分钟前 ⋅ 0

10个免费的服务器监控工具

监控你的WEB服务器或者WEB主机运行是否正常与健康是非常重要的。你要确保用户始终可以打开你的网站并且网速不慢。服务器监控工具允许你收集和分析有关你的Web服务器的数据。 有许多非常好的服...

李朝强 ⋅ 46分钟前 ⋅ 0

压缩工具之zip-tar

zip 支持目录压缩。使用yum安装zip包,使用yum安装unzip包 zip 1.txt.zip 1.txt #将1.txt文件压缩,新生成的压缩文件为1.txt.zip,原文件保留 zip -r 123.zip 123/ #-r对目录操作。将123/目录...

ZHENG-JY ⋅ 47分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部