9.3 动态查找表

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、在双链树中插入或删除一个关键字，相当于在树中某个结点上插入或删除一棵子树。

C语言 | 100-200之间不能被3整除的数​ mp.weixin.qq.com

文章来源: zhuanlan.zhihu.com，作者：小林C语言，版权归原作者所有，如需转载，请联系作者。

原文链接：zhuanlan.zhihu.com/p/338773523