跳到主要内容

search

查找表：由同一类型的数据元素构成的集合，完成查询|插入|删除元素等行为。只提供查询的查找表为$静态查找表$，反之为$动态查找表$。

关键字：查找表中的数据元素中某个数据项的值，可以标识一个数据元素。 主关键字：能够唯一确认一个元素的关键字，反之为次$关键字$。 查找：给定某个值，在查找表中确定一个其关键字等给定值的数据元素。

静态查找表​

顺序表的查找​

平均查找长度ASL：为确定记录在查找表中的位置而和给定值进行比较的关键字个数的期望值。

用顺序表|线性链表表示静态查找表。从第一个元素查找直到成功。ASL = $\frac34(n+1)$

有序表的查找​

折半查找法（ Binary Search）：先确定待查记录的范围，然后逐步缩小范围，直到找到|找不到记录为止。

它的近似 ASL = $log_2 (n+1) - 1$

package search;

class OrderSTable implements ISTable{
	public OrderSTable(int[] orderList) {
		this.setElements(orderList);
	}
	public int[] getElements() {
		return elements;
	}

	public void setElements(int[] elements) {
		this.elements = elements;
	}

	private int elements[];
}

public class BinarySearch implements ISearch{

	@Override
	public int search(ISTable st, int key) {
		OrderSTable ost = (OrderSTable)st;
		
		int low = 0;
		int high = ost.getElements().length;
		int mid = 0;
		while(low <= high){
			mid = (low + high) / 2;
			int cur_value = ost.getElements()[mid];
			if(key == cur_value){
				return mid;
			}else if(key > cur_value){
				low = mid +1;
			}else{
				high = mid + 1;
			}
		}
		
		return -1;
	}
}

折半查找法好比把数据拆分成一个二叉树A，A的左孩子一定大于右孩子。

斐波那契数查找：假设表ST中记录格式比某个斐波那契数小1，即 x = F(n) -1，将给定值k与cur =ST.elems[ F(n-1)]进行比较：

  • k == cur：成功
  • k < cur：在ST.elems[1] 到 ST.elems[F(n-1) - 1] 的子表中查找
  • k > cur：在ST.elems[F(n-1) + 1 ] 到 ST.elems[x] 的子表查找 斐波那契数列： F(0) = 0, F(1) = 1, F(i) = F(i - 1) + F(i -2)

斐波那契数查找的效率比折半查找法要好，但是最坏情况则更差。

插值查找： 查找给定的key，mid = $\frac{key - ST.elems[low].key}{ST.elems[high].key - ST.elems[low].key} (high - low + 1)$。

插值查找适合关键字均匀发布的表。

静态数表的查找​

当有序表中各记录的查找概率相等时折半查找法的性能最优，但是在概率不等时不成立。 我们看一个例子：

关键字p1p2p3p4p5
概率0.10.20.10.40.2
使用折半查找法的ASL =0.1* 1 + 0.22 + 0.42 +0.13 + 0.23 = 2.3
若令给定值先与p4比较，再和左右子树比较，ASL = 0.41 + 0.22 + 0.22 + 0.13 + 0.1 *3 = 1.8

使用，我们的目的在：构建一棵二叉树，使其查找性能最高。可见，这棵树的带权内路径长度之和PH最小。

静态最优查找树：PH值最小的二叉树。

静态最优查找树的构建代价过大，我们使用近似最优查找树，称作$次优查找树$。

已知一个按关键字有序的记录序列 A： $$( r(l), r(l+1), ..., r(h) )$$ 有: $$r(l).key < r(l+1).key < ... < r(h).key$$ 对应的权值为： $$w(l), w(l+1), ..., w(h)$$ 首先从 A 中取定 i 个元素构造根节点 ri，有： $$w(subl) = w(l) + w(l+1) + ... + w(i-1) $$ $$w(subr) = w(i+1) + w(i+2) + ... + w(h)$$ 我们选定的 i 将保证左右序列的权值最接近。左右子序列重复以上步骤就构造了一棵次优查找树。

索引顺序表的查找​

分块查找|索引顺序查找：除数据项表以外，还需建立一个索引表，索引表中每一项包括：

  • 关键字项：该子表内的最大关键字
  • 指针项：该子表第一个元素的位置

查找时先查找索引表，再查找数据表。

索引顺序表的查找|center|700

动态查找表​

动态查找表的特点是：边结构本身是在查找过程中动态生成的，即：对于给定值key，若表中存在关键字等于key的记录，则查找成功，否则插入关键字为key的值。

二叉排序树​

