二叉搜尋樹可以按比較結果尋找鍵,但一般排序不變量不會直接告訴我們一個節點下面有多少個鍵。每個節點多儲存一個數字,便可搜尋第五小的鍵;但更新操作必須維持該數字的意義。
1. 定義擴充數據
定義 4.1.1
(子樹大小與排名)
假設二叉搜尋樹有限且鍵值互不相同:左子樹的每個鍵小於節點的鍵,右子樹的每個鍵則較大。每個節點 儲存其整棵子樹(包括自身)的節點數 ;空子樹記作 。局部規則為
鍵 在樹中的排名是 加上樹中小於 的鍵的個數;第 小的鍵就是排名為 的鍵。
排名從 1 開始。以下操作要求 ;搜尋前須拒絕超出範圍的排名。特別是空樹沒有有效排名。鍵值互異令「第 小的鍵」沒有歧義;若允許重複值,須明確規定重數及相應計數,本節不暗中涵蓋該情況。
2. 選取算法
在當前節點,令 為左子樹的儲存大小。該節點在其子樹中恰有 個鍵排在它之前,所以局部排名是 。
select(root, k): // precondition: 1 <= k <= size(root)
x = root
while x is not empty:
L = size(x.left)
if k == L + 1: return x.key
if k <= L:
x = x.left
else:
k = k - (L + 1)
x = x.right
定理 4.1.2
(排名選取的正確性與成本)
設 是鍵值互異的二叉搜尋樹,其儲存的大小滿足局部規則,且 。則 select(root, k) 返回 中第 小的鍵。若 是以邊數計的高度,它最多檢查 個節點。
證明
(關於當前排名的迴圈不變量)
斷言:每次進入迴圈時,x 非空、,且要返回的鍵是以 x 為根的子樹中第 小的鍵。第一次進入時,由前置條件,這正是調用者的要求。
設斷言在某次進入時成立,並令 。由排序性質,該子樹的鍵依次是:左子樹的 個鍵、x 的鍵、右子樹的鍵。若 ,答案就是 x 的鍵,並被返回。若 ,則 ,左子節點非空,,而該子樹第 小的鍵就是左子樹第 小的鍵。若 ,則 ,且 ;所以右子節點非空,答案是它第 小的鍵。兩種下降情況下,斷言在下一次進入時對 x 的某個子節點成立。每一步下降一層,因此迴圈至多進入 次;又因為 x 一直非空,迴圈只能由 return 結束。
證明透視
為何迴圈不會離開這棵樹
論證靠兩件事。第一,二叉搜尋樹的次序使子樹內的排名分成連續三塊:左邊的鍵、該節點、右邊的鍵,所以排名可以換算成某個子節點中的排名。第二,儲存的大小在證明中用了兩次: 用來定位這三塊,而 說明換算後的排名仍在範圍內。若某個儲存的大小已過時,第二個不等式可能失效,下降便可能到達空子節點。鍵值互異也有用:若有重複鍵,「第 小的鍵」就不能確定單一節點。
若高度 按最長根到葉路徑的邊數計算,最多檢查 個節點。故選取時間為 、額外空間為 ;整棵 節點樹的大小欄位使用 儲存空間。不平衡樹可能有 ,因此對數時間還需要額外的平衡保證。
反例模式
不檢查排名就執行 select
斷言:無論 是甚麼,迴圈都會返回一個鍵。取下一節的七節點樹及 。在 16, 且 ,所以 變成 , 變成 24。在 24, 且 ,所以 變成 , 變成 31。在 31, 且 ,所以 變成 , 變成空的右子節點;迴圈結束,卻沒有任何 return。對 ,路徑 16、7、3 同樣在 3 的空左子節點結束。修正辦法就是所述前置條件:搜尋開始前,拒絕所有 或 的排名。
3. 例子
考慮以下互異鍵樹;括號內是儲存的子樹大小:
16(7)
/ \
7(3) 24(3)
/ \ / \
3(1) 11(1) 20(1) 31(1)
例題 4.1.3
(七節點樹中的排名 5)
求排名 。在 16,左子樹大小為 3,跳過這三個鍵及 16;接著在右子樹尋找排名 。在 24,左子樹大小為 1,故排名不變往左走。在 20,左子樹大小為 0,,因此返回 20。中序序列為 3, 7, 11, 16, 20, 24, 31,可獨立檢查結果。
例題 4.1.4
(最小鍵、最大鍵與根)
:在 16,左子樹大小為 3 且 ,向左;在 7,左子樹大小為 1 且 ,向左;在 3,左子樹大小為 0,,返回 3,即最小鍵。:在 16,,所以 變成 ,向右;在 24,,所以 變成 ,向右;在 31,,返回 31,即最大鍵。 時根節點立即回答,因為 ;中序序列也顯示第四個鍵是 16。
4. 修改樹後維持大小
把新互異鍵插入為葉節點後,令其大小為 1,再由下往上重新計算搜尋路徑上每個祖先的大小。若拒絕重複鍵插入,樹與計數都不變。刪除時同樣要重新計算實際移除所影響的所有祖先。特別是雙子節點刪除若以複製中序後繼的鍵、再移除後繼節點實作,須由被移除節點的原父節點向上重新計算,適用時包括目標節點。後繼恰為目標的直接右子節點也包括在內:此時其原父節點就是目標。這是單次操作的更新規則,不表示可讓並行讀取者看到複製鍵的中間狀態。
旋轉保留中序鍵序列,卻會改變兩棵局部子樹包含的節點。對 x 及其右子節點 y 進行左旋後,先用新子節點重新計算 s(x),再算 s(y)。此局部旋轉下,更高祖先的後代集合不變。平衡算法可以使用這些局部更新;本節沒有證明任何平衡算法,也不保證對數高度。
例題 4.1.5
(在根作左旋後的大小)
在七節點樹中,對 x = 16 及其右子節點 y = 24 左旋。於是 24 成為根,16 是其左子節點,24 原來的左子節點 20 成為 16 的右子節點;16 的左子節點 7(3) 不變。先重新計算 s(16)=1+3+1=5,再計算 s(24)=1+5+1=7。中序序列仍是 3, 7, 11, 16, 20, 24, 31。現在選取排名 5:在 24, 且 ,向左;在 16, 且 ,所以 變成 ,向右;在 20,,返回 20,與之前相同。
常見錯誤
(向右走時只跳過左邊的鍵)
當 ,被跳過的鍵是左邊 個鍵加當前鍵,所以新排名是 。只減去 會令排名大了一。在七節點樹中取 ,根節點會帶我們以排名 向右;在 24, 且 ,程式碼便會返回 24。正確答案是 20。
常見錯誤
(旋轉後以錯誤的次序重新計算大小)
上述左旋之後,16 是較低的節點,24 是較高的節點。24 的大小取決於 16 的新大小。若先重新計算 s(24),就會用上已過時的 ,得出 ,而不是 。應先重新計算較低的節點,再算較高的節點。
5. 檢查與練習
快速檢查
(在例子樹中插入 18 並更新大小。之後排名 6 返回甚麼?)
沿 18 的搜尋路徑,由下往上重新計算。
解答 · 答案
路徑是 16 -> 24 -> 20;18 成為 20 的左子節點。20、24、16 的新大小分別是 2、4、8。此時排名 6 返回 20,因為中序序列是 3, 7, 11, 16, 18, 20, 24, 31。
快速檢查
(原七節點樹的排名 0 或 8 有甚麼意義?)
對照 select 的前置條件。
解答 · 答案
按從 1 開始的規約,兩者均無效;應拒絕,而非返回可能被誤認為鍵值的哨兵。
快速檢查
(為何一般 BST 排序不變量不足以保證所述複雜度?)
想一想算法在每個節點必須知道甚麼。
解答 · 答案
沒有儲存大小時,求 可能要數遍很大的子樹;有了大小,在一般指標模型下每層的排名決策只需常數工作。
快速檢查
(解釋為何同一組鍵可構成不同高度的 BST。)
想一想鍵的插入次序。
解答 · 答案
把已排序的互異鍵插入普通不平衡 BST 可能形成鏈;按排名選取仍正確,但可能逐一訪問線性數量的節點。
局部不變量與成本分析假設計數初始化正確,且操作期間沒有並行修改。