查找

静态查找表

顺序表的查找

平均查找长度 (ASL, Average Search Length) 定义为查找一条存在于表中的记录时进行比较操作次数的期望值. 若 `c_k` 是找到第 `k` 个记录所需比较的次数, `p_k` 为查找第 `k` 个记录的概率, 则 `sum_k p_k = 1`, 且 `ASL = sum_k p_k c_k`.

顺序查找 即逐个查找比较, 适用面很广. 为了避免每一步都要检测整个表是否查找完毕, 在表头处设置哨兵, 从表尾开始反向查找. 如果找不到, 则返回 0. 可以看到, 哨兵同样完美解决了空表的判断问题.

L.find(key):
	L[0] = key
	i = L.length-1
	while L[i] != key
		--i
	return i

折半查找 (二分查找, binary search) 设函数 f 是 [a, b] 到 {0, 1} 的单调增函数, 下面的 bsearch 算法在区间中寻找满足 f(n) = 1 的最小整数 hi 和满足 f(n) = 0 的最大整数 lo. 我们不妨设 f(a) = 0, f(b) = 1, 这样所求的数就总是存在的. 思路是令初值 lo = a, hi = b, 每次将区间缩小一半, 直到 hi-lo = 1.

例如, 为了在升序数组 L 中找到第一个大于 (大于等于, 等于) val 的元素, 我们取 f(n) = L[n] >(≥,=) val, 初值可以设定为 lo = -1, hi = L.length; 若算法返回 L.length, 则表示该元素不存在.

寻找数组中第一个大于等于 2 的数 hi, 和最后一个小于 2 的数 lo. 若前者不存在, 返回数组的长度 6, 若后者不存在, 返回 -1.

在 while 循环末尾处维持不变式: f(lo) = 0, f(hi) = 1. 由 f 的单调性有 lo < hi.
循环一定会结束, 因为 hi-lo > 1 保证了 lo < mid < hi.
一旦循环结束, 有 lo < hi ≤ lo+1, 即 hi-lo = 1.
结合循环不变式, lo, hi 即为所求.

又例如, f 在正整数集上有定义, 要求满足 f(n) = 1 的最小正整数. 我们只知道这个数存在, 而 n 的上界尚不清楚. 这时可以用如下的函数得到一对初值:

# 规定 f(0) = 0
init(f):
    n = 1
    while !f(n):
        n *= 2
    return ⌊n/2⌋, n # 检验: f(lo) = 0, f(hi) = 1;

令 mid = ⌊(lo+hi)/2⌋ 可能导致整数上溢. 更进一步, 若 lo, hi 是指针或迭代器类型, 相加是不可能的.
由于算法涉及到 -1, 我们不推荐使用无符号整型下标. 如果非要用, 一个补救的措施是把数组头空出不用, 从下标 1 开始使用它.

Fibonacci 查找 同样仅适用于按关键字有序的顺序表. 利用 Fibonacci 数列 `F_n = { 0, if n = 0; 1, if n = 1; F_(n-1) + F_(n-2), if n ge 2; :}` 假设表中记录数 `n = F_k-1`, 以 `F_(k-1)` 为分点, 将表分为长 `F_(k-1)-1` 的左半部分 L[1..F_k-1-1] 和长 `F_(k-2)-1` 的右半部分 L[F_k-1+1..F_k-1]. 由于 Fibonacci 数列前后项比以黄金比例为极限, 可以证明 Fibonacci 查找的平均性能优于折半查找, 但最坏情况的性能 (仍是 `O(log n)`) 比折半查找差. 它的另一优点是分割时只需加减运算.

插值查找 同样仅适用于按关键字有序的顺序表. 令 hi, lo 分别为当前表的最大, 最小元素的下标, 取分点为 `i = lo + (val - L[lo])/(L[hi] - L[lo]) (hi - lo)`. 插值查找特别适用于那些元素值分布均匀的表.

Huffman 树 (到叶结点带权路径最短)

树中两个结点之间的路径长度是这两个结点间路径所含的边数. 树的路径长度是从根到每一叶结点的路径长度之和. 结点的带权路径长度是从根到该结点的路径长度乘以该结点的权重. 这里假定各结点的权重是正数. 树的带权路径长度 (weighted path length, WPL) 是从根到每一叶结点的带权路径长度之和: `WPL = sum_k w_k l_k`. 给定叶子结点及其权重, 构造的具有最小 WPL 的二叉树称为最优二叉树. 最优二叉树一般是不惟一的.

