搜尋樹可以圍繞剛存取的項目重組
二叉搜尋樹依鍵比較決定搜尋方向。若樹成為一條鏈,搜尋可能需線性時間。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。它容許勢能下降以支付差額,完整證明保證此伸展確有足夠下降。因此線性實際存取與對數攤銷界相容;高度平衡不變量是另一種保證,伸展沒有宣稱它。