相关树

2020-08-27 本文已影响0人 vavid

二叉树

性质：

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

image

满二叉树

节点的度都是2且叶子节点都在同一层次上

完全二叉树

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

性质： ⌈59/60⌉

若 i<=⌊n/2⌋，则结点i为分支结点，否则为叶子结点

最下面层的叶节点一定出现在左边

深度为k的完全二叉树，其最少的结点数=深度为k的满二叉树的结点数+1=2^(k-1)-1+1=2(k-1);其最多结点数=深度为k的满二叉树的结点数=2^k-1

k与结点数目n之间的关系可以根据二叉树的性质4得出 k=1+2^k

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

最优二叉树（哈夫曼树）

性质：

有n个叶子结点

没有度为1的结点

总的结点数为2n-1

深度<=n-1

形态不唯一

最小生成树

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

prim算法

image.png

kruskal算法

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

性质：空树/如果左子树不为空，则左子树的所有结点的值均小于根节点；如果右子树不为空，则右子树的所有结点均大于根节点；左右字数分别也是二叉排序树。

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

构造过程：

平衡二叉树（AVL树）

性质：左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

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

B树

B树一开始是针对机械磁盘而设计的，因为机械磁盘的磁头跳转消耗的时间比较多，为了减少跳转的次数，所以设计了B-Tree。B树的目标是在 O(logn) 时间复杂度内，完成一些动态操作。这种数据结构多用于实现数据库索引。红黑二叉树的时间复杂度也是 O(logn) ，但是B树可以比红黑二叉树存储更多的节点。

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

（1）树中的每个结点至多有 m 棵子树；

（2）若根结点不是叶子结点，则至少有两颗子树，至多有 m 颗子树；

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

（4）根结点至少含有1个关键字，除根结点外，非叶结点至少有 ⌈m/2⌉ 颗子树，至少有 ⌈m/2⌉-1 个关键字，至多有 m-1 个关键字；

一颗m阶的B树，其它重要性质：

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

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

B+树

是应文件系统所需而出的一种B-树的变型树。

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

（1）有n棵子树的结点中包含有n个关键字；

（2）所有叶子结点中包含了全部关键字的信息，以及指向这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；

（3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。

B-树

是一种平衡的多路查找树，在文件系统中很有用。

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

（1）树中的每个结点至多有m棵子树；

（2）若根结点不是叶子结点，则至少有两颗子树；

（3）除根之外的所有非终端结点至少有⌈m/2⌉ 棵子树；

（4）所有的非终端结点中包含下列信息数据

（n,A0,K1,A1,K2,A2,...,Kn,An）

其中：Ki(i=1,2,...,n)为关键字，且Ki<Ki+1(i=1,1,...,n-1);

Ai(i=0,1,...,n)为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki(i=1,2,...,n),An所指子树中所有结点的关键字均大于Kn，n（⌈m/2⌉ -1<=n<=m-1）为关键字的个数（或n+1为子树个数）

（5）所有叶子结点都出现在同一层次上，并且不带信息

性质：

在含有N个关键字的B-树上进行查找时，从根结点到关键字所在结点的路径上涉及的结点数不超过log⌈m/2⌉[(N+1)/2]+1。

红黑树

性质：待补充

键树（数字查找树）

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

相关树

二叉树