ToB企服应用市场:ToB评测及商务社交产业平台

标题: 数据布局之树体系：二叉树、均衡二叉树、红黑树、AVL树、B树、B+树、最小生 [打印本页]

作者: 笑看天下无敌手 时间: 2024-8-23 15:53
标题: 数据布局之树体系：二叉树、均衡二叉树、红黑树、AVL树、B树、B+树、最小生
概述

数据布局与算法

二叉树

其中每个结点都不能有多于两个子结点：

满二叉树：若设二叉树的高度为 h h h，除第 h h h层外，其它各层(1～h-1) 的结点数都达到最大个数，末了一层都是叶子结点，且叶子结点都是从左到右依次排布，结点总数为 2 n − 1 2^n-1 2n−1
完全二叉树：全部叶子结点都在末了一层或倒数第二层，且末了一层的叶子结点在左边连续，倒数第二层的叶子结点在右边连续。和堆联系比较紧密
均衡二叉树：AVL树（区别于AVL算法），是一棵二叉排序树，且具有以下性子：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，且左右两个子树都是一棵均衡二叉树。

满二叉树

完全二叉树

关于二叉树的一些基础算法题，可参考面试+算法之二叉树(Java)。
二叉搜刮树

Binary Search Tree，BST，又称为二叉查找树、二叉排序树。
特点：任何一个结点的值都大于其左子树的全部结点的值，任何一个结点的值都小于其右子树的全部结点的值。
二叉搜刮树匀称时间复杂度可以认为是树的高度 O ( h ) O(h) O(h)。理论上，二叉搜刮树的查询、插入和删除操纵的时间复杂度均为 O ( l o g N ) O(logN) O(logN)。极端环境下，高度达到最大时，二叉搜刮树退化成链表，此时查询、插入和删除元素，时间复杂度变成 O ( N ) O(N) O(N)。
均衡二叉搜刮树

为了办理极端环境下二叉搜刮树退化成链表的问题，引入旋转操纵维护树的均衡。
Balanced Binary Search Tree（BBST，均衡二叉搜刮树），也叫Balanced Binary Tree（BBT，均衡二叉树），包罗AVL树和红黑树。
定义：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，而且左右两个子树都是一棵均衡二叉树。当时间复杂度为 O ( l o g N ) O(logN) O(logN)；
均衡，Balance，即当结点数量固定时，左右子树的高度越靠近，这棵二叉树越均衡，即高度越低。最理想的均衡就是完全二叉树/满二叉树，高度最小的二叉树。
遍历

二叉树的遍历有两种：按照结点遍历与层次遍历
结点遍历，一般递归实现：

前序遍历：遍历到一个结点后，马上输出该结点的值，并继续遍历其左右子树(根左右)
中序遍历：遍历一个结点后，将其暂存，遍历完左子树后，再输出该结点的值，然后遍历右子树(左根右)
后序遍历：遍历到一个结点后，将其暂存，遍历完左右子树后，再输出该结点的值(左右根)。

层次遍历

深度优先遍历：实际上就是上面的前序、中序和后序遍历，也就是尽大概去遍历二叉树的深度。
广度优先遍历：实际上就是一层一层的遍历，按照层次输出二叉树的各个结点。

二叉堆

二叉堆是一棵完全二叉树或是近似完全二叉树，还满足堆的特性：父结点的键值总是保持固定的序关系于任何一个子结点的键值，且每个结点的左子树和右子树都是一个二叉堆。常常被用来构造优先队列(Priority Queue),当你需要找到队列中最高优先级或者最低优先级的元素时，使用堆布局可以帮助你快速的定位元素。
布局性子：堆是一棵被完全填满的二叉树，有大概的例外是在底层，底层上的元素从左到右填入。如许的树称为完全二叉树。
分类

最大堆：父结点的键值总是大于或即是任何一个子结点的键值
最小堆：父结点的键值总是小于或即是任何一个子结点的键值

二叉堆可以用数组实现也可以用链表实现，观察上述的完全二叉树可以发现，是比较有规律的，以是完全可以使用一个数组而不需要使用链。下面用数组来表现上图所对应的堆结。
对于数组中恣意位置i的元素，其左儿子在位置2i上，右儿子在左儿子后的单位(2i+1)中，它的父亲则在位置[i/2上面]
红黑树

