动态查找

总结完静态查找，继续总结一下动态查找
动态查找表的特点是：表结构本身是在查找过程中动态生成的，对于给定的值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于Key的记录。

• 二叉排序树（BST）
  二叉排序树：或者是一棵空树，或者具有以下性质：1）若其左子树不空，则左子树上的所有结点的值均小于它的根结点的值；2）若它的右子树不空，则右子树上所有结点的值均大于它的跟结点的值；3）它的左右子树也分别是二叉排序树。
  由其定义我们可知，中序遍历二叉树可得到一个关键字的有序序列。

• 平衡二叉树(AVL树)
  平衡二叉树，或者为空树，或者具有如下性质：左子树和右子树都为平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1.
  平衡因子（BF）:该结点的左子树的深度减去它右子树的深度。平衡二叉树上所有结点的平衡因子只可能是-1、0和1.
  在平衡二叉树上查找的时间复杂度为O(logn)

• B-树
  是一种平衡的多路查找数，在文件系统中很有用。
  一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：
  1）树中每个结点最多有m棵子树
  2）若根结点不是叶子结点，则至少有两棵子树
  3）除根结点外的所有非终端结点至少有m/2上取整棵子树
  4）所有的非终端结点包含如下信息（n,A0,K1,A1,K2,A2,…,Kn