相关树及性质

二叉树

性质：

第 n 层最多有 2^n-1 个节点
深度为 k 的二叉树最多有 2^k - 1 个节点（满二叉树）
对于任何一颗二叉树，如果其叶节点有 n₀ 个，度为2的非叶节点有 n₂个，则有 n₀ = n₂ + 1
n个节点的完全二叉树的深度为 ⌊log₂n⌋+1
如果有一颗有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i（1 $\leqslant$ i $\leqslant$ n）有
1. 如果i=1，则节点i是二叉树的根，无双亲，如果i>1，则其双亲节点为 ⌈i/2⌉
2. 如果2i>n，则节点i没有左孩子，否则其左孩子为2i
3. 如果2i+1>n，则节点没有右孩子，否则右孩子为2i+1

image

满二叉树

节点的度都是2且叶子节点都在同一层次上
是一种特殊的二叉树

完全二叉树

与满二叉树深度相同，并且编号一一对应的二叉树

性质：

若 i $\leqslant$ ⌊n/2⌋，则结点i为分支结点，否则为叶子结点
最下面层的叶节点一定出现在左边
深度为k的完全二叉树，其最少的结点数=深度为 k-1 的满二叉树的结点数+1，即 2^k-1个；其最多结点数=深度为k的满二叉树的结点数，即 2^k-1

顺序存储完全二叉树A[1,...,n]，当 i $\leqslant$ (n-1)/2 时，结点A[i]的右孩子是结点 A[2i+1]

哈夫曼树（最优二叉树）

性质：

有n个叶子结点
没有度为1的结点
总的结点数为2n-1
深度 $\leqslant$ n-1
形态不唯一
要使一棵二叉树的带权路径长度最小，必须使权值越大的叶子节点越靠近根节点，权值越小的节点越远离根节点

利用哈夫曼树可构造前缀编码

最小生成树

在连通网的所有生成树中，所有边的代价和最小的生成树

看谁代价最小，来 PK 呀！P-prime, K-kruskal

prim算法
算法思想：从图中任取一个顶点，把它当成一棵树，然后从这棵树的顶点相邻的边中选取权值最小的边，并把这条边相邻的顶点并入树中，此时得到一颗有两个顶点的树，然后继续从这棵树的两个顶点相邻的边中选取一条最短的边，将其和相邻顶点再次并入树中，重复操作直到所有顶点都被并入树中。

prime算法图解
kruskal算法
算法思想：每次从所有边中选出权值最小的边，将其并入树中，重复操作直到所有顶点都被并入树中。

kruskal算法图解

图片来源：https://blog.csdn.net/luoshixian099/article/details/51908175

二叉排序树（二叉查找树）

性质：空树/如果左子树不为空，则左子树的所有结点的值均小于根节点；如果右子树不为空，则右子树的所有结点均大于根节点；左右子树分别也是二叉排序树。中序遍历会得到一个有序序列。

既拥有类似于折半查找的特性，又采用了链表做存储结构，它是动态查找表的一种适宜表示。其查询效率高于链表结构。

二叉排序树

AVL树（平衡二叉树）

它是二叉排序树的一种改进，由于树的高度越小，查找效率越高，所以尽可能的保持左右子树高度平衡，会使得树的高度达到最小。

性质：左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。即就是平衡因子只会取 -1，0 ，1，因此此处的重点不断的执行是平衡调整。

基于二分法的策咯提高数据查找速度的二叉树的数据结构。

【例】若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为20

B树（多路平衡查找树）

B树（B-tree）是在AVL树基础上的一种升级，它是各个节点平衡因子都为0的多路平衡查找树。
B树一开始是针对机械磁盘而设计的，因为机械磁盘的磁头跳转消耗的时间比较多，为了减少跳转的次数，所以设计了B-Tree。B树的目标是在 O(logn) 时间复杂度内，完成一些动态操作。这种数据结构多用于实现数据库索引。红黑二叉树的时间复杂度也是 O(logn) ，但是B树可以比红黑二叉树存储更多的节点。属于查找的应用。

一颗3阶B树

一颗4阶B树

一颗 m 阶的B树，或为空树，或为满足下列特性的 m 叉树：

（1）树中的每个结点 $\color{red}{至多有 m 棵子树}$ ；

（2）若 $\color{red}{根结点}$ 不是叶子结点，则 $\color{red}{至少有1个关键字}$ ， $\color{red}{至少有2颗子树}$ ； $\color{red}{至多有 m-1 个关键字}$ ， $\color{red}{至多有 m 颗子树}$ ；