最优二叉树对叶子结点的次序不作要求, 如果要求构造的二叉树具有给定次序的叶子结点 (比如, 成绩等级的判定树) 可以参考下面的静态最优查找树.

最优二叉树没有 1 度点; 因此, 一棵具有 `n` 个叶结点的最优二叉树一共有 `2n-1` 个结点.

假如一棵最优二叉树有 1 度点 `s`, 不妨设 `s` 只有左子树. 去掉 `s`, 令 `s` 的左子树取代 `s` 的位置, 则所有 `s` 的左子树中的叶结点的深度都减 1, 由于结点的权重是正数, 我们就得到一棵 WPL 更小的二叉树. 矛盾. 二叉树的 2 度点比叶子结点少 1, 因此共有 `2n-1` 个结点.

给定权值所构造的所有最优二叉树中, 可以找到一棵, 其权值最小的两个叶结点是兄弟.

设 `a, b` 是最优二叉树 `T` 中权值最小的两个叶结点, 假如 `a, b` 不是兄弟, 设 `a, a_1` 是兄弟, `b, b_1` 是兄弟. 则 `max(w(a), w(b)) le min(w(a_1), w(b_1))`. 不妨设 `d = "depth"(a_1) - "depth"(b) ge 0`, 现交换结点 `a_1, b`, 新的 WPL 与旧的之差 `WPL' - WPL = (w(b) - w(a_1))d le 0` 因此新二叉树的 WPL 不大于原来的 WPL, 新二叉树必为最优二叉树.

给定带权叶结点集 `N`. 去掉其中权值最小的两个结点 `a, b`, 加入一个新结点 `c`, 满足 `w(c) = w(a) + w(b)`. 令集合 `M = N\\{a, b} uu {c}`. 设 `T` 为 `M` 上构造的一棵最优二叉树, 现在 `T` 中加入结点 `a, b` 作为 `c` 的子结点, 则所得的新二叉树 `T_1` 是 `N` 上的一棵最优二叉树.

可以看到, 在 `T` 中加入 `a, b` 的效果是使得权值 `w(a) + w(b)` "下移" 一层, 所以 `WPL(T_1) = WPL(T) + w(a) + w(b)`. 设 `S_1` 是 `N` 上的一棵最优二叉树, 且 `a, b` 在 `S_1` 中是兄弟. 我们从 `S_1` 中去掉 `a, b`, 令它们的父结点 `c` 的权值等于 `w(a) + w(b)`, 作为新的结点. 所得的新二叉树记为 `S`, 则 `WPL(S_1) = WPL(S) + w(a) + w(b)`. 但 `T` 是 `M` 上的最优二叉树, 有 `WPL(T) le WPL(S)`. 所以 `WPL(T_1) le WPL(S_1)`, 即 `T_1` 是 `N` 上的一棵最优二叉树.

构造最优二叉树的 Huffman 算法

给定 N 个正的权值, 先构造 N 棵具有单结点的二叉树, 将权值赋予根结点.
新建一个根结点, 选取森林中权值最小的两棵树, 分别作为它的左右子树. 令新构造的树权值为两子树之和, 替代原来的两棵子树, 加入到森林中.
反复步骤 2, 直到只剩一棵树, 称为 Huffman 树. Huffman 树就是一棵最优二叉树.

[0..N-1]

PriorityQueue

HuffmanTree {
	int weight
	int left
	int right
} ht[2*N-1]

huffman(w):
	PriorityQueue q
	for i = 0 to N-1:
		ht[i] = (w[i], 0, 0)
		q.enqueue(i)
	for i = N to 2*N-2:
		l = q.dequeue()
		r = q.dequeue()
		ht[i] = (weight[l] + weight[r], l, r)
		q.enqueue(i)
	return q.dequeue()

Huffman 编码 电报编码问题中, 需要将 A-Z 等字符编码为 0-1 二进制串. 为避免解码时的歧义, 要求使用前缀编码, 即任一字符的编码都不是另一字符编码的前缀. 如果从二叉树的根出发, 用 "向左" 表示数位 0, "向右" 表示数位 1, 则每一条从根到叶的路径都确定一个编码, 容易看出, 任一编码都不是另一编码的前缀, 因此得到的是前缀编码. 可以根据各种字符在电报中使用的频率, 为二叉树的每个叶结点赋以权值, 构造 Huffman 树, 来设计电报的编码. 由于 Huffman 树是带权路径最小的二叉树, 所以平均的报文长度也是最短的. 这种编码称为 Huffman 编码.