Red Black Tree，一种自均衡的二叉搜刮树（Self Balancing Binary Search Tree），又叫均衡二叉B树（Symmetric Binary B-tree）。
定义：红黑树是一种含有红黑结点，并能自均衡的二叉查找树。插入，删除，查找的复杂度都是 O ( l o g N ) O(logN) O(logN)
满足二叉搜刮树的性子外，还要满足如下性子：

每个结点要么是玄色，要么是红色
根结点是玄色
每个叶子结点（NIL）是玄色
每个红色结点的两个子结点肯定都是玄色
恣意一结点到每个叶子结点的路径都包罗数量雷同的黑结点
从根结点到叶子结点的最长路径不多于最短路径的长度的两倍

左倾红黑树，即红色结点都是父结点的左子树
右倾红黑树，
均衡

维持均衡的三种操纵：变色、左旋、右旋。
左旋指的是以某个结点作为支点（旋转结点），其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。不考虑结点颜色，可以看到左旋只影响旋转结点和其右子树的布局，把右子树的结点往左子树移动。
右旋指的是以某个结点作为支点（旋转结点），其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。不考虑结点颜色，可以看到右旋只影响旋转结点和其左子树的布局，把左子树的结点往右子树移动。
变色指的是结点的颜色由红变黑或由黑变红。
将左旋、右旋和变色结合起来，得到一套变更规则。
变色：如果当前结点的父结点和叔父结点是红色，那么：

把父结点和叔父结点变为玄色
把祖父结点变为红色
把指针定义到祖父结点

左旋：当前结点是右子树，且父结点是红色，叔父结点是玄色，对它的父结点左旋。
右旋：当前结点是左子树，且父结点是红色，叔父结点是玄色，那么：

把父结点变为玄色
把祖父结点变为红色
对祖父结点右旋

搜刮

由于红黑树本来就是均衡二叉搜刮树，而且搜刮也不会破坏树的均衡，以是搜刮算法也与均衡二叉搜刮树一致：

详细步骤：

从根结点开始检索，把根结点设置为当前结点
若当前结点为空，返回nil
若当前结点不为空，比较当前结点Key与搜刮Key的大小
若当前结点Key即是搜刮Key，则该Key是搜刮目标，返回当前结点
若当前结点Key大于搜刮Key，把当前结点的左子结点设置为当前结点，重复步骤2
若当前结点Key小于搜刮Key，把当前结点的右子结点设置为当前结点，重复步骤2

插入

删除

AA树

AA树是一种用于高效存储和检索有序数据的均衡树形布局，Arne Andersson教授于1993年在其论文Balanced Search Trees Made Simple中介绍，筹划的目标是减少红黑树考虑的差别环境。AA树的查找，插入和删除等操纵的时间复杂度都是 O ( l o g N ) O(logN) O(logN)。
AA树是红黑树的一种变体，与红黑树差别，AA树上的红色结点只能作为右子结点。AA树模仿2-3树，从而极大地简化维护操纵。红黑树的维护算法需要考虑七种差别的环境来精确均衡树。因为红色结点只能作为右子结点，AA树只需要考虑两种环境。
AVL树

不均衡的二叉树性能差，需要在插入、删除结点时保证其均衡，即减小树的高度，引入AVL树。AVL Tree，缩写取自G.M. Adelson-Velsky和E.M. Landis两位教授的名字。
AVL树，首先是一棵二叉搜刮树，每个结点的左右子树的高度之差的绝对值最多为1。这个高度差就叫均衡因子，Balance Factor，某结点的左右子树的高度差；显然，叶子结点的均衡因子是0。
AVL树的特点：

每个结点的均衡因子只大概是-1、0、1（如果绝对值超过1则是失衡）
每个结点的左右子树高度差不超过1
搜刮、插入、删除等操纵在匀称和最坏环境下的时间复杂度都是 O ( l o g N ) O(logN) O(logN)

如上图是一个AVL树。如下图，往这颗树里插入一个结点T：

从T往上找，它的父结点是U，U的两颗子树的高度差为1，满足AVL树的规则。再往上查找，父结点是S，S的两颗子树的高度差为1，满足AVL树的均衡规则。再往上，S的父结点是V，V的两颗子树的高度差为2，不满足规则。此时，需要一个自均衡的过程。
维持树的均衡的一种大概的旋转过程如下，其中红色结点表现旋转的轴，经过两次旋转，再次变成AVL树：

由此可总结出AVL树的缺点：

插入、删除元素时维持均衡比较复杂且代价高，树越大，写操纵占比越高（操纵无外乎读或写，写包罗插入和删除），性能影响越大
需要存储每个结点的均衡因子，增加额外的内存斲丧
结点数很多时，不够直观（还能接收）

