第七章学习小结

顺序查找

监视哨的顺序查找

因为每次循环都需要对是否越界，即是否小于n做判断。事实上，还可以有更好一点的办法，设置一个哨兵，可以解决不需要每次让i与n作比较。

折半查找（二分查找）

二分查找（又称为折半查找）是在有序序列中查找比较多的查找算法，基本思路：设有一个从小到大的序列，取中间的元素m进行比较，如果等于需要查找的元素x则返回元素m的下标，若x大于m则再从右边的区间查找，若x小于m则再从左边的区间查找，这样每次减少一半的查找范围。时间复杂度为O(lgn)，查找速度相对顺序查找要快很多，但是查找的数据序列必须是有序序列（即数据是从小到大或从大到小排序的）。

分块查找

分而治之的思想还有归并

索引存储结构

存储节点信息时，建立索引表，索引表含有若干个索引项，索引项的一般形式：(关键字，地址)，关键字表示表示一个节点，地址是指向节点的信息。可以通过索引的方法来操作相应位置的数据。

优点：

1.提高数据查找的速度

2.插入、删除时，只需要移动索引表中对应节点的存储地址，而不必移动节点中节点的数据。

缺点：

增加了索引表，所以降低了存储空间的利用率。

二叉排序树

1、就是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2、若它的右子树不空，则右子树上所有节点的值均大于其根节点的值。
3、换句话说就是：任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。
如下便是一颗二叉排序树

平衡树（AVL树）

那么什么叫“平衡”，直观上的最佳平衡条件就是 每个节点的左右子树有着相同高度，但这确实太过苛刻。平衡二叉树AVL tree退而求其次，要求任何节点的左右节点的左右子树高度差不超过1。

 B-树和B+树

是一种多路搜索树（并不是二叉的）：

       1.定义任意非叶子结点最多只有M个儿子；且M>2；

       2.根结点的儿子数为[2, M]；

       3.除根结点以外的非叶子结点的儿子数为[M/2, M]；

       4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

       5.非叶子结点的关键字个数=指向儿子的指针个数-1；

       6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

       7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的

子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

       8.所有叶子结点位于同一层；

B+树是B-树的变体，也是一种多路搜索树：

       1.其定义基本与B-树同，除了：

       2.非叶子结点的子树指针与关键字个数相同；

       3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树

（B-树是开区间）；

       5.为所有叶子结点增加一个链指针；

       6.所有关键字都在叶子结点出现；

散列表的查找

散列表的构造方法：

数字分析法；平方取中法 折叠法；除留余数法；

处理冲突的方法：

开放地址法 ；线性探测法 ；二次探测法；伪随机探测法；