二叉搜尋樹每比較一次,就可以排除其中一棵子樹,從而回答有序集合的查詢。這聽來很有效率,但比較次數其實取決於樹的高度。若依次把 插入一棵普通空搜尋樹,每個新鍵都成為上一個鍵的右子節點。搜尋 5 便要遍歷全部五個節點。只有次序規則,並不足以令樹保持低矮。
AVL 樹額外要求每個節點附近的兩棵子樹高度相差不多。它的價值在於:一個可以在更新路徑上檢查及修復的局部條件,竟能保證整棵樹的高度界。本節先證明這一點,再分清旋轉的兩項工作:保留樹所儲存的鍵,以及恢復高度條件。刪除尤其需要小心,因為一次成功修復可能令子樹變矮,繼而令更高的祖先失衡。
先說清楚有序集合的操作約定
假設所有鍵互不相同,並具有固定的全序。每個節點儲存一個鍵、兩個子指標,以及其子樹高度。插入已存在的鍵時,集合不變;刪除不存在的鍵時,集合也不變。映射還會儲存與每個鍵相聯的值,但我們先研究集合介面。
定義 15.1.1
(搜尋次序、高度與 AVL 平衡)
在鍵為 的節點,左子樹的每個鍵都小於 ,右子樹的每個鍵都大於 。兩棵子樹亦各自遞歸滿足同一條件。這就是二叉搜尋樹不變量。
高度以邊數計算:空子樹的高度為 ,葉節點的高度為 0。對非空節點 ,
定義其平衡因子為
若二叉搜尋樹的每個節點均滿足 ,它就是一棵 AVL 樹。
定義亦不要求每一層都填滿。在每個節點比較的是兩棵子樹的高度,不是鍵的數目。
常見錯誤
(只檢查根的平衡)
樹 10(5(4(3,-),-),15(12,-)) 的根平衡因子為 ,因為左子樹高度為 2、右子樹高度為 1。它卻不是 AVL 樹:節點 5 的左高度為 1、右高度為 ,平衡因子為 2。
若根的高度為 ,搜尋最多遍歷 個非空節點,之後或會到達一個空子指標。因此,我們只需用儲存的鍵數 來限制 。
為何局部平衡能保證對數高度
令 表示高度恰為 的 AVL 樹所需的最少節點數。初始值為 、。高度為 的樹,至少有一棵子樹的高度為 ;平衡條件要求另一棵的高度至少為 。選取這兩種高度各自最小的 AVL 子樹,確實能達到最少節點數,所以對 ,
| 高度 | |||||||
|---|---|---|---|---|---|---|---|
| 最少節點數 |
這與 Fibonacci 遞歸式相似。但要證明對數高度,我們不必先求出它的閉式公式。
定理 15.1.2
(AVL 樹的對數高度)
含 個鍵的 AVL 樹,高度滿足 。特別地,搜尋最多遍歷 個節點。
證明
(不解遞歸式,也能得到高度界)
設 。當 ,遞歸式變成
因為 隨高度增加。初始值滿足 、。每次把高度減二作歸納,可得
一棵有 個節點、高度為 的 AVL 樹滿足 ,所以
因此搜尋時間為 。這個界刻意取得較寬鬆;目的在於直接從平衡不變量證明高度呈對數增長。
證明透視
為甚麼要加一,又為甚麼一次減二
令 去掉了遞歸式中多出的常數,於是 成為純粹的加法關係。一次減二是由假設決定的:平衡只保證較矮的子樹高度至少為 ,並不保證 ;若把 用兩次,便要求兩棵子樹的高度都是 ,這只有完全平衡的形狀才成立。
平衡假設不能刪去。按 的遞增次序插入所得的搜尋樹是一條鏈,、高度為 ,而 AVL 樹必須滿足 。
證明亦說明更新必須保留甚麼。不能只憑某個小例子的樹形看來緊湊,就認定算法正確:高度界所依賴的不變量,必須在每個節點繼續成立。
旋轉保留整個有序集合
假設節點 的左子節點為 。用 代表整棵子樹,當中可以有空子樹。右旋轉改變以下指標:
z y
/ \ / \
y C becomes A z
/ \ / \
A B B C
中間子樹 從 的右側移到 的左側。不能把它丟失,也不能讓它同時保留在兩個位置。圖中子樹若還有父節點,其指標現在必須改為指向新根 。
命題 15.1.3
(旋轉保留搜尋次序)
設 是二叉搜尋樹的根,其左子節點為 , 如圖所示。右旋轉所得的仍是同一組鍵上的二叉搜尋樹,中序序列不變,並且可以取代任何較大搜尋樹內的原子樹。
證明
(旋轉前後的中序序列相同)
旋轉前,搜尋次序給出
若某棵子樹為空,略去涉及其鍵的比較。這些不等式同樣支持旋轉後的每個位置: 應在 左側; 應在 右側、 左側; 應在 右側。
也可以看中序序列:兩邊都是 。沒有新增、遺失或重複任何鍵,因此旋轉後的子樹表示同一個有序集合。它對外所須滿足的鍵值上下界亦不變,所以可以在一棵更大的搜尋樹內取代原子樹。
這證明了搜尋次序得以保留。旋轉是否恢復 AVL 平衡,仍取決於子樹的高度;不能單靠次序證明第二件事。
左旋轉就是左右對稱的操作。兩者都只修改常數個指標。更新高度時,先更新位置較低的舊根,再更新新根;第二次計算要使用第一次更新後的高度。
依子節點的平衡因子選擇修復
經過一次插入或刪除,並完成某節點下方的修復後,該節點的平衡因子只可能是 或 2。若為 2,便是左子節點 太高。當 ,一次右旋轉就足夠;當 ,先左旋轉 ,再右旋轉原根。這個雙旋轉會把中間的鍵帶到上方。右側過高的情況則左右對稱。
| 的平衡因子 | 較高子節點的平衡因子 | 修復方式 |
|---|---|---|
| 右旋轉 | ||
| 先左旋轉左子節點,再右旋轉 | ||
| 左旋轉 | ||
| 先右旋轉右子節點,再左旋轉 |
例題 15.1.4
(兩種插入形狀需要不同修復)
依次插入 30、20、10。在 30 處,左子樹高度變成 1,右側空子樹高度為 ,所以平衡因子為 2。其左子節點 20 的平衡因子為 1。一次右旋轉得到根 20、左右葉節點 10 和 30,全部平衡。
改為依次插入 30、10、20。30 的平衡因子仍為 2,但其子節點 10 的平衡因子為 。若立即右旋轉 30,新根 10 的右子樹高度會是 1,左子樹卻為空,仍然失衡。應先左旋轉 10,把 20 帶到它上方,再右旋轉 30。最後同樣得到根 20、左右子節點 10 和 30。
兩例最終的有序集合相同。決定修復方式的是中途的子節點平衡因子,而不是所儲存的鍵集合。
命題 15.1.5
(插入後的修復恢復原有子樹高度)
設 是新插入節點由下而上第一個平衡因子變成 的祖先(若有的話)。依上表選擇的單旋轉或雙旋轉,使修復後子樹的每個節點都平衡,而且其高度等於插入前以 為根的子樹高度。因此 的祖先不會因這次插入而改變高度或平衡因子。
證明
(單旋轉與雙旋轉之後的高度)
對插入而言,設 是由下而上第一個失衡的祖先。插入前,它較高的子樹高度為 ,另一棵為 。插入令較高子樹升至 。在左左型情況,沿用上方旋轉圖的記號:插入後 的高度為 , 和 的高度均為 。右旋轉令 的高度變成 ,新根 的高度則為 。
在左右型情況,設 是插入後 的右子樹的根。 的高度為 ,其兩個子節點高度均不超過 。外側兩棵子樹,即 左方及 右方的子樹,高度均為 。雙旋轉令 和 成為 的子節點。兩者現在的高度均為 ,所以新根 的高度為 。右側較高的情況則左右對稱。
兩種修復因此都恰好恢復插入前的子樹高度。 上方的祖先看不到淨高度增加。一次單旋轉或雙旋轉修復就足夠,但找出插入位置及更新高度,仍要走過一條對數長度的路徑。
刪除可能截斷,也可能傳遞高度變化
普通搜尋樹的刪除,最終會移除一個最多只有一個子節點的節點。若指定節點有兩個子節點,先把其中序後繼的鍵複製過來,再從右子樹刪除該後繼。後繼是右子樹中最小的鍵,故沒有左子節點。搜尋次序仍然成立,而集合恰好失去指定的鍵。若是映射,必須連同鍵一起複製其關聯值。
沿真正被移除的節點到根的路徑返回時,逐層修復。不能以被刪鍵的舊位置判斷旋轉;必須檢查目前較高子節點的平衡因子。
例題 15.1.6
(較高子節點的平衡因子為零時,應作單旋轉)
起初根為 4;左子樹的根為 2,兩個葉子為 1 和 3;右子樹的根為 6,右側還有葉子 7。整棵樹高度為 2。先刪除 7,令 6 成為葉節點;根 4 的平衡因子為 1,仍然平衡。
現在刪除 6。在根 4 處,子樹高度為 1 和 ,平衡因子變成 2。其左子節點 2 的平衡因子是零。右旋轉 4:
4 2
/ / \
2 becomes 1 4
/ \ /
1 3 3
旋轉後,節點 4 的高度為 1、平衡因子為 1;節點 2 的高度為 2、平衡因子為 。所有節點都平衡。修復後的子樹高度仍為 2,等於刪除 6 之前的高度。如果上方還有祖先,它不會看到高度下降,所以這次修復會截斷高度變化的向上傳遞。
平衡因子為零的子節點會在刪除中出現,因此修復表須使用 及 。若只記住插入時新鍵的方向,便容易漏掉此情況。
其他刪除修復會降低子樹高度,於是祖先也可能失衡。
例題 15.1.7
(一次刪除令兩個祖先都要旋轉)
記號 k(left,right) 表示根為 k,- 表示空子節點,單獨一個鍵則表示葉節點。起始樹為
8(5(3(2(1,-),4),7(6,-)),11(10(9,-),12))
它是一棵包含鍵 1 至 12 的 AVL 樹。左子樹高度為 3、右子樹高度為 2,根的高度為 4。刪除葉節點 12。在節點 11 處,左高度為 1、右高度為 ;右旋轉 11 後得到 10(9,11)。這棵子樹的高度從 2 降至 1。根 8 現在的兩個子樹高度為 3 和 1,也需要修復。其左子節點 5 的平衡因子為 1;右旋轉 8 後得到
5(3(2(1,-),4),8(7(6,-),10(9,11)))
最後高度為 3。一次刪除令兩個不同的祖先需要旋轉。若修復第一個節點後便停止,根 8 仍會失衡。
傳回修復後的新根,並局部維護高度
以下 Python 程式明確寫出指標與高度的更新規則。insert 和 erase 傳回可能已改變的根,調用端必須保留它,例如 root = erase(root, key)。鍵的比較必須構成一致的全序。程式不會遞歸走遍子樹以重新計算高度;refresh 只讀取兩個子節點儲存的高度。
class Node:
def __init__(self, key):
self.key = key
self.left = self.right = None
self.height = 0
def height(v):
return -1 if v is None else v.height
def refresh(v):
v.height = 1 + max(height(v.left), height(v.right))
def balance(v):
return height(v.left) - height(v.right)
def rotate_right(z):
y = z.left
z.left = y.right
y.right = z
refresh(z)
refresh(y)
return y
def rotate_left(z):
y = z.right
z.right = y.left
y.left = z
refresh(z)
refresh(y)
return y
def rebalance(v):
refresh(v)
if balance(v) == 2:
if balance(v.left) < 0:
v.left = rotate_left(v.left)
return rotate_right(v)
if balance(v) == -2:
if balance(v.right) > 0:
v.right = rotate_right(v.right)
return rotate_left(v)
return v
def insert(v, key):
if v is None:
return Node(key)
if key < v.key:
v.left = insert(v.left, key)
elif key > v.key:
v.right = insert(v.right, key)
else:
return v
return rebalance(v)
def erase(v, key):
if v is None:
return None
if key < v.key:
v.left = erase(v.left, key)
elif key > v.key:
v.right = erase(v.right, key)
else:
if v.left is None:
return v.right
if v.right is None:
return v.left
successor = v.right
while successor.left is not None:
successor = successor.left
v.key = successor.key
v.right = erase(v.right, successor.key)
return rebalance(v)
旋轉程序要求圖中相應的子節點存在;rebalance 的平衡條件保證這項要求。此外,rebalance 假設兩棵子樹已是 AVL 樹、高度數據正確,而目前節點是經過一次普通更新後到達的狀態。它修復的是這種情況,並非用來平衡任意損壞的樹。
常見錯誤
(丟掉傳回的根)
對 20(10,30(-,40)) 執行 erase(root, 10),節點 20 失去左葉節點後,右子樹比左子樹高 2,所以會傳回新根 30,得到 30(20,40)。若調用端只寫 erase(root, 10) 而不接收傳回值,root 仍指向節點 20;它現在是 30 的左子節點,沒有右子樹,從它出發無法到達鍵 30 和 40。應寫成 root = erase(root, 10)。
每個返回中的遞歸框架只作常數工作,最多兩次旋轉。原樹的高度為對數級,所以插入及刪除的最壞時間均為 ,包括搜尋後繼所需的時間。遞歸堆疊使用 空間,全部節點則佔 空間。刪除可以修復多個祖先,但路徑上總共只有對數個祖先。
反例模式
局部看來正確,不代表整棵樹正確
在兩個祖先連鎖修復的例子中,假設程式修復節點 11 後便停止。以 10 為根的右子樹是一棵正確的 AVL 樹。整棵結構的中序遍歷仍然有序,也恰好包含應有的鍵。然而,根 8 的平衡因子是 2。只檢查鍵是否排序,便會漏掉這個錯誤。
必須分開檢查三件事:鍵的次序正確;每個儲存高度等於一加兩個子高度的最大值;每個平衡因子的絕對值不超過一。即使所有指標都正確,過時的高度仍可能掩蓋失衡。這三項斷言對應不同的數學責任。
練習與詳解
快速檢查
(1. 一致使用高度約定)
一棵 AVL 樹儲存十個鍵。其高度可以是 4 嗎?可以是 3 嗎?使用最少節點數遞歸式,而不是較寬鬆的對數上界。
解答 · 解答 1
高度 4 不可能,因為 。高度 3 則可以。完整的高度 2 樹有七個節點,在下一層的可用位置加入三個子節點,並保持各處平衡即可。例如 4(2(1,3),8(6(5,7),9(-,10))) 有十個鍵、高度為 3,每個節點的平衡因子絕對值均不超過一。
快速檢查
(2. 找出旋轉中的中間子樹)
右旋轉前,根 40 的左子節點為 20,而 20 的右子樹以 30 為根。旋轉後,這棵子樹應接到哪裏?哪些鍵值不等式支持這個移動?
解答 · 解答 2
它成為 40 的左子樹,而 40 成為 20 的右子節點。被移動子樹的每個鍵都嚴格介於 20 與 40 之間,所以旋轉前後都應位於 20 右側、40 左側。若仍把它留在原來的子指標位置,又把 40 接到同一位置,便會遺失子樹或破壞樹的連結。
快速檢查
(3. 追蹤右左型插入)
向空 AVL 樹依次插入 10、30、20。指出第一個失衡節點、兩個相關的平衡因子、旋轉次序及最終高度。
解答 · 解答 3
節點 10 的平衡因子為 ,其右子節點 30 的平衡因子為 1。先右旋轉 30,再左旋轉 10。最後根為 20,葉子為 10 和 30,高度為 1。只在原根作一次左旋轉並不足夠。
快速檢查
(4. 刪除有兩個子節點的節點)
在 20(10,30(25,40)) 中,以中序後繼方法刪除 20。用哪個鍵取代它?真正被移除的是哪個節點?完成所需平衡檢查後,樹形如何?
解答 · 解答 4
後繼為 25。把 25 複製到根,再從右子樹移除原來的葉節點 25。結果是 25(10,30(-,40)),高度為 2。根 25 的平衡因子為 ,節點 30 的平衡因子為 ,葉節點均為 0,因此毋須旋轉。集合失去 20,而 25 仍恰好只出現一次。
快速檢查
(5. 為何一次刪除修復未必完成工作?)
在十二個鍵的刪除例子中,剛修復節點 11 後,根 8 的兩個子樹高度分別是多少?為何遞歸返回時必須繼續對根 8 作平衡修復?
解答 · 解答 5
左高度仍為 3,修復後的右子樹高度則為 1,所以根 8 的平衡因子為 2。第一次旋轉保留了次序,也修復了自己的子樹,但同時令該子樹變矮,沒有修復祖先因此出現的失衡。第二次右旋轉才在該處恢復 AVL 平衡,得到最終根 5。
快速檢查
(6. 分清常數高度更新與遞歸量度)
為何程式在每個節點儲存高度?如果 refresh 改為每次返回時遞歸計算整棵目前子樹的高度,單憑對數高度界還能證明更新時間為對數級嗎?
解答 · 解答 6
讀取已儲存的子高度,令每次更新只需常數時間;返回框架數量為對數級,總工作量才是對數級。若在根上遞歸量度高度,單是這次量度已可能遍歷全部 個節點。因此,樹高為對數級將不足以推出更新時間為對數級。結構界限制框架數量;實作還必須限制每個框架內的工作量。