二叉排序树：一棵空树，或者具有：

  • 若左子树不为空，左子树上的所有的结点均小于它的根结点
  • 若右子树不为空，右子树上的所有的结点均大于它的根结点
  • 子树也是一棵二叉排序树

的树。

查找|插入​

查找过程和次优二叉树类似：

和根节点比较：根节点为空，插入；匹配，返回，否则继续 若给定值小于根节点值，和右节点比较，重复第一步 若给定值大于根节点值，和左节点比较，重复第一步

删除​

需要删除双亲节点为f的节点p，不失一般性，设p为f的左孩子，则有：

  • 若 p 为叶子节点，只需修改双亲节点的孩子指针；
  • 若 p 只有 左子树或者右子树，只需将其设置为f的左|右子树；
  • 若 p 同时有左子树和右子树，可以：
    • f的左子树为p的左子树c，p的右子树成为 以p的左子树c为根节点的二叉树的最后一个右孩子节点为空的节点（持续的找c的右子孩子r直到r的右孩子为空） 的右子孩子节点（如图1）
    • 直接使用p的直接前驱|后x继将p替换。因为x一定是右孩子，且没有子节点（如图2）

图1
二叉树删除|center|600
图2
二叉树删除|center|600

平衡二叉树​

平衡二叉树(AVL)：一棵空树或者具有

  • 左右子树都是平衡二叉树
  • 左右子树的深度子差绝对值不超过1

平衡因子BF(Balance Factor)：该节点的左子树深度减右子树的深度。

具体的保证 |BF| < 2 的算法不详述。

键树​

键数：有叫数字查找树。一棵度 > 1 的树，树种每个结点中不包含一个或几个关键字， 而是包含组成关键字的符号。

假设有关键字集合A = {CAI, CAO, LI, LAN ,CHA, CHANG, WEN, CHAO, YUN, YANG, LONG, WANG, ZHAO, LIU, WU, CHEN}。 首先按第n =1 个字母分为：{CAI, CAO, CHA, CHANG, CHAO, CHEN}, {WEN, WANG, WU}, {ZHAO}, {LI, LAN, LONG, LIU}, {YUN, YANG}。 观察发现，第一组还可以按 n + 1 个字母细分，如此反复直到每个小子集只有一个元素。

约定：

  • 使用$作为结束符表明字符串的结束。
  • 键树为一棵有序树，同一层的兄弟结点之间所含符号从左到右有序，结束符$小于任何字符。

结果如图所示： 键树|center|600

其实很清晰了，插入和查找就不作详述。

哈希表​

如果希望一次存取就可以找到记录，那么必须在存储位置和它的关键字之间建立一个确定的对应关系f。我们称f为$哈希(hash)函数$。可以根据这个思想创建一直$哈希表$。

哈希冲突：不同的关键字得到同一哈希地址。冲突可以减少，但无法杜绝。除了一个好的哈希函数，还要设定一种处理冲突的方法。

哈希表：哈希函数H(key)和处理冲突的方法将一组关键字映射到一个有限连续的地址集上，key 和 对应的地址 的集合 组成哈希表。 哈希造表|散列：映射过程。 哈希|散列地址：哈希函数的结果。

哈希函数的构建方法​

均匀的哈希函数：对于关键字集合中的任何一个关键字，经哈希函数映射地址集合中任何一个地址的概率是相等的。

好的哈希函数：冲突越少，函数越好。

哈希函数包括但不限于：

  • 直接定址法：取关键字或者关键字的某个线性函数值为哈希地址。$$H(key) = key | H(key) = a * key + b$$
  • 数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都事先知道，可取关键字的若干位组成哈希地址。
  • 平方取中法：取关键字平方后的中间的几位为哈希地址。
  • 折叠法：将关键字分割为位数相同的几部分，进行累加作为哈希地址。
  • 除留余数法：哈希表长 m，有$$H(key) = key \ MOD \ p, \ p ≤m $$

处理冲突的方法​

处理冲突的方法就是在冲突发生时找一个新的地址存储元素。

  • 开放定址法：$$ H_i = (H(key) + d_i) \ MOD \ m ,\ i = 1, 2, ..., m-1$$$d_i$为增量序列，有不同的取法：

    • 线性探测再散列：{1,2, ... , m-1}
    • 二次探测再散列：${1^2, -1^2, 2^2, -2^2, ... , ±k^2} (k ≤ m/2)$
    • 伪随机再散列：伪随机数字序

  • 再哈希法：在冲突时使用其他的哈希函数直到解决冲突。$$H_i= RH_（key）\ i = i, 2, .., k $$

  • 链地址法：将同义词的记录保存到哈希地址指向的一个队列中，并保证同一线性表按照关键字有序。

其实很清晰了，插入和查找就不作详述。