搜索树可以围绕刚访问的项目重组
二叉搜索树依键比较决定搜索方向。若树成为一条链,搜索可能需线性时间。AVL 树维持明确的高度平衡条件来避免这种形状;伸展树(splay tree)则在找到项目后,按指定旋转序列把该节点移到根。
结果不必高度平衡,单次搜索仍可昂贵。有用保证针对一连串访问,证明通过势能变化为旋转付账。我们会证明这项保证,而不是从几幅较矮的树图猜测它。
全节固定 个互异键,只分析成功搜索后伸展已找到节点。插入、删除及搜索失败时的策略,需要另作定义与分析,不是以下过程所实现的操作。
旋转改链接,却保留搜索顺序
定义 9.1.1
(二叉搜索树顺序与旋转)
节点左子树所有键都较小,右子树所有键都较大。旋转把子节点 x 提升至父 p 之上,并保留键的中序排列。
若 x 是左子节点,右旋为:
p x
/ \ / \
x C -> A p
/ \ / \
A B B C
A、B、C 子树可为空;A、x、B、p、C 的顺序不变。提升右子节点则用左右镜像的旋转。
指针实现须把提升节点接回原祖父或树根,转移中间子树 B,并更新父指针;B 非空时也须更新其父。旋转不新增、删除或改变键。若有父指针,每次只改常数个链接。
以 ROTATE_UP(x) 表示把 x 提升至其当前父之上的基本操作;左旋或右旋由 x 当前位于哪一边决定。
伸展选择单步或双步
设 p 是 x 的父,g 是存在时的祖父。
- Zig:p 是根,提升 x 一次。
- Zig-zig:x、p 同为左子节点或同为右子节点;先把 p 提升至 g 之上,再把 x 提升至 p 之上。
- Zig-zag:x、p 位于相反边;先把 x 提升至 p 之上,再把 x 提升至 g 之上。
SPLAY(x):
while parent(x) is not NONE:
p = parent(x)
g = parent(p)
if g is NONE:
ROTATE_UP(x)
else if (x is left child of p) == (p is left child of g):
ROTATE_UP(p)
ROTATE_UP(x)
else:
ROTATE_UP(x)
ROTATE_UP(x)
return x
每个组成旋转都保留搜索树顺序,所以整步也保留它。每次旋转把被访问 x 的深度减一,包括 zig-zig 中先旋转 p 的那一次。因此过程终止并让 x 成根。若 x 原深度为 d,恰需 d 次旋转;搜索本身访问 d+1 个节点。
例题 9.1.2
(比较三个键上的两种双步)
先设根为 30,左子为 20,而 20 的左子为 10。访问 10 要做 zig-zig。先提升 20 至 30 之上,得到根 20、子节点 10 与 30;再提升 10,得到根 10,其右子为 20,而 20 的右子为 30。
若改成根 30、左子 10,而 10 的右子为 20,访问 20 是 zig-zag:先把 20 提升至 10 之上,再提升至 30 之上。最后根为 20,左右子为 10、30。
两次访问都做两次旋转,中序都是 10、20、30。但第一结果仍是一条链。伸展没有保证每次结果都平衡。
反例模式
反复提升 x 不等于 zig-zig 规则
第一个三键例子中,若先把 10 提升至 20 之上,再提升至 30 之上,结果是根 10、右子 30、30 的左子 20,与指定 zig-zig 结果不同。
两方法都保留搜索顺序,也都把所求键移至根,但这些性质不足以让它们成为同一算法。以下访问引理使用指定双步,不能当成任意保序旋转序列的性能证明。
用子树大小定义势能
定义 9.1.3
(秩、势能与摊还旋转成本)
以 表示含 v 自身在内的子树节点数,定义秩及树势能:
全节对数以 2 为底。对局部一步,以 表示步前秩、 表示步后秩。若用了 c 次旋转,摊还旋转成本定义为 。这是记账量,不是该步实际测量的时间。
因为 ,有 。大小可以只是证明使用的数学量;基本伸展过程不必在每次旋转后存储或重算所有子树大小。
只有局部旋转中的节点改变子树大小:zig 是 x、p,双步是 x、p、g。其余子树大小不变;局部子树以上祖先的后代集合也不变。双步后 x 成为 g 原子树的根,因此 。每步都有 。
为两次旋转付账的大小不等式
引理 9.1.4
(两个不相交非空子树给出秩界)
若大小 a、b 的两个不相交非空子树,都在大小 S 的子树内,则
证明
(由两个大小的乘积出发)
不相交给出 。由 ,得 ,其中第二个不等号用到 及正数性质。对这些正数取以 2 为底的对数,得 。
减去的 2 很重要,它将支付两次实际旋转。不能对任意重叠子树套用此式。
分别界定每种局部伸展步
引理 9.1.5
(单个伸展步的摊还成本)
设某一伸展步提升 x,步前秩为 、步后秩为 。Zig(一次旋转)有 。Zig-zig 或 zig-zag(两次旋转)有 。
证明
(分别计算 zig、zig-zig 与 zig-zag)
Zig。 p 为根且 ,只有 x、p 改秩,所以
故也至多为 。一次伸展最多有一次 zig,而且只在结尾出现。
Zig-zig。 看左左情形,右右为镜像。步前形状是 g(p(x(A,B),C),D),两旋转后为 x(A,p(B,g(C,D)))。所以旧 x 子树与新 g 子树不相交,且都包含于新 x 子树。大小不等式给出 。利用 、 及 ,
Zig-zag。 左右情形步前为 g(p(A,x(B,C)),D),步后为 x(p(A,B),g(C,D))。新的 p、g 子树不相交,且都在新 x 子树内,故 。又因 ,
最后一步用了 x 的秩增加非负;右左情形对称。
证明透视
Zig-zig:旧 x 子树与新 g 子树
Zig-zig 计算所用的事实中,只有一项带有实质内容。等式 恰好消去两个秩。不等式 与 成立,是因为新 p 子树在新 x 子树之内,而旧 p 子树包含旧 x 子树;它们只是舍去几项。真正的输入是大小不等式,应用于旧 x 子树(A、B 与 x 的节点)和新 g 子树(C、D 与 g 的节点)。这两个节点集合不相交,且都在新 x 子树内,因此 。
记账之所以结清,是因为该不等式的 抵消了代表两次旋转的 2,恰好剩下 。若改为把新 p 子树与新 g 子树配对就会失败:g 在 p 之内,两个集合重叠,不等式不适用。在 zig-zag 步中,新 p 子树与新 g 子树不相交,所以同一不等式在那里可用。
把局部界望远镜相消,得到访问引理
定理 9.1.6
(固定大小树的访问引理)
设 x 是成功访问的节点,C 是其伸展的总旋转次数。则
证明
(累加同一被访问节点的秩增加)
每个双步的摊还成本,至多是 x 秩增加的三倍;可能出现的最后 zig 至多多付一。局部势能差相消成整次伸展的势能差;每步提升的都是同一 x,所以秩增加也相消。最后 x 为根,秩是 ,减初始秩即得第一界;初始秩非负,再得第二界。若 x 原已是根,零旋转直接满足不等式。
对固定键集合的 m 次成功访问求和,得
任意初始树可能带有势能,有限序列界不可悄悄删去它。每次搜索访问 个节点,每次旋转只做常数指针工作,所以在键比较与指针操作为常数成本的通常模型下,总成功搜索及伸展成本为 。这是摊还序列保证,没有随机输入假设。
两次访问的势能逐步计算
例题 9.1.7
(深度为三的访问:先 zig-zig,后 zig)
取根为 40、左子 30、30 的左子 20、20 的左子 10 的链,访问 10。40、30、20、10 的子树大小是 4、3、2、1,所以 。
节点 10 的深度是 3,所以这次伸展用三次旋转。第一步是 zig-zig,x=10、p=20、g=30:先把 20 提升至 30 之上,再把 10 提升至 20 之上。结果是根 40、左子 10、10 的右子 20、20 的右子 30。此时 10 是根的左子,以一次 zig 结束:根变成 10,右子为 40,40 的左子为 20,20 的右子为 30。中序仍是 10、20、30、40。
最后 10、40、20、30 的子树大小为 4、3、2、1,所以 又是 ,。摊还成本是 。访问引理允许 。结果又是深度为 3 的链:势能没有下降,这次伸展也没有让树变矮。
例题 9.1.8
(边界情形:单独一次 zig、根节点与单个键)
取两个键,根为 20、左子为 10,访问 10。此时 。10 是根的子节点,一次 zig 就够:根变成 10,右子为 20, 仍是 1。所以 ,在单步界 之内。
再次访问 10。它已经是根,不做旋转,势能不变,。引理中 ,允许 ,而 。只有一个键时伸展什么也不做,引理的界是 。
单次访问仍可能花线性时间
n 节点链中,搜索最深键访问 n 个节点,做 n-1 次旋转。访问引理界定的是实际旋转加势能差,所以势能大幅下降可以支付昂贵访问;它没有对该次实际旋转数给相同对数上界。
访问后同一键已在根,再次成功访问不需旋转,这说明重组可以有帮助。但定理为所有序列所证,包括不重复的序列。伸展的保证来自指定更新与摊还记账,不是 AVL 式高度不变量。
伸展树在每个序列上是否都追得上最佳树策略,即动态最优猜想,至今未被证明。
自然的下一个问题
伸展树和任何搜索树策略一样好吗?
伸展树在每个序列上是否都追得上最佳树策略,即动态最优猜想,至今未被证明。
访问引理只把伸展与平衡树的 成本相比。更强的问题是:对每个访问序列,伸展的总成本是否都在最佳二叉搜索树策略成本的常数倍之内?这里的最佳策略可以在两次访问之间重排树,并且预先知道整个序列。动态最优猜想的答案是肯定的。本单元没有证明它,它仍然只是猜想。
伸展记账中的常见错误
常见错误
(把大小不等式用在嵌套的子树上)
不等式 需要两个子树不相交。若取一个子树与它自己配对,即 ,左边是 ,比右边多 2。在 zig-zig 步中,新 p 子树包含新 g 子树,所以两者不能配对;旧 x 子树与新 g 子树则可以。
常见错误
(在序列界中漏掉初始势能)
界 并不成立。取 ,对 32 个键的链访问最深的键,,而 。初始势能 可大至 ,正是它支付了这个差额。
常见错误
(以为伸展后的树一定平衡)
伸展保证的是一个访问序列的摊还界,不是树的形状。在上面深度为三的例子中,访问后的树又是四个节点的链;之后访问其最深的键,仍要三次旋转。
附解答练习
快速检查
(1. 两次旋转的顺序有关系)
根为 30、左子 20、20 的左子 10。伸展 10,给出第一次旋转后的根及最后形状,并与连续提升 10 两次比较。
解答 · 解答 1
指定 zig-zig 先提升 20,中间根是 20、子为 10、30;再提升 10,成为根 10、右子 20、20 的右子 30。若改成提升 10 两次,则根 10、右子 30、30 的左子 20。中序都是 10、20、30,但形状不同,只有第一个是指定 zig-zig。
快速检查
(2. 计算实际与摊还成本)
根为 30、左子 10、10 的右子 20。伸展 20,用以 2 为底的对数计算前后势能、旋转次数及摊还旋转成本。
解答 · 解答 2
初始 30、10、20 子树大小是 3、2、1,势能为 。Zig-zag 后根 20、叶子 10、30,势能为 。两次实际旋转、势能差 ,摊还成本为 。指针工作确实做了;较小记账成本反映势能下降。
快速检查
(3. 保留初始势能项)
对任意初始形状的固定八键伸展树做 16 次成功访问,用已证粗界计算总旋转数与总搜索访问节点数。这是概率主张吗?
解答 · 解答 3
、,所以旋转总数至多 。每次搜索比其旋转数多访问一节点,故总访问数至多 。这是保守的确定性序列界,没有假设随机访问或对输入序列取期望。
快速检查
(4. 对数摊还界不是每次访问上限)
32 键树是一条链,成功搜索最深节点。访问几个节点、旋转几次?为何不违反访问引理对摊还旋转成本的界 ?
解答 · 解答 4
搜索访问 32 节点,做 31 次旋转。引理界定 ,不是单独 31。它允许势能下降以支付差额,完整证明保证此伸展确有足够下降。因此线性实际访问与对数摊还界相容;高度平衡不变量是另一种保证,伸展没有声称它。