树形结构的概念_护理理论四个基本概念

树形结构的概念_护理理论四个基本概念转自:https://blog.csdn.net/zhangyuan19880606/article/details/51220561树型结构的基本概念对大量的输入数据,链表的线性访问时间太慢,不

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

转自:https://blog.csdn.net/zhangyuan19880606/article/details/51220561

树型结构的基本概念

对大量的输入数据,链表的线性访问时间太慢,不宜使用。本文探讨另外一种重要的数据结构—-树,其大部分时间可以保证操作的运行平均时间复杂度为O(logN),第一部分先来看一下树的一些预备知识。

首先看一下树形结构的样子,下图代表的是树型结构的一般形态:

树形结构的概念_护理理论四个基本概念

由上图看得出树是一些节点的集合,总结一下树的一些基本概念:

1、结点:树中的数据元素都称之为结点

2、根:最上面的结点称之为根,一颗树只有一个根且由根发展而来,从另外一个角度来说,每个结点都可以认为是其子树的根

3、父亲:结点的上层结点,如图中,结点K的父亲是E、结点L的父亲是G

4、兄弟:具有相同父亲的结点称为兄弟,图中F、G、H互为兄弟

5、结点的度:结点所拥有的子树的个数称之为结点的度,如结点B的度为3

6、树叶:度为0的结点,也叫作终端结点,图中D、K、F、L、H、I、J都是树叶

7、分支结点:度不为0的结点,也叫作非终端结点或内部结点,图中根、A、B、C、E、G都是分支结点

8、结点的层次:从根节点到树中某结点所经路径上的分支树称为该结点的层次,根节点的层次规定为1,其余结点的层次等于其父亲结点的层次+1

9、树的深度:树中结点的最大层次数,图中树的深度为4

 

二叉树

上面的是树的一般形态,下面看一下二叉树。二叉树是一棵树,其中每个结点都不能有多于两个子树。

下图展示了一颗二叉树:

树形结构的概念_护理理论四个基本概念

二叉树的一个性质是一颗平均二叉树的深度要比及结点个数N小得多,这个性质很重要,尤其对于特殊类型的二叉树即二叉查找树而言,其深度的平均值是O(logN),这将大大降低查找时的时间复杂度。

当然,二叉树在运用得不好的情况下的情况下是有严重的问题的,即:

树形结构的概念_护理理论四个基本概念

树的深度大到了N-1,这样的情况是绝对不允许的,这种树也被称为不平衡树。在下一部分的二叉查找树说明完之后,会讲让二叉树带有自平衡条件,成为平衡树。

 

二叉查找树

二叉树的一个重要应用是在它们查找中的使用。假设树中的每个结点存储一项数据,使得二叉树成为二叉查找树的性质是:对于树中的每个结点X,它的左子树中所有项的值小于X,而它的右子树中所有项的值大于X,这意味着该树所有的元素可以用某种一致的方式排序。

如下图:

树形结构的概念_护理理论四个基本概念

这就是一个二叉查找树。但是如果我这么修改一下:

树形结构的概念_护理理论四个基本概念

这就不是一个二叉查找树了,因为在根节点的左子树中,有一个节点是11。

 

AVL树

前面已经讲到过了,在生成二叉树/二叉查找树的时候是非常容易失衡的,造成的最坏的情况就是一边倒(只有左子树/右子树),这样将会导致树的检索效率大大降低,所以为了维持二叉树的平衡,大牛们提出了各种实现的算法,如:AVL树、节点大小平衡树(SBT)、伸展树、树堆(Treap)、红黑树等等。

这里讲AVL树—-一种带有平衡条件的二叉查找树,这种平衡条件必须要容易保持,而且它保证树的深度必须是O(logN)。

对于AVL树来说,它的平衡必须满足以下特征之一:

1、空树

2、每个结点的左子树和右子树深度最多差1

可以看一下下图:

树形结构的概念_护理理论四个基本概念

图中,左边的树是AVL树,右边的树不是。因为很显然,从根结点7看起,右子树的深度为1,而左子树7–>2–>4–>5(3)这条路径深度为3,不满足每个结点的左子树和右子树深度最多差1的条件。