（3）除根结点外， $\color{red}{非叶结点至少有 ⌈m/2⌉-1 个关键字}$ ， $\color{red}{至少有 ⌈m/2⌉ 颗子树}$ ； $\color{red}{至多有 m-1 个关键字}$ ， $\color{red}{至多有 m 颗子树}$ ；

【例】在一棵高度为2的5阶B树中，所含关键字的个数最少是5。因为根结点关键字是5个的时候会产生分裂，高度正好变为2

（4）n个结点的m阶B树的 $\color{red}{高度}$ 范围：
$log_m(n+1) \leqslant h \leqslant log_{⌈m/2⌉}((n+1)/2)+1$

（5）n个非叶结点的m阶B树 $\color{red}{至少}$ 包含的关键字个数： $\color{red}{ (n-1)(⌈m/2⌉-1 )+1}$

（6）所有叶节点都在同一层

B树中的叶结点又叫外部结点，类似于查找判定树的查找失败结点，实际上这些点并不存在。

结合下例理解：

一棵5阶B树

一棵5阶B树特点总结

B树的关键字插入和删除操作：

插入操作涉及到结点分裂的问题

image.png
删除操作涉及到结点合并的问题

$\color{HotPink}{需要满足删除后的结点关键字个数 \geq ⌈m/2⌉-1 }$

情况一： 被删关键字是非终端结点，则先用其前驱或后继结点替代它，使得被删结点落到终端结点，然后走情况二；

先用前驱结点替代被删结点

情况二： 被删关键字在终端结点
step1. 结点关键字个数 $\geqslant$ ⌈m/2⌉，直接删除，否则走step2
step2. 兄弟够借：被删关键字所在的结点关键字个数为⌈m/2⌉-1 ，其左/右兄弟结点关键字个数 $\geqslant$ ⌈m/2⌉，此时采用“父子换位法“执行删除操作；否则走step3
step3. 兄弟不够借，被删关键字所在的结点关键字个数为⌈m/2⌉-1 ，其左/右兄弟结点关键字个数也是⌈m/2⌉-1，则需将左/右兄弟结点关键字与父级结点关键字进行合并

image.png

B+树

B+树是应数据库所需而生的一种B树的变形树，相对于B树来说B+树更充分的利用了节点的空间，磁盘读写代价更低，查询速度更加稳定，其速度完全接近于二分法查找。适应于操作系统中的文件索引和数据库索引。B+树既能顺序查找，也能索引查找。

一颗4阶B+树

一棵m阶的B+树需满足下列条件：

（1）每个分支结点最多有 m 颗子树（孩子结点）；

（2）根结点(若不是叶结点)至少有1个关键字，2颗子树，至多m个关键字，m颗子树；其它非叶结点至少有⌈m/2⌉个关键字，⌈m/2⌉颗子树，至多有m个关键字，m颗子树；

（3）结点的子树个数与关键字个数相等；

（4）所有叶结点包含全部关键字以及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。

（5）所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针；

一颗m阶的B+树与B树的差异在于：

（1）在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一颗子树；在B树中，具有n个关键字的结点含有n+1颗子树

（2）在B+树中，每个结点（非根内部结点）的关键字个数 n 的范围是⌈m/2⌉ $\leqslant$ n $\leqslant$ m（根节点：1 $\leqslant$ n $\leqslant$ m）；在B树，每个结点（非根内部结点）的关键字个数n的范围是⌈m/2⌉-1 $\leqslant$ n $\leqslant$ m - 1（根节点：1 $\leqslant$ n $\leqslant$ m - 1）

（3）在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

（4）在B+树中，所有叶子结点中包含了全部关键字的信息，以及指向这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；即在非叶结点中出现的关键字也会出现在叶节点；而在B树中，叶结点包含的关键字和其它结点包含的关键字是不重复的。

红黑树

红黑树（Red Black Tree）是一种自平衡二叉查找树，它是一种特化的AVL树，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。若一棵二叉查找树是红黑树，则它的任一子树必为红黑树。

性质：

（1）节点是红色或黑色；

（2）根节点是黑色；

（3）所有叶子都是黑色；

（4）每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）

（5）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点；

应用：红黑树已广泛应用Linux 的进程管理、内存管理，设备驱动及虚拟内存跟踪等一系列场景中。

键树（数字查找树）

是一颗度 $\geqslant$ 2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。