動機
平衡搜尋樹在相差常數倍的意義下使最壞情況深度最小,但各個鍵未必被等機會查詢。若某個鍵被查詢的頻率遠高於其他鍵,把它放在接近根的位置可以降低期望比較次數。失敗搜尋同樣重要:鍵與鍵之間不同的間隙可能有不同的查詢概率。
我們推導一個區間動態規劃,為已知的查詢權重選出最優樹。狀態同時記錄有序的鍵及其周圍的間隙,遞推式對到達非空子樹根的每個查詢收取一次比較。然後由根表重構出一棵最優樹。
定義
成本約定
定義 2.11.1
(鍵、查詢權重與比較成本約定)
設 為互不相同的有序鍵。成功查詢是搜尋 ,權重為 。失敗查詢落入 個間隙之一: 是低於 的權重,當 時 是嚴格介乎 與 之間的權重, 是高於 的權重。若所有權重之和為一,則下面的目標函數就是鍵比較次數的期望值。該遞推式對任意非負權重(無需歸一化)同樣適用。
一次搜尋在每個到訪的內部節點處,將查詢值與該節點的鍵作比較。失敗搜尋在到達空子節點時結束;該空子節點本身不再進行鍵比較。因此在空樹中,失敗搜尋的比較次數為零。在非空根處的那一次比較,要計入到達該根的每一個成功或失敗查詢。
定義 2.11.2
(區間成本與總權重)
對 ,令 為恰好包含鍵 的樹在這些鍵的成功權重及周圍間隙權重 下的最小加權比較成本。該成本以子樹的根處於比較深度一來量度,忽略該子樹之外的任何祖先。對於空區間,令 。
非空子問題的總權重定義為
定理
定理 2.11.3
(最優搜尋樹遞推式)
對每個非空區間,
的值是最小加權比較成本,而儲存下來的取最小值的根可以重構出一棵最優樹。當 時,在上述約定下空樹的成本為零。
定理 2.11.4
(動態規劃的複雜度)
利用前綴和計算 ,並按區間長度遞增的次序求值,可得在算術/比較模型中時間為 、空間為 的算法。這裏不假設使用任何更快的根搜尋優化。
證明
證明:對根作條件劃分
證明
(對根作條件劃分)
考慮 上的任意一棵搜尋樹,設其根為 。由二叉搜尋性質,左子樹必須恰好包含 ,右子樹必須恰好包含 。相應的間隙權重分為 與 ;對 的成功查詢在根處結束。
該子問題中的每個查詢都在這個根處作一次比較,共貢獻 。其餘的比較則完全發生在相應的子樹中。因此這棵樹的成本為
對於固定的根,兩棵子樹的成本都不可能低於各自區間的最優值,而選取最優子樹即可達到兩者之和。對所有可能的根取最小值,便證明了遞推式。對區間長度作歸納,可確立每一個狀態,包括空的子區間。取得最小值的根與該值一併儲存;遞歸地使用所儲存的根,便得到一棵達到最優值的有序樹。
證明透視
每個查詢在根處恰好計費一次
成功鍵權重與失敗間隙權重在進入非空子樹時都要支付一次比較。該次比較之後,只有被選中的子樹產生進一步的成本。這就把根處的計費與兩個互相獨立的較小區間問題分離開來。唯一不顯然的一點,是左右兩個區間子問題互相獨立:二叉搜尋性質確定每一側有哪些鍵和間隙,因此沒有權重被兩側共用,一側子樹內的成本也不取決於另一側子樹的形狀。論證按區間長度歸納而告完結,因為兩棵子樹都嚴格更短,空區間是基礎情形;最小值有並列並不影響其值。
空區間的基礎值為零,因為到達空子節點不需要再作任何鍵比較。有些教材把外部的啞節點算作額外一次操作,因而採用不同的基礎值與目標函數。兩種約定各自都可以自洽,但若把其中一種的遞推式與另一種的基礎值混用,答案就會改變。
求值與重構
證明
(區間與候選根的計數)
預先計算 與 權重的前綴和,使 能在常數算術時間內求出。共有 個區間。對長度為 的區間,要嘗試其 個可能的根;對所有長度求和 ,得到 次候選求值。把每個成本及一個取得最小值的根分別存入兩張 的表中。
重構時,從 所儲存的根開始,遞歸地重構其左、右區間;空區間給出空子節點。每個鍵成為一個節點,因此重構共產生 個輸出節點,並需要 的額外遍歷工作。若有多個根並列取得最小值,任何一個被記錄的最小值點都給出一棵最優樹。
上述成本模型把加法與比較視為常數時間運算。若有理數權重以二進制編碼,則精確算術以及中間和的位元長度需要另外核算。該分析並不假設應用中的查詢概率已被精確得知;它所說明的,只是對給定的權重哪一棵樹是最優的。
直接的成本檢驗
一棵完整的候選樹可以獨立於動態規劃來求值。對每個成功鍵 ,數出從根到 的路徑上的鍵節點個數,再乘以 。對每個間隙,數出通往相應空子節點的路徑上的鍵節點個數,再乘以該間隙的權重。把這些項相加,得到與遞推式所計費用相同的目標值。在小例子上,這個直接計算可用於檢驗重構所得的樹。
例如,設鍵為 ,根為 ,則第一個鍵與第三個鍵分別是它的左、右子節點。對 或 的每個成功查詢支付兩次比較,而對 的查詢支付一次。四個失敗間隙都到達這兩個子節點之一下方的空子節點,因此都支付兩次比較。加權成本為
遞推式給出同樣的表達式:它在根處把總權重計費一次,然後再把左、右子樹的權重各計費一次。如果從根直接到達的是缺失的子節點,則相應的間隙只需支付根處的那一次比較。
概念視角結構
成本即各子樹權重之和
候選樹的每個鍵節點,恰好與搜尋路徑經過它的那些查詢作比較,而這些查詢正是其鍵或間隙落在該節點子樹所對應區間內的查詢。因此一棵樹的加權成本,等於對它的所有鍵節點 ,把 以下區間的總權重相加,也就是把各子樹所對應區間的 相加。這與上面按深度的計數相同,只是改為逐個節點而不是逐個查詢來計算。對根為 的三鍵樹,三個區間是 、 和 ,而 等於 ;遞推式就是這個和,只是最小化逐個區間進行。
前綴和使權重的計算無需反覆對區間求和。令 ,,並令 ,同時為方便起見約定 。則 。當 時會出現下標 ;這一約定恰好把最左側的間隙 正確地計入。顯式地檢驗只含一個鍵的區間,是發現該公式中差一錯誤的有效辦法。
區間表還避免了在許多候選樹中重複計算同一個子問題。擬定根左側的區間只取決於它的端點,而與其上方的具體祖先無關;那些祖先處的比較已在子問題之外計費。這就是最優子結構的原因:一個儲存下來的值可以代表許多不同的、更大的候選樹。立方時間界是嘗試每一個候選根的最壞情形計數。最終那棵樹中一次搜尋所用的比較次數則是另一個量:它取決於該樹的形狀以及具體的查詢。更高效的預處理算法不會改變最優搜尋成本的定義,而期望成本最優也並不意味著每個查詢都只用對數次比較。
例題詳解
間隙為何改變答案
考慮兩個鍵且沒有成功查詢:,間隙權重為 ,。總權重為一。若 為根,則低於它的查詢在一次比較後即停止;右子樹的權重為 ,所以成本為 。若 為根,則左子樹的權重為 ,所以成本為 。即使沒有任何成功鍵的權重為正,最常見的失敗搜尋間隙仍會影響哪個鍵應當接近根。
這就是為甚麼把失敗查詢當作單一不加區分的概率是不足夠的。低於所有鍵的失敗查詢與高於所有鍵的失敗查詢走的是不同的路徑。間隙恰好是搜尋判定結構的葉子,必須被分配到正確的子問題中。
反例模式
平衡的根未必使期望成本最小
設有三個鍵,成功權重為 ,所有間隙權重為零。選中間的鍵為根,成本為 。選第一個鍵為根並把另外兩個鍵放在它下方,成本為 。僅按鍵的個數作平衡,忽略了實際的查詢負載。
具體例題
例題 2.11.5
(一個鍵)
設只有一個鍵,權重為 ,兩個間隙權重為 ,則每個查詢恰好作一次比較。遞推式給出 。兩個子區間的成本都為零,儘管它們的間隙權重仍然計入根處的費用。
例題 2.11.6
(含混合查詢的兩個鍵)
取 ,,。總權重為一。以 為根,右子問題的權重為 ,成本為 。以 為根,左子問題的權重為 ,成本為 。最優的根是 。
例題 2.11.7
(權重為零的查詢類)
若每個 與 都為零,則每棵樹的加權成本都為零。遞推式容許任意的並列,可以記錄任何一個根。權重為零並不表示該鍵從樹中移除;它只表示該鍵的查詢對這一目標函數不產生成本。
例題 2.11.8
(空樹)
若 ,則不存在鍵比較。即使唯一的失敗查詢權重 為一,在我們的約定下成本仍為零,因為搜尋立即到達空樹。若採用另一種約定,對檢查啞葉子也收費,則計的是另一個量。
常見錯誤
常見錯誤
(把間隙分給錯誤的子樹)
當 為根時,間隙 屬於右子樹,間隙 屬於左子樹。它們描述的是不同範圍的查詢值。仔細劃分間隙,可避免某個權重被遺漏或被兩個子樹重複計入。對根為 的兩個鍵,左子問題是帶有間隙 的 ,右子問題為空,其間隙為 。
常見錯誤
(在根處只計根鍵的權重)
根處的費用是到達該子問題的所有查詢的權重,而不僅僅是根鍵的成功權重。失敗查詢同樣要與其搜尋路徑上的每個鍵作比較。空子節點的基礎值為零,只是因為該子節點不再增加任何鍵比較。在上面的兩鍵例子中,根為 時,根處的費用是全部權重 ,而不是 。
常見錯誤
(把最優值當作保證)
最後,最優樹依賴於所給的權重與成本約定。它並不聲稱這些權重能準確預測未來的訪問量,也不聲稱使期望比較次數最小就能使最壞情況深度最小。平衡樹與加權最優樹解決的是不同的目標。若工作負載隨時間變化,就應當重新考慮所給的權重,以及重建這棵樹的成本。
總結
對每個鍵區間,嘗試每一個可能的根。該區間內的全部查詢權重都要支付一次根處的比較,隨後兩個子區間各自貢獻互相獨立的最優成本。前綴和與按長度遞增的求值次序給出立方時間的動態規劃,而儲存的根可復原出一個見證。間隙權重以及空子節點的約定對結果至關重要。
練習
快速檢查
(對只有一個鍵、 且 的情形,計算最優成本。)
每個查詢都會到達唯一的節點。
解答 · 答案
每個查詢都訪問這唯一的鍵,所以平均成本為 次比較。
快速檢查
(對兩個鍵,,,三個間隙的權重均為 ,計算以每個鍵為根時的成本。)
把每個根之下剩餘子樹的權重加到總權重上。
解答 · 答案
總權重為一。以 為根,右子樹權重為 ,成本為 ;以 為根,左子樹權重為 ,成本為 。
快速檢查
(解釋為甚麼即使相應的間隙權重為正,仍有 。)
想一想失敗查詢在到達空子節點之前作了哪些比較。
解答 · 答案
失敗查詢在到達這個空子節點之前,已經為每個祖先鍵的比較付過費。空子樹不含任何可供比較的鍵,在上述約定下不貢獻任何額外比較。
快速檢查
(對三個鍵,成功權重為 ,間隙權重為零,比較以中間鍵為根的成本,與以第一個鍵為根、然後第二個鍵為其子節點的樹的成本。)
分別計算兩棵樹中每個鍵的深度。
解答 · 答案
以中間鍵為根的成本為 。以第一個鍵為根、第二個鍵為其子節點的樹,成本為 。這個例子說明,按鍵的個數作平衡,對所給的權重未必是最優的。