求 Huffman 编码 使用回溯法遍历 Huffman 树的所有根到叶的路径. 根到叶的最长路径不超过结点数减一, 即 N-1, 再算上空字符, str 只需大小为 N 的空间即可.

char str[N]

# 调用时取 lv = 0
huffman_code(root, lv):
	if root > N: # 当 root 是内结点时
		str[lv] = '0'
		huffman_code(ht[root].left, lv+1)
		str[lv] = '1'
		huffman_code(ht[root].right, lv+1)
	else:
		str[lv] = '\0'
		print(str)

静态最优查找树 (到所有结点带权路径最短)

考虑将分数 (0-100) 转换为等级 (E, D, C, B, A) 的程序, 假设已知输入数据的分布为

等级	E	D	C	B	A
分数	0-59	60-69	70-79	80-89	90-100
频率	0.05	0.15	0.40	0.30	0.10

从理论上计算, 当输入数据有 100 个时, 程序 1 的比较次数为 315, 而程序 2 的比较次数为 220, 优于程序 1. 原因在于, 程序 1 的判定树严重不平衡, 而程序 2 的判定树是最优查找树.

程序 1

  60             if n < 60:
 /  \            	'E'
E   70           elif n < 70:
   /  \          	'D'
  D   80         elif n < 80:
     /  \        	'C'
	C   90       elif n < 90:
	   /  \      	'B'
	  B    A     else:
                 	'A'

程序 2

       80        if n < 80:
     /    \      	if n < 70:
    70     90    		if n < 60:
   /  \   /  \   			'E'
  60   C B    A  		else:
 /  \            			'D'
E    D           	else:
                 		'C'
                 elif n < 90:
                 	'B'
                 else:
                 	'A'

动态查找树

即具有静态的查找功能, 又具有动态的增, 删, 改的功能.

二叉查找树 (二叉排序树, Binary Search Tree, BST) 是一棵二叉树, 它要么是空树, 要么每个结点中存储一个不重复的关键字, 若左子树非空, 则左子树上所有结点关键字小于根的关键字; 右右子树非空, 则右子树上所有结点关键字大小根的关键字. 且左右子树也分别是二叉查找树. 二叉排序树的中序遍历序列将所有关键字从小到大列出.

struct BSTNode:
	KeyType key
	BSTNode *left, *right
BSTNode *root

# 在以 root 为根的 BST 中查找值 key, 以引用返回指向结点的指针
find_rec(&root, key):
	if !root or key == root->key:
		return root					# 返回引用
	elif key < root->key:
		return find_rec(root->left)	# 引用重绑定
	else:
		return find_rec(root->right)

# 非递归实现, 效率更高
find(&root, key):
	while root and key != root->key:
		if key < root->key:
			&root = root->left	# 引用重绑定
		else:
			&root = root->right
	return root					# 返回引用

insert(&root, key):
	# node 是一个引用, 因此当树空时, node 就是 root.
	# 当某结点的左子树空时, node 就是这个结点的左指针域. 右子树类似.
	node = find(root, key)
	if node:
		error('key already exists')
	else:
		node = new BSTNode(key, NULL, NULL) # 插入一个叶子结点

delete(&root, key):
	node = find(root, key)	# node 是引用
	if !node:
		error('key not exist')
	elif !node->left:		# 左子树空, 重接右子树
		tmp = node
		node = node->right
	elif !node->right:		# 右子树空类似
		tmp = node
		node = node->left
	else:					# 左右子树都不空
		pre = node
		tmp = node->left
		# 寻找左子树的中序终点
		while tmp->right:
			pre = tmp
			tmp = tmp->right
		# 现在 tmp 无右子树. 将 tmp 拷贝到 node
		node->key = tmp->key
		if pre == node:
			pre->left = tmp->left
		else:
			pre->right = tmp->left
	delete tmp

delete 函数中, 也可以用下面的写法避免拷贝
if pre == node:
    tmp->right = node->right
    tmp = node
    node = node->left
else:
    pre->right = tmp->left
    tmp->left = node->left
    tmp->right = node->right
    swap(tmp, node)

cpp 不支持引用重绑定. 因此 c/cpp 的实现应该使用二重指针:
BSTNode **find(BSTNode **root, int val) {
	while ((*root) && val != (*root)->val) {
		if (val < (*root)->val)
			root = &(*root)->left;
		else
			root = &(*root)->right;
	}
	return root;
}
BSTNode* insert(BSTNode* root, int val) {
	BSTNode **node = find(&root, val);
	*node = new BSTNode(val, NULL, NULL);
	return root;
}