因为这些缺点，大家们又提出各种经过优化的均衡树。
AVL算法

AVL树使用的算法，即树的自均衡旋转方式，目标是用只管少的调解次数达到适度均衡。
多叉树

也叫多路树，用于搜刮场景的树，叫做多路搜刮树，简单分类：

平常多路搜刮树
均衡多路搜刮树

B树

磁盘IO操纵的服从很低。当在大量数据存储中，查询时不能一下子将全部数据加载到内存中，只能逐一加载磁盘页，每个磁盘页对应树的结点。造成大量磁盘IO操纵（最坏环境下为树的高度）。均衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致服从低下。
为减少磁盘IO次数，必须降低树的深度：

每个结点存储多个元素
摒弃二叉树布局，采用多叉树

引出一个新的查找树布局：多路查找树，一颗均衡多路查找树，可使得数据的查找服从保证在 O ( l o g N ) O(logN) O(logN)时间复杂度。
Balanced Tree，一种均衡的多路搜刮（查找，排序）树，多用于文件系统、数据库的实现。有些资料也叫B-树（对应的英文是B-Tree），实际上是同一种数据布局。
B树的阶：全部结点的孩子结点的最大值。
一个 m m m阶（ m ≥ 2 m≥2 m≥2）的B树特点如下：

全部叶子结点都在同一层级；
每一个结点最多有 m m m个子结点；
如果根结点不是叶子结点，则它至少有两个子结点；
有 k k k个子结点的非叶子结点拥有 k − 1 k−1 k−1个键；
每一个非叶子结点（除根结点）最少有 ⌈ m / 2 ⌉ ⌈m/2⌉ ⌈m/2⌉个子结点，也就是中间结点最少有 ⌈ m / 2 ⌉ ⌈m/2⌉ ⌈m/2⌉个子结点。

两个取整：

Ceiling：向上取整，指的是取比自己大的最小整数，用数学符号 ⌈ ⌉ ⌈⌉ ⌈⌉表现；
Floor：向下取整，指的是取比自己小的最大整数，用数学符号 ⌊ ⌋ ⌊⌋ ⌊⌋表现。

假设一个结点存储的元素个数为 x x x，则如果这个结点是：

根结点： 1 ≤ x ≤ m − 1 1≤x≤m-1 1≤x≤m−1
非根结点： ⌈ m / 2 ⌉ − 1 ≤ x ≤ m − 1 ⌈m/2⌉-1≤x≤m-1 ⌈m/2⌉−1≤x≤m−1

如果有子结点，子结点个数为 y = x + 1 y=x+1 y=x+1，则如果这个结点是：

根结点： 2 ≤ y ≤ m 2≤y≤m 2≤y≤m
非根结点： ⌈ m / 2 ⌉ ≤ y ≤ m ⌈m/2⌉≤y≤m ⌈m/2⌉≤y≤m

m取值差别时：

m=3，叶子结点个数 2 ≤ y ≤ 3 2≤y≤3 2≤y≤3，可称为 ( 2 , 3 ) (2,3) (2,3)树、2-3树、3阶B树。
m=4，叶子结点个数 2 ≤ y ≤ 4 2≤y≤4 2≤y≤4，可称为 ( 2 , 4 ) (2,4) (2,4)树、2-3-4树、4阶B树。
m=5，叶子结点个数 3 ≤ y ≤ 5 3≤y≤5 3≤y≤5，可称为 ( 3 , 5 ) (3,5) (3,5)树、3-4-5树、5阶B树。

同样地，另有2-3-4-5-6树、3-4-5-6树，无穷无尽，统一都叫B树。
结论：

B树和二叉搜刮树，在逻辑上是等价的
多代结点归并，可以得到一个超等结点，且n代归并的超等结点，最多拥有 2 n 2^n 2n个子结点（至少是 2 n 2^n 2n阶B树）

应用场景：

B树重要用于文件系统及部分数据库索引，如MongoDB。而大部分关系数据库则使用B+树做索引，如MySQL；
从查找服从考虑一般要求B树的阶数 m > = 3 m>=3 m>=3；
B树算法的实行时间重要由读、写磁盘的次数来决定，故一次I/O操纵应读写尽大概多的信息。因此B-树的结点规模一般以一个磁盘页为单位。一个结点包罗的关键字及其孩子个数取决于磁盘页的大小。

操纵

B树的操纵，无非查询、插入、删除三种。
查询
插入
删除
2-3树