可以证明,一颗AVL树的高度最多为1.44 * log(N + 2) – 1.328,但是实际上的高度只略大于logN。

 

红黑树

红黑树是对AVL树的另一种变种。红黑树顾名思义就是结点是红色或者黑色的平衡二叉树,它通过颜色的约束来维持着二叉树的平衡。下图为一颗典型的二叉树:

树形结构的概念_护理理论四个基本概念

对于一颗有效的红黑树而言我们必须增加如下规则:

1、每个结点都只能是红色或者黑色

2、根节点是黑色

3、每片叶子都是黑色的

4、如果一个结点是红色的,则它的两个子节点都是黑色的,也就是说在一条路径上不能出现相邻的两个红色结点

5、从任意一个结点到其每个叶子的所有路径都包含着相同数目的黑色结点

这些约束强制了红黑树的关键性质:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果就是这棵树大致上是平衡的,因为插入、删除和查找某个值得最坏情况时间都要求与树的高度成比例,这个高度理论上限允许红黑树只在最坏情况下都是高效的。

再具体就不说了,可以参看http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html,对红黑树的讲解写得非常好。

对了,TreeMap和TreeSet就是红黑树的典型实现

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168282.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • AvalonDock 2.0 的简单运用

    AvalonDock 2.0 的简单运用最近在研究AvalonDock的一些使用,碰到了一些问题。现在拿出来跟大家分享分享。网上找了一大把AvalonDock1.3版本的资料,弄出Demo后发现属性面板(DockableContent)设置成浮动后不能停靠其它的面板。最后只得试试AvalonDock2.0版本的,还好2.0版本没让我们失望。首先需要库文件:Xceed.Wpf.AvalonDock…

  • Google虚拟机_免费google账号

    Google虚拟机_免费google账号 GoogleAppEngine是Google推出的免费虚拟主机空间,其实这比一般虚拟主机强悍的多,你可以利用GoogleAppEngine工具来开发网站或制作网络应用程序,Google会在自己的庞大服务器集群上为你提供空间、带宽、资源等。目前GoogleAppEngine为每个用户提供10个Application(简称App),每个App有500M免费空间,每个App限制100

    2022年10月15日
  • 内测体验:JetBrains面向未来的Fleet编辑器是什么+究竟怎样 使用初体验+与vsc对比

    内测体验:JetBrains面向未来的Fleet编辑器是什么+究竟怎样 使用初体验+与vsc对比引言上个月,我在看到某公众号推广后,作为热衷于先进技术、常年游历于各个软件公司内测组的用户自然是早早申请了内测。因为在申请时官网的公告是“我们也不知道新一代编辑器(Fleet)什么时候可以与大家见面”,因此我也没有过多在意。令人意外的是,昨天晚上22:09,我收到了来自JetBrains的邮件。此处点名一下GitHubCopilot项目,申请完了这么久还不给个信[手动旺柴]简介如果你实在不知道什么是JetBrains,那你也应该知道PyCharm,再次也要知道AndroidStudio。

  • bs架构与cs架构的区别详细讲解_cs架构的优缺点

    bs架构与cs架构的区别详细讲解_cs架构的优缺点C/S结构,即Client/Server(客户机/服务器)结构,是大家熟知的软件系统体系结构,通过将任务合理分配到Client端和Server端,降低了系统的通讯开销,可以充分利用两端硬件环境的优势。早期的软件系统多以此作为首选设计标准。 B/S结构,即Browser/Server(浏览器/服务器)结构,是随着Internet技术的兴起,对C/S结构的一种变化或者改进的结构。在这种结构下,用户

  • git clone与git pull区别

    git clone与git pull区别原地址最近一直焦虑换工作与面试,自然面试过程中也被问到了很多问题,在一家公司中,被问到了git相关的知识。面试官提出了gitclone与gitpull有什么区别。由于自己对git的掌握情况不是特别深入,感觉瞬间被问蒙圈一样。后来,查了相关的文档,看了一些文章,自己有了一丁点的理解,觉得应该…

  • 【Jqurey EasyUI+Asp.net】—DataGrid增加、删、更改、搜

    【Jqurey EasyUI+Asp.net】—DataGrid增加、删、更改、搜

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号