上一篇【数据结构与算法】四、链表相关算法题

1、树 Tree

2.1、树的定义和特点

2.1.1、每个节点有零个或多个子节点；

2.1.2、没有父节点的节点称为根节点；

2.1.3、每一个非根节点有且只有一个父节点；

2.1.4、除了根节点外，每个子节点可以分为多个不相交的子树。

2.2、二叉树

2.2.1、二叉树的含义

就是单向链表中的节点中持有两个指向下一个引用的变量，且下一个引用不能去指向原有树中出现过的元素；如果有往回指向的子节点引用那么在查询时就会往回检索，那么这个数据结构就是树。

2.2.2、二叉树的每个节点最多只能有两个子节点；

2.2.3、增加、删除、修改的时间复杂度均为O(1)，查询的时间复杂度为O(n)，完全和链表一样；

2.3、二叉搜索树（又：二叉查找树，二叉排序树）

2.3.1、在二叉树定义的基础上，附加一条对所有节点其左子树所有的节点必须小于根节点，右子树所有的节点必须大于根节点。

2.3.2、因为其在增加删除、修改的时候都需要先查询一次应该存放的位置，所以其增加、删除、修改和查询的时间复杂度均为O(log(n))、最坏情况为：均为O(n)。

2.4、AVL树（平衡二叉树）

2.4.1、在二叉搜索树的基础上，附加一条任何节点的两棵子树的高度差不大于1，即左右子树的高度差必须<=1;

2.4.2、由于需要维护平衡的条件，所以每当增加、删除、修改时需要对整个二叉树进行旋转以达到平衡的目的，因此每次进行增加、删除和修改后对树的结构调整较大，较为耗时。

2.4.3、增加、删除、修改和查询的时间复杂度均为O(log(n))，最坏情况也为：均为O(log(n))。

2.5、红黑树

2.5.1、红黑树的五个特性

在二叉搜索树的基础上，附加：

• 1、每个节点有红黑之分，非红即黑，非黑即红；
• 2、根节点必须为黑色；
• 3、如果一个节点为红色，那么它的子节点肯定是黑色的，即：两个连的节点不会同色，必须是红黑交替的形式出现；
• 4、叶子节点都是黑色；
• 5、从任一节点到其子孙节点的路径含有相同数目的黑色节点；

2.5.2、为了解决AVL树需要维护平衡的条件而导致的每次进行增加、删除和修改后对树的结构调整较大，较为耗时的情况，所以红黑树的平衡条件就没有那么的苛刻，这样既降低了增删改对树的结构的调整的耗时，但是也是相对来说是平衡的，所以其也需要旋转。

2.5.3、红黑树的旋转

为了维护红黑树在增加或者删除节点后的平衡，所以就需要在增加或者删除节点后进行红黑树的旋转

• 1、变色：由红变黑或者由黑变红；
• 2、左旋：即逆时针旋转，找到需要旋转的点，然后将其右节点的左子树作为自己的右子树，然后让其右节点代替自己的位置；
• 3、右旋：即顺时针旋转，找到需要旋转的点，然后将其左节点的右子树作为自己的左子树，然后让其左节点代替自己的位置；

2.5.4、红黑树旋转时的细节

1、任何新插入的节点都默认为红节点；

2、触发变色的条件：当前节点的父节点为红色，且其叔叔也为红色；

3、变色的具体步骤：

• ①把父节点变为黑色
• ②把叔叔节点变为黑色
• ③把爷爷节点变为红色

4、触发左旋的条件：当前节点的父节点为红色，且叔叔节点为黑色，且当前节点是右子树；

如果父节点为爷爷节点的左子节点，旋转的点就为当前节点的父节点；
如果父节点为爷爷节点的右子节点，旋转的点就为当前节点的爷爷节点；

5、左旋的具体步骤：

如果父节点为爷爷节点的右子节点需要增加变色操作：

• 1、把父节点变为黑色
• 2、把爷爷节点变为红色
  参照2.5.3的2
  

6、触发右旋的条件：当前节点的父节点为红色，且叔叔节点为黑色，且当前节点是左子树；

