01
二叉排序树和平衡二叉树
1、二叉排序树及其查找过程
二叉排序树或者是一棵空树，或者是具有以下性质：
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
（3）它的左、右子树也分别为二叉排序树。
2、二叉排序树的插入和删除
（1）和次优二叉树相对，二叉排序树是一种动态树表。其特点是，树点的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。
（2）对于一般的二叉树来说，删去树中一个结点是没有意义的。因为它将使以被删结点为根的子树成为森林，破坏了整棵树的结构。然而，对于二叉排序树，删去树上一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。
3、平衡二叉树又称AVL树，它或者是一棵空树，或者它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1.
02
B-树和B+树
1、B-树是一种平衡的多路查找树，它在文件系统中很有用。
2、在B-树上进行查找包含两种基本操作：
（1）在B-树中找结点。
（2）在结点中找关键字。
3、B+树是应文件系统所需而出的一种B-树的变型树，一棵m阶的B+树和m阶的B-树的差异在于：
（1）有n棵子树的结点中含有n个关键字。
（2）所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
（3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大关键字。
03
键树
1、键树又称数字查找树（Digital Search Trees）。它是一棵度>=2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。
2、在双链树中插入或删除一个关键字，相当于在树中某个结点上插入或删除一棵子树。
如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！