数据结构-树

先看一张表:


树的种类

没想到竟然有这么多树,相对而言,重要一点的就是二叉树,AVL树,红黑树,B树,B+树,咱们就从简单的到深入的慢慢讲

一、二叉树

二叉树是每个节点最多有两个子节点的树结构,二叉树里面还分:
满二叉树:顾名思义,每一层都是满的,因此深度为k的满二叉树的节点数为2^k-1个
完全二叉树:完全二叉树为除了最后一层都是满的,并且最后一层节点都集中在左边的树
一个节点的子节点数为节点的度,对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1
二叉树理论上是二分法的所以查找效率为logN,但是因为不是平衡的,所以有可能在更新过程中变成是单链的,效率会降低为N
对于二叉树的遍历,有前序中序后序,使用递归法非常容易理解但是调用栈太深了,容易出现效率太低甚至溢出的情况,因此可以采用非递归的方法,非递归其实也是用到了栈来存储一路走下来的节点,中序遍历最简单,后续遍历会难一些,如果需要可以留言,我把思路和代码写出来。

二、AVL树

AVL树即平衡二叉树,又叫二叉排序树,之所以是平衡的,是因为它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是平衡的。
平衡二叉树的查找效率一定是logN的,因此适合用来搜索。
在插入和删除的时候要想保持一颗树的平衡性不是那么容易的,需要先从上往下遍历找到位置,插入的时候还需要在从下往上遍历使它保持平衡,保持一颗树平衡的方法有左旋和右旋,双向旋转无非就是先左后右或者先右后左的组合。
那么如何知道它不平衡了呢,平衡二叉树引入了一个平衡因子,其实就是该节点左右子树的高度差,该因子的值为0,-1,1视为平衡,其他时候为不平衡,就需要做旋转操作。

三、红黑树

红黑树也是一种自平衡二叉树,它的定义比较复杂:
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
性质5.每个叶子的节点都是黑色的null节点
保持红黑树的平衡挺蛋疼的,需要旋转加变色的配合,旋转通过AVL树的练习倒是容易理解,但是变色因为要同时满足5个性质,所以emmmm

四、B树

B树又称B-树,它已经不是二叉树了,可以称为m叉树,m为节点的最大子节点个数,m>=3,非根非叶子节点至少有m/2个(向上取整)分支。如果一个结点有n-1个关键字,那么该结点有n个分支。
B树的节点中包含关键字和数据,这是和B+树,查找的关键字如果等于非叶子的关键字那么就可以返回了。
B树的插入有可能导致个数超过限制,因此通过分裂操作来保持满足规则,同理,删除结点的时候导致个数小于m/2,可以通过合并来保持。

五、B+树

对标B树,最大的特点就是信息只保存在叶子节点中,中间节点不带数据,只作为索引,并且叶子节点包含了全部关键字,父节点的关键字在子结点中为该子树的最大值。因此B+树要想得到数据,必须要查找到叶子节点才能返回。
B+树的叶子节点同时还形成一个有序列表。

B树和B+树的区别:

1、B+树的中间节点不带数据,因此能存储更多内容,所以B+树更加的矮胖,查询的IO次数就会更少
2、所有查询都要查找到叶子节点,查询性能稳定。
3、所有叶子节点形成有序链表,便于范围查询。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 目录 1、什么是树 2、相关术语 3、二叉树 3.1、二叉树的类型 3.2、二叉树的性质 3.3、二叉树的结构 3...
    我哈啊哈啊哈阅读 2,588评论 0 10
  • 树(Tree)的基本概念树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称...
    意识流丶阅读 52,898评论 0 30
  • 树是非线性存储结构,存储的是具有“一对多”关系的数据元素的集合。 使用树结构存储的集合 {A,B,C,D,E,F,...
    飞扬code阅读 4,808评论 0 2
  • 一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这...
    Winterfell_Z阅读 6,006评论 0 13
  • 这篇文章收录在我的 Github 上 algorithms-tutorial,另外记录了些算法题解,感兴趣的可以看...
    Lindz阅读 15,343评论 4 15