平衡二叉树 (AVL 树) 是一棵二叉查找树, 且任意结点的左, 右子树的高度差 (即平衡因子, height(left) - height(right)) 的绝对值不大于 1. 另一种等价定义是, 平衡二叉树是一棵二叉查找树, 它或者是空树, 或者左右子树的高度差的绝对值不大于 1, 且左右子树都是平衡二叉树.

L = +1
E = 0
R = -1

struct AVLNode
	Type data
	AVLTreeNode *left, *right
	int bf                  # 平衡因子 balance factor
AVLNode *root

# 返回左/右指针的引用
go(dir):
	if dir == L:
		return this->left
	elif dir == R:
		return this->right

# 右旋示意图. 此操作保持中序序列不变
#   T         P
#  /           \
# P    P   T    T
#  \    \ /    /
#   Q    Q    Q
rotate(dir):
	p = this->go(-dir)
	this->go(-dir) = p->go(dir)
	p->go(dir) = this
	this = p

# 左平衡示意图
# LL单旋:            LR双旋:
#     T(++)   P          T(++)     T       Q
#    /  \    / \        /  \      / \    /   \
#   P(+) S  R   T      P(-) S    Q   S  P     T
#  / \         / \    / \       / \    / \   / \
# R   Q       Q   S  R   Q(?)  P   B  R   A B   S
#                       / \   / \
#                      A   B R   A
# 双旋情形, 分别代入 Q.bf = 0, +, -, 考查 A, B, R, S 的高度可知,
# Q.bf == 0 时四者高度相等; Q.bf == + 时其它三者相等, 而 B 短 1;
# Q.bf == - 时其它三者相等, 而 A 短 1.
balance(dir):
	p = this->go(dir)
	if p->bf == dir:    # 单旋
		this->bf = p->bf = E
		this->rotate(-dir)
	elif p->bf == -dir: # 双旋
		q = p->go(-dir)
		if q->bf == dir:
			this->bf = -dir
			p->bf = E
		elif q->bf == -dir:
			this->bf = E
			p->bf = dir
		else: # q->bf == E:
			this->bf = p->bf = E
		q->bf = E
		this->go(dir)->rotate(dir)
		this->rotate(-dir)

# 在 dir 子树插入结点, 并判断树是否长高
is_taller(dir):
	if !this->go(dir)->insert(val):
		return False
	elif this->bf == -dir:	# 原本向 -dir 倾斜: 倾斜抵消, 树不变
		this->bf = E
		return False
	elif this->bf == dir:	# 原本向 dir 倾斜: 为保持平衡需作调整
		balance(dir)
		return False
	else: # this->bf == E:	# 原本平衡时: 向 dir 倾斜, 树长高
		this->bf = dir
		return True

# 当且仅当执行的插入使得以 this 为根的树长高时返回 True
insert(val):
	if !this:              # 空树, 插入
		this = new AVLTNode(val, NULL, NULL, E)
		return True
	elif val == this->data:# 结点已存在, 不插入
		return False
	elif val < this->data: # 应当搜索左子树
		return this->is_taller(L)
	else:                  # 应当搜索右子树
		return this->is_taller(R)

设高度为 `h` 的平衡二叉树中的最少结点数为 `n_h`, 含 `n` 个结点的平衡二叉树的最大高度为 `h_n`, 则 `n_h = { (0, if h = 0), (1, if h = 1), (n_(h-1) + n_(h-2) + 1, if "else") :}` 可以解得 `n_h = 1/(2 sqrt 5) [(sqrt 5 + 3) varphi^h + (sqrt 5 - 3) psi^h] - 1`. 其中 `varphi, psi = (1+-sqrt 5)//2`. 于是 `n_h = O(varphi^h)`, `h_n = O(log_varphi h) = O(log_2 h)`.

B 树

struct BNode:
	int n_key			# 关键字数目
	KeyType key[m]		# 0 号单元未用
	BNode *parent		# 父指针
	BNode *child[m]		# 子树指针

find(KeyType k):
	p = this
	pre = NULL
	i = 0
	while p:
		# i = 1..p->n_key
		# 且 p->key[i] ≤ k < p->key[i+1]
		i = p->key.find(k)
		if i > 0 and p->key == k:
			return p, i, True	# 查找成功
		else:
			pre = p
			p = p->child[i]
	return pre, i, False		# 查找失败

B⁺树