文档章节

数据结构(树)

潦草的犀牛
 潦草的犀牛
发布于 2019/12/14 21:44
字数 1550
阅读 11
收藏 0

树:

    树是n个结点的有限集合,有且仅有一个根结点,其余结点可分为m个根结点的子树。

    度:

        指的是一个节点拥有子节点的个数。如二叉树的节点的最大度为2。

    高度/深度:

        数的层数,根节点为第一层,依次类推。

    叶子节点:

        度为0的节点,即没有子节点的节点。

 

二叉树:

    在二叉树中每个节点最多有两个子节点,一般称为左子节点和右子节点(或左孩子和右孩子)

    前序遍历(前根遍历):——>左——>右

    中序遍历(中根遍历):左——>——>右

    后序遍历(后根遍历):左——>右——>

 

满二叉树:

    在一棵二叉树中,如果所有分支结点都有左孩子和右孩子结点,并且叶子结点都集中在二叉树的最下层,这样的树叫做满二叉树

    高度为h,由2^h-1个节点构成的二叉树。

完全二叉树:

    二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树),第 h 层所有的结点都连续集中在最左边。

 

二叉查找树(BST):

    又称二叉排序树,亦称二叉搜索树(Binary Search Tree)。

    定义:

    一棵空树,或者是具有下列性质的二叉树:

    1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;

    2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;

    3)左、右子树也分别为二叉排序树;

    4)没有键值相等的结点。

    最坏情况,会退化为一条链表:

 

平衡二叉树(AVL):

    AVL树本质还是一棵二叉查找树,只是在其基础上增加了“平衡”的要求。

    定义: 

    它或者是一颗空树,或者具有以下性质的二叉排序树:

    它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1。

     二叉树,它的搜索时间复杂度为O(log2N),所以它的搜索效率和树的深度有关。

    由于普通的二叉查找树会容易失去”平衡“,极端情况下,二叉查找树会退化成线性的链表,导致插入和查找的复杂度下降到 O(n) 。

    通过平衡二叉树,我们解决了二叉查找树的缺点。对于有 n 个节点的平衡树,最坏的查找时间复杂度也为 O(logn)

    插入、删除结点,可能会破坏其二叉平衡树的平衡,此时需要通过 左旋、右旋等操作使之重新平衡。

 

红黑树:

    定义:

    1)具有二叉查找树的特点。

    2)根节点是黑色的;

    3)每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存数据。

    4)如果一个节点是红色的,则它的子节点必须是黑色的,也就是说,红色节点是被黑色节点隔开的。

    5)每个节点,从该节点到达其可达的叶子节点是所有路径,都包含相同数目的黑色节点。

    虽然平衡树解决了二叉查找树退化为近似链表的缺点,能够把查找时间控制在 O(logn),不过却不是最佳的,因为平衡树要求每个节点的左子树和右子树的高度差至多等于1。这个要求实在是太严了,导致每次进行插入/删除节点的时候,几乎都会破坏该规则,进而需要通过左旋右旋来进行调整,使之再次成为一颗符合要求的平衡树。

    显然,如果在那种插入、删除很频繁的场景中,平衡树需要频繁着进行调整,这会使平衡树的性能大打折扣,为了解决这个问题,于是有了红黑树。与平衡树不同的是,红黑树在插入、删除等操作,不会像平衡树那样,频繁破坏红黑树规则,所以不需要频繁调整,这也是我们为什么大多数情况下使用红黑树的原因。不过,单单在查找方面的效率的话,平衡树比红黑树快。

    平衡树是为了解决二叉查找树退化为链表的情况,而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。

 

