动机
平衡搜索树在相差常数倍的意义下使最坏情况深度最小,但各个键未必被等概率地查询。若某个键被查询的频率远高于其他键,把它放在靠近根的位置可以降低期望比较次数。失败查找同样重要:键与键之间不同的间隙可能有不同的查询概率。
我们推导一个区间动态规划,对已知的查询权重选出最优树。状态同时记录有序的键及其周围的间隙,递推式对到达非空子树根的每个查询收取一次比较。随后由根表重构出一棵最优树。
定义
代价约定
定义 2.11.1
(键、查询权重与比较代价约定)
设 为互不相同的有序键。成功查询是查找 ,权重为 。失败查询落入 个间隙之一: 是低于 的权重,当 时 是严格介于 与 之间的权重, 是高于 的权重。若所有权重之和为一,则下面的目标函数就是键比较次数的期望值。该递推式对任意非负权重(无需归一化)同样适用。
一次查找在每个访问到的内部节点处,将查询值与该节点的键作比较。失败查找在到达空子节点时结束;该空子节点本身不再进行键比较。因此在空树中,失败查找的比较次数为零。在非空根处的那一次比较,要计入到达该根的每一个成功或失败查询。
定义 2.11.2
(区间代价与总权重)
对 ,令 为恰好包含键 的树在这些键的成功权重及周围间隙权重 下的最小加权比较代价。该代价以子树的根处于比较深度一来度量,忽略该子树之外的任何祖先。对于空区间,令 。
非空子问题的总权重定义为
定理
定理 2.11.3
(最优搜索树递推式)
对每个非空区间,
的值是最小加权比较代价,而保存下来的取最小值的根可以重构出一棵最优树。当 时,在上述约定下空树的代价为零。
定理 2.11.4
(动态规划的复杂度)
利用前缀和计算 ,并按区间长度递增的顺序求值,可得在算术/比较模型中时间为 、空间为 的算法。这里不假设使用任何更快的根搜索优化。
证明
证明:对根作条件划分
证明
(对根作条件划分)
考虑 上的任意一棵搜索树,设其根为 。由二叉搜索性质,左子树必须恰好包含 ,右子树必须恰好包含 。相应的间隙权重分为 与 ;对 的成功查询在根处结束。
该子问题中的每个查询都在这个根处作一次比较,共贡献 。其余的比较则完全发生在相应的子树中。因此这棵树的代价为
对于固定的根,两棵子树的代价都不可能低于各自区间的最优值,而选取最优子树即可达到两者之和。对所有可能的根取最小值,便证明了递推式。对区间长度作归纳,可确立每一个状态,包括空的子区间。取得最小值的根与该值一同保存;递归地使用所保存的根,便得到一棵达到最优值的有序树。
证明透视
每个查询在根处恰好计费一次
成功键权重与失败间隙权重在进入非空子树时都要支付一次比较。该次比较之后,只有被选中的子树产生进一步的代价。这就把根处的计费与两个相互独立的较小区间问题分离开来。唯一不显然的一点,是左右两个区间子问题互相独立:二叉搜索性质确定每一侧有哪些键和间隙,因此没有权重被两侧共用,一侧子树内的代价也不取决于另一侧子树的形状。论证按区间长度归纳而告完结,因为两棵子树都严格更短,空区间是基础情形;最小值有并列并不影响其值。
空区间的基础值为零,因为到达空子节点不需要再作任何键比较。有些教材把外部的哑节点算作额外一次操作,因而采用不同的基础值与目标函数。两种约定各自都可以自洽,但若把其中一种的递推式与另一种的基础值混用,答案就会改变。
求值与重构
证明
(区间与候选根的计数)
预先计算 与 权重的前缀和,使 能在常数算术时间内求出。共有 个区间。对长度为 的区间,要尝试其 个可能的根;对所有长度求和 ,得到 次候选求值。把每个代价及一个取得最小值的根分别存入两张 的表中。
重构时,从 所保存的根开始,递归地重构其左、右区间;空区间给出空子节点。每个键成为一个节点,因此重构共产生 个输出节点,并需要 的额外遍历工作。若有多个根并列取得最小值,任何一个被记录的最小值点都给出一棵最优树。
上述代价模型把加法与比较视为常数时间运算。若有理数权重以二进制编码,则精确算术以及中间和的位长需要另外核算。该分析并不假设应用中的查询概率已被精确得知;它所说明的,只是对给定的权重哪一棵树是最优的。
直接的代价检验
一棵完整的候选树可以独立于动态规划来求值。对每个成功键 ,数出从根到 的路径上的键节点个数,再乘以 。对每个间隙,数出通往相应空子节点的路径上的键节点个数,再乘以该间隙的权重。把这些项相加,得到与递推式所计费用相同的目标值。在小例子上,这个直接计算可用于检验重构所得的树。
例如,设键为 ,根为 ,则第一个键与第三个键分别是它的左、右孩子。对 或 的每个成功查询支付两次比较,而对 的查询支付一次。四个失败间隙都到达这两个孩子之一下方的空子节点,因此都支付两次比较。加权代价为
递推式给出同样的表达式:它在根处把总权重计费一次,然后再把左、右子树的权重各计费一次。如果从根直接到达的是缺失的孩子,则相应的间隙只需支付根处的那一次比较。
概念视角结构
代价即各子树权重之和
候选树的每个键节点,恰好与搜索路径经过它的那些查询作比较,而这些查询正是其键或间隙落在该节点子树所对应区间内的查询。因此一棵树的加权代价,等于对它的所有键节点 ,把 以下区间的总权重相加,也就是把各子树所对应区间的 相加。这与上面按深度的计数相同,只是改为逐个节点而不是逐个查询来计算。对根为 的三键树,三个区间是 、 和 ,而 等于 ;递推式就是这个和,只是最小化逐个区间进行。
前缀和使权重的计算无需反复对区间求和。令 ,,并令 ,同时为方便起见约定 。则 。当 时会出现下标 ;这一约定恰好把最左侧的间隙 正确地计入。显式地检验只含一个键的区间,是发现该公式中差一错误的有效办法。
区间表还避免了在许多候选树中重复计算同一个子问题。拟定根左侧的区间只取决于它的端点,而与其上方的具体祖先无关;那些祖先处的比较已在子问题之外计费。这就是最优子结构的原因:一个保存下来的值可以代表许多不同的、更大的候选树。立方时间界是尝试每一个候选根的最坏情形计数。最终那棵树中一次查找所用的比较次数则是另一个量:它取决于该树的形状以及具体的查询。更高效的预处理算法不会改变最优查找代价的定义,而期望代价最优也并不意味着每个查询都只用对数次比较。
例题详解
间隙为何改变答案
考虑两个键且没有成功查询:,间隙权重为 ,。总权重为一。若 为根,则低于它的查询在一次比较后即停止;右子树的权重为 ,所以代价为 。若 为根,则左子树的权重为 ,所以代价为 。即使没有任何成功键的权重为正,最常见的失败查找间隙仍会影响哪个键应当靠近根。
这就是为什么把失败查询当作单一不加区分的概率是不够的。低于所有键的失败查询与高于所有键的失败查询走的是不同的路径。间隙恰好是查找判定结构的叶子,必须被分配到正确的子问题中。
反例模式
平衡的根未必使期望代价最小
设有三个键,成功权重为 ,所有间隙权重为零。选中间的键为根,代价为 。选第一个键为根并把另外两个键放在它下方,代价为 。仅按键的个数作平衡,忽略了实际的查询负载。
具体例题
例题 2.11.5
(一个键)
设只有一个键,权重为 ,两个间隙权重为 ,则每个查询恰好作一次比较。递推式给出 。两个子区间的代价都为零,尽管它们的间隙权重仍然计入根处的费用。
例题 2.11.6
(含混合查询的两个键)
取 ,,。总权重为一。以 为根,右子问题的权重为 ,代价为 。以 为根,左子问题的权重为 ,代价为 。最优的根是 。
例题 2.11.7
(权重为零的查询类)
若每个 与 都为零,则每棵树的加权代价都为零。递推式允许任意的并列,可以记录任何一个根。权重为零并不表示该键从树中移除;它只表示该键的查询对这一目标函数不产生代价。
例题 2.11.8
(空树)
若 ,则不存在键比较。即使唯一的失败查询权重 为一,在我们的约定下代价仍为零,因为查找立即到达空树。若采用另一种约定,对检查哑叶子也收费,则计的是另一个量。
常见错误
常见错误
(把间隙分给错误的子树)
当 为根时,间隙 属于右子树,间隙 属于左子树。它们描述的是不同范围的查询值。仔细划分间隙,可避免某个权重被遗漏或被两个子树重复计入。对根为 的两个键,左子问题是带有间隙 的 ,右子问题为空,其间隙为 。
常见错误
(在根处只计根键的权重)
根处的费用是到达该子问题的所有查询的权重,而不仅仅是根键的成功权重。失败查询同样要与其查找路径上的每个键作比较。空子节点的基础值为零,只是因为该子节点不再增加任何键比较。在上面的两键例子中,根为 时,根处的费用是全部权重 ,而不是 。
常见错误
(把最优值当作保证)
最后,最优树依赖于所给的权重与代价约定。它并不声称这些权重能准确预测未来的访问量,也不声称使期望比较次数最小就能使最坏情况深度最小。平衡树与加权最优树解决的是不同的目标。若工作负载随时间变化,就应当重新考虑所给的权重,以及重建这棵树的成本。
总结
对每个键区间,尝试每一个可能的根。该区间内的全部查询权重都要支付一次根处的比较,随后两个子区间各自贡献相互独立的最优代价。前缀和与按长度递增的求值顺序给出立方时间的动态规划,而保存的根可恢复出一个见证。间隙权重以及空子节点的约定对结果至关重要。
练习
快速检查
(对只有一个键、 且 的情形,计算最优代价。)
每个查询都会到达唯一的节点。
解答 · 答案
每个查询都访问这唯一的键,所以平均代价为 次比较。
快速检查
(对两个键,,,三个间隙的权重均为 ,计算以每个键为根时的代价。)
把每个根之下剩余子树的权重加到总权重上。
解答 · 答案
总权重为一。以 为根,右子树权重为 ,代价为 ;以 为根,左子树权重为 ,代价为 。
快速检查
(解释为什么即使相应的间隙权重为正,仍有 。)
想一想失败查询在到达空子节点之前作了哪些比较。
解答 · 答案
失败查询在到达这个空子节点之前,已经为每个祖先键的比较付过费。空子树不含任何可供比较的键,在上述约定下不贡献任何额外比较。
快速检查
(对三个键,成功权重为 ,间隙权重为零,比较以中间键为根的代价,与以第一个键为根、然后第二个键为其孩子的树的代价。)
分别计算两棵树中每个键的深度。
解答 · 答案
以中间键为根的代价为 。以第一个键为根、第二个键为其孩子的树,代价为 。这个例子说明,按键的个数作平衡,对所给的权重未必是最优的。