如果父节点为爷爷节点的左子节点，旋转的点就为当前节点的爷爷节点；
如果父节点为爷爷节点的右子节点，旋转的点就为当前节点的父节点；

7、右旋的具体步骤：

如果父节点为爷爷节点的左子节点需要增加变色操作：

• 1、把父节点变为黑色
• 2、把爷爷节点变为红色
• 3、具体参照2.5.3的
• 

具体事例：

2.5.6、增加、删除、修改和查询的时间复杂度均为O(log(n))，最坏情况也为：均为O(log(n))。

2.5、B-Tree 平衡多路查找树

注意这里的B-Tree，并不是B减Tree，- 只是一个连接符号，人们经常这么写而已，实际上是B-Tree就是指B Tree（B树）；

每个节点最大可以存放（路数-1）个关键字信息；
每个节点最大可以有（路数）个分支；

以上是3路的B-Tree数据结构在索引中的示意图；
数据查找方式：
X < 17 --> P1
X = 17 命中
17< X < 35 --> P2
X = 35 命中
X > 35 --> P3
模拟查找关键字29的过程：
根据根节点找到磁盘块1，读入内存，（磁盘I/O操作第1次）（根节点常驻内存）
比较关键字29所在区间（17,35），找到磁盘块1的指针P2；
根据P2指针找到磁盘块3，读入内存，（磁盘I/O操作第2次）
比较关键字29所在区间（26,30），找到磁盘块3的指针P2；
根据P2指针找到磁盘块8，读入内存，（磁盘I/O操作第3次）
在磁盘块8中的关键字列表中找到关键字29；

分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率，而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素，B-Tree相对于AVL Tree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率

2.6、B+Tree 改进版平衡多路查找树

MySQL的InnoDB存储引擎采用的就是B+Tree数据结构实现其索引结构；

2.7 B-Tree 与 B+Tree有什么区别？

B+Tree是基于B-Tree的，大部分数据结构相同，但也有一些区别：

• 1、B+Tree非叶节点不保存数据信息，只保存关键字和子节点的引用；
• 2、B+Tree关键字的数据保存在叶子节点中；
• 3、B+Tree叶子节点是顺序排列的，并且相邻节点具有顺序引用关系；
• 4、B+Tree由于非叶子节点不存储数据，那么每个节点就可以存储更多的元素，树的层级更少所以查询数据更快，所有数据都存在叶子节点，所以每次查找的次数都相同因而查询速度更稳定；
• 5、B+Tree通常有两个指针，一个指向根结点，另一个指向关键字最小的叶子结点，因此可以对B+Tree进行两种查找运算：一种是对于关键字的范围查找和分页查找，另一种是从根节点开始，进行随机查找；

2.8 举例说明：B+Tree的优势

B＋树的查找和Ｂ树一样，类似于二叉查找树，从根节点出发自顶向下遍历树，在节点内部使用二分查找来确定走哪一边的指针；

（1）不同的是，Ｂ＋树中间非叶子节点没有数据（索引元素所指向的数据记录），只有索引，而Ｂ树每个结点中的每个关键字都有数据，这样使得同样大小的磁盘页可以容纳更多节点元素，在相同数据量下（1kw），Ｂ＋树更加“矮胖”，ＩＯ操作更少；

B树的数据：

B+树的数据：

（2）因为数据的不同，导致查询过程也不同，Ｂ树的查找只需找到匹配元素即可，最好情况下查找到根节点，最坏情况下查找到叶子结点，所以性能很不稳定，而Ｂ＋树每次必须查找到叶子结点，性能稳定；

（3）在范围查询方面，B+树的优势更加明显，B树的范围查找需要不断依赖中序遍历。

首先二分查找到范围下限，在不断通过中序遍历，直到查找到范围的上限，整个过程比较耗时；
而B+树的范围查找则简单许多，首先通过二分查找，找到范围下限，然后同过叶子结点的链表顺序遍历，直至找到上限即可，效率更高；
例如：同样查找范围 [3-11]，两者的查询过程如下：

• B树的查找过程：
  
• B+树的查找过程：
  -在这里插入图片描述