B-树、B+树、B*树

    二叉树,它的搜索时间复杂度为O(log2N),所以它的搜索效率和树的深度有关,如果要提高查询速度,那么就要降低树的深度。要降低树的深度,很自然的方法就是采用多叉树,再结合平衡二叉树的思想,我们可以构建一个平衡多叉树结构,然后就可以在上面构建平衡多路查找算法,提高大数据量下的搜索效率。

    B树(balanced tree),平衡多路搜索树。相关分析参考:mysql索引数据结构

 

    B+树 与 红黑树 应用场景:

        1.红黑树多用在内部排序,即全放在内存中;B树多用在内存里放不下,大部分数据存储在外存时。因为B树层数少,因此可以确保每次操作,读取磁盘的次数尽可能的少。

        2.在数据较小,可以完全放到内存中时,红黑树的时间复杂度比B树低。反之,数据量较大,外存中占主要部分时,B树因其读磁盘次数少,而具有更快的速度。

© 著作权归作者所有

潦草的犀牛
粉丝 16
博文 296
码字总数 593250
作品 0
虹口
程序员
私信 提问
目录帖:​​​​​​​浅谈算法和数据结构

浅谈算法和数据结构: 一 栈和队列 浅谈算法和数据结构: 二 基本排序算法 浅谈算法和数据结构: 三 合并排序 浅谈算法和数据结构: 四 快速排序 浅谈算法和数据结构: 五 优先级队列与堆排序 浅谈...

安小乐
2018/09/04
73
0
数据结构之Tree

数据结构和数据的关系,就如同水和盛水的器皿一样, 比如: 消防员会选择用消防水栓装水,原因是他需要处理高压大量的水,解救火灾;茶馆的伙计会用茶壶, 茶壶受热均匀,煮出的茶才韵味无穷...

晨曦之光
2012/03/09
216
0
应对程序员面试,你必须知道的八大数据结构

瑞士计算机科学家Niklaus Wirth在1976年写了一本书,名为《算法+数据结构=编程》。 40多年后,这个等式仍被奉为真理。这就是为什么在面试过程中,需要考察软件工程师对数据结构的理解。 几乎...

技术小能手
2018/08/29
0
0
【从蛋壳到满天飞】JS 数据结构解析和算法实现-二分搜索树(一)

前言 【从蛋壳到满天飞】JS 数据结构解析和算法实现,全部文章大概的内容如下: Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜...

哎哟迪奥
2019/03/24
0
0
PostgreSQL 源码解读(20)- 查询语句#5(查询树Query详解)

本文简单介绍了PG查询优化重写后生成的查询树Query的详细结构,查询重写优化的输入是上一节介绍的解析树Parsetree。 一、查询树结构 查询语句: 跟踪分析: Query->rtable Query->jointree ...

EthanHe
2018/08/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

LeetCode.6.Z字形变换

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时,排列如下: L C I R E T O E S I I G E D H N 之后,你的输出需...

tedzheng
19分钟前
21
0
使用postman测试接口,解决Session共享问题

问题: 在做登录模块时,使用Postman做接口测试,发现session不能共享问题:第一次请求将系统随机生成验证码放入Session中,第二次请求想要获取系统生成的验证码,但是取到的值为null,因此无...

code-ortaerc
51分钟前
67
0
从Maven存储库获取源JAR

有谁知道您是否可以在Maven存储库中找到源JAR? #1楼 如果您使用的是eclipse,则还可以打开“首选项”>“ Maven”并选择“下载Artifact源”,这将使pom.xml完整无缺,并将源或Java文档(如果...

技术盛宴
59分钟前
60
0
CentOS 7 SSH连接超时自动断开解决方案

用SSH登录到Linux的时候,由于默认的连接超时时间很短,经常断开。可以修改配置文件调整服务器端向客户端请求消息的时间间隔,解决自动断开的问题。 编辑/etc/ssh/sshd_config 找到 #ClientA...

matrixchan
今天
53
0
非典期间的一段回忆

最近的新型肺炎病毒甚嚣尘上,已经成了大众最瞩目的事件,整个国家层面反应也算迅速,毕竟我们是一个十几亿人口的国家。 公众号的读者和我分享了一个一段03年非典期间的故事,感慨颇深。经原...

王知无
今天
65
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部