二叉树
性质：
-
第 n 层最多有 2(n-1) 个节点
-
深度为 k 的二叉树最多有 2k - 1 个节点
-
对于任何一颗二叉树，如果其叶节点有 n0 个，度为2的非叶节点有 n2个，则有 n0 = n2 + 1
-
n个节点的完全二叉树的深度为向下取整
-
如果有一颗有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i（1<=i<=n）有
-
如果i=1，则节点i是二叉树的根，无双亲，如果i>1，则其双亲节点为 ⌈i/2⌉
-
如果2i>n，则节点i没有左孩子，否则其左孩子为2i
-
如果2i+1>n，则节点没有右孩子，否则右孩子为2i+1
-
image
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树的高度范围：
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的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。
网友评论