查找概论
- 查找表(search table): 由同一类型的数据元素(或记录)构成的集合.
- 查找: 就是根据给定的某个值, 在查找表中确定一个其关键字等于给定值的数据元素.
查找表按照操作方式分为两种:
- 静态查找表(static search table): 只作查找操作的查找表.
- 动态查找表(dynamic search table): 在查找的过程中同时插入查找表中不存在的数据元素, 或者从查找表中删除已经存在的某个元素.
顺序表查找:
- 顺序查找: 又叫线性查找, 是最基本的查找技术, 它的查找过程是: 从头到尾一一查找匹配.
有序表查找:
- 折半查找(binary search), 又名二分查找. 它的前提是线性表中的记录必须是关键字有序.
- 插值查找
- 斐波那契查找
线性索引查找
索引: 就是把一个关键字与它对应的记录相关联的过程.
- 稠密索引: 在线性表中, 将数据集中的每个记录对应一个索引项, 索引项一定是按照关键码有序排列.
- 分块索引: 把数据的记录分成了若干块, 块内无序, 块间有序.
- 倒排索引: 索引项的通用结构是: 1 次关键码(可以对应多条记录) 2 记录号表(里面是记录的主关键字)
二叉排序树(binary sort tree, 二叉查找树)
- 或是空树
- 若它的左子树不为空, 则左子树上所有结点的值均小于它根结点的值.
- 若它的右子树不为空, 则右子树上所有结点的值均大于它根结点的值.
- 左右子树也分别为二叉排序树.
平衡二叉树(AVL树): 一种二叉排序树, 其中每一个节点的左子树和右子树的高度差至多等于1.
AVL树判断
多路查找树(muitl-way search tree): 每一个结点的孩子数可以多于两个, 且每一个结点处可以存储多个元素.
B树: 一种平衡的多路查找树, 结点最大的孩子数目称为B树的阶. 一个m阶的B树具有如下属性.
- 若根结点不是叶结点, 则至少有两颗子树.
- 每一个非根的分支结点都有k-1个元素和k个孩子 ([m/2] <= k <= m), 每一个叶子结点n都有k-1个元素([m/2] <= k <= m).
- 所有叶子结点都位于同一层次.
B+树: 应文件系统所需而出的一种B树的变形, 严格来说, 它已经不属于树形结构.
B+树
散列表查找
处理散列冲突的方法:
-
开放定址法: 一旦发生冲突, 就去寻找下一个控的散列地址.
开放定址法公式 再散列法: 可以实现准备多个散列函数, 若发生冲突, 则用下一个函数再散列.
-
链地址法: 如图
链地址法 -
公共溢出区法: 所有冲突的关键字存放在一个公共的溢出区域
公共溢出区法