2-3树，是指每个具有子结点的结点（内部结点，Internal Node），要么有2个子结点和1个数据元素，要么有3个子结点和2个数据元素的自均衡的树，全部叶子结点都具有雷同的高度。即，2-3树的非叶子结点都具有两或三个分支。
空间复杂度为 O ( N ) O(N) O(N)，搜刮、插入、删除等操纵的时间复杂度都是 O ( l o g N ) O(logN) O(logN)。
2-3树把数据存储在叫做元素的单独单位中，元素组合成结点。有2结点和3结点两种。
2结点：包罗1个元素和2个子结点

3结点：包罗2个元素和3个子结点

2–3树和AA树是等距同构的，意味着它们是同一种数据布局。对于每个2–3树，都至少存在1种AA树和它的元素排列是雷同的。2–3树是均衡树，意味着右边，左边，中间的子树的元素数量都是雷同或靠近的。
一棵树T为2–3树的三种环境：

T为空：即T不包罗任何结点；
T为拥有数据元素a的2结点。若T的左子结点为L、右子结点为R，则：
- L和R是等高的2–3树；
- a大于L中的全部数据元素；
- a小于即是R中的全部数据元素。
T为拥有数据元素a和b的3结点，且 a < b a<b a<b。若T的左子结点为L、中子结点为M、右子结点为R，则：
- L、M、和R是等高的2–3树；
- a大于L中的全部数据元素，且小于即是M中的全部数据元素；
- b大于M中的全部数据元素，且小于即是R中的全部数据元素。

上面这颗树就是一个2-3树。此时，如果要插入一个元素K，它会先找到I J这个结点；插入元素K，形成暂时结点I J K，不符合2-3树的规则。
差别于AVL树，不满足树的规则时，需要对树进行旋转，2-3树则需要进行分裂操纵。
J往上移，F H这个结点变成F H J，也不符合2-3树的规则。继续上移H，根结点变为D H。同时，上移的过程中，子结点也要相应的分裂，过程大致如下：

图片来自于红黑树。
在上面自均衡的过程中，出现一种结点，它具有四个子结点和三个数据元素，即4结点。如果4结点允许存在，则引出另一种树：2-3-4树。
另外，B树的均衡过程叫分裂，相比于AVL树的旋转，更直观易懂，服从更高。
2-3-4树

与2-3树雷同，多了一种4结点：包罗3个元素和4个子结点。

2-3-4树是有序的：每个元素必须大于或即是它左边的和它的左子树中的任何其他元素。每个子结点因此成为由它的左和右元素界定的一个区间。
2-3-4树的空间复杂度为 O ( N ) O(N) O(N)，搜刮、插入、删除等操纵的时间复杂度都是 O ( l o g N ) O(logN) O(logN)。
2-3-4树在多数编程语言中实现起来相对困难，因为在树上的操纵涉及大量特殊环境。红黑树实现起来更简单一些，可用它来替代。
2-3-4树是红黑树的一种等同，这意味着它们是等价的数据布局。对于每个2-3-4树，都存在着至少一个数据元素是雷同序次的红黑树。在2-3-4树上的插入和删除操纵也等价于在红黑树中的颜色翻转和旋转。这使得它成为理解红黑树背后逻辑的紧张工具。
B+树

B+树是B树的变种，但差别资料（以及实现里）中B+树的定义各有差别，其差异在于结点中关键字个数和孩子结点个数。
B+树的特点：

每个结点中子结点的个数不能超过N，也不能小于 N / 2 N/2 N/2（不然会造成页分裂或页归并）
根结点的子结点个数可以不超过 m / 2 m/2 m/2
m叉树只存储索引，并不真正存储数据，只有末了一行的叶子结点存储行数据
通过链表将叶子结点串联在一起，方便按区间查找

这种在叶结点存放一整行记录的索引被称为聚簇索引，其他的就称为非聚簇索引。
一个 m m m阶的B+树具有如下几个特性：

有 k k k个子树的中间结点包罗有k个元素（B树中是 k − 1 k-1 k−1个元素），每个元素不生存数据，只用来索引，全部数据都生存在叶子结点；
全部的叶子结点中包罗全部元素的信息，及指向含这些元素记录的指针，且叶子结点自己依关键字的大小自小而大顺序链接；
全部的中间结点元素都同时存在于子结点，在子结点元素中是最大（或最小）元素

B+树通常有两个指针，一个指向根结点，另一个指向关键字最小的叶子结点。对于B+树进行查找有两种算法：一种是从最小关键字起顺序查找，另一种是从根结点开始，进行随机查找。
对比B树

