一、查找表(search table):是由同一类型的数据元素或记录构成的集合。分成有序表查找和无序表查找

查找：根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。
     存在则查找成功，不存在则查找失败。
常用的操作：
    1. 查找元素是否存在
    2. 查找特定元素的属性
    3. 查找的过程中插入新的元素
    4. 查找的过程中删除找到的元素
静态查找：只有1，2两种操作
动态查询：有3，4两种操作的查找
关键字：数据元素或记录中某个数据项的值，用它可以标识一个数据元素或记录。
主关键字：可以惟一的标识一个记录
次关键字：可以识别若干个记录
查找依赖数据的组织结构或组织方式。

二、静态查找

1. 顺序表的查找,用顺序表或线性链表存储，基本思想：从表中最后一个记录开始，逐个和关键字进行比较，O(n)
2. 有序表的查找,以有序表存储，二分折半查找，low<=high,log2N+1,二叉判定树，满二叉树
   类似的有斐波那契查找：根据斐波那契序列对表进行分割
   插值查找：(key-s[l].key)/(s[h].key-s[l].key)*(h-l+1),适用与关键字均匀分布的表
3. 静态树表的查找，元素查找的概率不等，使得带权内路径长度之和PH值最小的二叉树称为静态最优查找树。
   次优查找树，构造一棵次优查找树，递归的实现，选择最小的，生成结点，构造左子树，构造右子树,调整
4. 索引顺序表的查找：用索引顺序表存储数据，分块查找,每个块记录最大值，最小值

三、动态查找表

0. 动态查找表的特点是：表结构本身是在查找过程中动态生成的，即对于给定的key，若表中存在则返回，不存在，则插入。
   动态查找表有不同的存储方法，本节讨论以各种树结构表示时的实现方法。
1. 二叉排序树:二叉排序树或是是一棵空树或者有以下性质的二叉树，若它的左子树不空，则左子树上所有结点的值均小于
   它的根结点的值，若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值，它的左右子树也分别为二叉排序树。
   也称做二叉查找树，一般可用二叉链表作为存储结构.
   二叉排序树的插入和删除，新插入的结点一定是一个新添加的叶子结点,并且是查找不成功时插入的左孩子或右孩子结点.
   中序遍历二叉排序树可得到一个关键字的有序序列。一个无序序列可通过构造一棵二叉排序树而变成一个有序序列。O(logn)
2. 平衡二叉树,又称AVL树，它或者是一棵空树，或者具有以下性质：它的左子树和右子树都是平衡二叉树，且左子树和右子树的
   深度之差的绝对值不超过1.若将二叉树上结点的平衡因子定义为该结点的左子树深度减去右子树深度，则平衡二叉树上所有结点
   的平衡因子只有-1，0，1三种取值。它的平均查找长度也和logn同数量级。
   如何使构成的二叉排序树称为平衡二叉树呢？初始化，插入，调整（单向右旋、单向左旋、先左后右，先右后左)
   在平衡树上进行查找的的时间复杂度为O(logn)
3. B-树
   B-树是一种平衡的多路查找树，它在文件系统中很有用。一棵m阶的B-树，或为空树，或是满足以下特性的m叉树：
    (1) 树中每个结点至多有m棵子树
    (2) 若根结点不是叶子结点，则至少有两棵子树
    (3) 除根结点之外的所有非叶子结点至少有m/2棵子树
    (4) 所有叶子结点中包含下列信息数据(n,A0,K1,A1,K2,A2...Kn,An)
    (5) 所有叶子节点都出现在同一层次上，并且不带信息
   B-树的查找过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程.
   B-树主要用作文件的索引，因此它的查找涉及外存的存取
   B-树的查找过程
   B-树的插入和删除过程: 叶子结点，分裂
4. B+树
    B+树是应文件系统所需而出的一种B-树的变形树。一棵m阶的B+树和m阶的B-树的差异在于:
    (1) 有n棵子树的节点中含有n个关键字
    (2) 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的
        大小自小而大顺序链接。
    (3) 所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大或最小关键字
    可以对B+树进行两种查找运算：一种是从最小关键字起顺序查找，另一种是从根结点开始，进行随机查找。
5. 键树
   键树又称数字查找树，它是一棵度>=2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。
   为查找和插入的方便，我们约定键树是有序树，可以有两种存储结构:
    (1) 以树的孩子兄弟链表来表示键树
    (2) 以树的多重链表表示键树，又称Trie树

三、哈希表

1. 哈希表定义:根据设定的哈希函数和处理冲突的方法将一组关键字映像到一个有限的连续的地址集上，并以关键字在
            地址集中的“像”作为记录在中的存储位置，这种表便称为哈希表，这一映像过程称为散列.
2. 哈希函数的构造方法
   a. 直接定址法:线性函数
   b. 数字分析法:10或8或16进制的若干位
   c. 平方取中法:取关键字平房后的中间几位为哈希地址
   d. 折叠法:将关键字分割成位数相同的几部分，然后取这几部分的叠加和
   e. 除留余数法
3. 哈希冲突的解决方法:
   a. 开放定址法，线性探测在散列，二次探测在散列，伪随机探测在散列
   b. 在哈希法
   c. 链地址法
   e. 建立一个公共溢出区
4. 哈希表的查找及分析