和B树一样，雷同于二叉查找树。起始于根结点，自顶向下遍历树，选择其分离值在要查找值的恣意一边的子指针。在结点内部典型的使用是二分查找来确定这个位置。
区别：

B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点逐个扫一遍就完；
B+树支持区间查询(Range Query)，而B树不支持。数据库选用B+树的最重要原因；
B+树中间结点没有卫星数据（索引元素所指向的数据记录），只有索引，而B树每个结点中的每个关键字都有卫星数据；即，同样大小磁盘页可以容纳更多结点元素，数据量雷同时，B+树更加矮胖，IO操纵更少
因卫星数据的差别，导致查询过程也差别；B树的查找只需找到匹配元素即可，最好环境下查找到根结点，最坏环境下查找到叶子结点，性能很不稳定；B+树每次必须查找到叶子结点，性能稳定
在范围查询方面，B+树的上风更加明显
B树的范围查找需要不绝依靠中序遍历。首先二分查找到范围下限，再不绝通过中序遍历，直到查找到范围的上限即可。整个过程比较耗时。B+树的范围查找则简单很多。首先通过二分查找，找到范围下限，然后通过叶子结点的链表顺序遍历，直至找到上限即可，整个过程更简单，服从也更高。

面试题

为啥索引常用B+树作为底层的数据布局？
除了B+树索引，另有什么索引？
为啥保举自增ID作为主键，自建主键不行吗？
什么是页分裂，页归并？
怎么根据索引查找行记录？

B*树

B+树的变体，区别：

在B+树的非根和非叶子结点再增加指向兄弟的指针；
B*树定义非叶子结点关键字个数至少为 ( 2 / 3 ) ∗ M (2/3)*M (2/3)∗M，即块的最低使用率为2/3，优于B+树的1/2；
分裂
- B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，末了在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，以是它不需要指向兄弟的指针；
- B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，末了修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，末了在父结点增加新结点的指针；
B*树分配新结点的概率比B+树要低，空间使用率更高；

最小天生树

Minimum Spanning Tree，MST，最小权重天生树，是一副连通加权无向图中一棵权值最小的天生树。
哈夫曼树

Huffman Tree，最优二叉树，是一种带权路径长度最短的二叉树。树的带权路径长度，就是树中全部的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为 W P L = ( W 1 ∗ L 1 + W 2 ∗ L 2 + W 3 ∗ L 3 + . . . + W n ∗ L n ) WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln) WPL=(W1∗L1+W2∗L2+W3∗L3+...+Wn∗Ln)， N N N个权值 W i ( i = 1 , 2 , . . . , n ) Wi(i=1,2,...,n) Wi(i=1,2,...,n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为 L i ( i = 1 , 2 , . . . , n ) Li(i=1,2,...,n) Li(i=1,2,...,n)。可证实霍夫曼树的WPL是最小的。
哈夫曼编码就是哈夫曼树的应用。
决策树

Decision Tree，也叫判断树，是一个雷同于流程图的树布局：其中，每个内部结点表如今一个属性上的测试，每个分支代表一个属性输出，而每个树叶结点代表类或类分布。树的最顶层是根结点。
构造决策树的过程叫做决策树算法，常用于呆板学习中的分类。
优点：直观，便于理解，小规模数据集有效
缺点：

处置处罚连续变量不好
类别较多时，错误增加的比较快

Trie树与Radix树

参考Trie树、Radix树。
LSM树

Log-Structured Merge-Tree。适用于写入密集型的数据库系统，如LevelDB和RocksDB。
上风：提供非常高的写入性能和批处置处罚能力，支持对数据的压缩。
劣势：因为涉及多层查找和归并操纵，读取性能不如其他数据布局。
后缀树

Suffix Tree，用于字符串搜刮、生物信息学等范畴。
上风：可以快速办理多种字符串相干的问题，如查找子字符串出现的位置、查找最长重复子字符串等。
劣势：空间占用较大，构建过程复杂且耗时。
R树

R-Tree，适用于空间数据库中索引多维空间数据，如地理信息系统(GIS, Geographic Information System)。
上风：支持多维范围查询和最邻近搜刮，适合存储空间数据。
劣势：更新本钱高，查询性能依靠于数据分布。
对比

图片来源：https://bytebytego.com/
参考

全面分析二叉树
红黑树
面试必知的红黑树
面试必知B+树
最小天生树
红黑树
AA树

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)