AA 樹

AA 樹是一種用於高效存儲和檢索有序數據的平衡樹形結構，Arne Andersson 教授於 1993 年在他的論文 "Balanced search trees made simple" 中介紹，設計的目的是減少紅黑樹考慮的不同情況。AA 樹可以在 \(O(\log N)\) 的時間內做查找，插入和刪除。下面是一個 AA 樹的例子。

AA 樹是紅黑樹的一種變體，與紅黑樹不同，AA 樹上的紅色節點只能作為右子節點。這導致 AA 樹模擬了 2-3 樹而不是 2-3-4 樹，從而極大地簡化了維護操作。紅黑樹的維護算法需要考慮七種不同的情況來正確平衡樹。

因為紅色節點只能作為右子節點，AA 樹只需要考慮兩種情況。

定義

AA 樹遵循與紅黑樹相同的規則，但添加了一條新規則，即紅色節點不能作為左孩子出現。

1. 每個節點都可以是紅色或黑色。
2. 根節點總是黑色。
3. 葉節點（NULL）總是黑色。
4. 紅色節點的兩個子節點必須都是黑色，即沒有兩個相鄰的紅色節點。
5. 從根節點到 NULL 節點的每條路徑都有相同數量的黑色節點。
6. 紅色節點只能作為右子節點。

平衡維護

AA 樹的每個節點維護一個 level 字段，類似紅黑樹的每個節點維護一個 color 字段 ("RED" or "BLACK")。level 的規定滿足以下 5 個條件：

1、每個葉節點的 level 是 1。

2、每個左孩子的 level 是其父節點的 level 減 1。

3、每個右孩子的 level 等於其父節點的 level 或等於其父節點的 level 減 1。

4、每個右孫子的 level 嚴格小於其祖父節點的 level。

5、每個 level 大於 1 的節點有兩個孩子。

水平鏈接（Horizontal Link）

子節點的 level 等於父節點的 level 的鏈接被稱為 水平鏈接，類似於紅黑樹中的紅鏈接。允許單獨的右水平鏈接，但不允許連續的右水平鏈接；不允許左水平鏈接。這些限制比紅黑樹的限制更加嚴格，因此 AA 樹的平衡過程比紅黑樹的平衡過程在程序上要簡單得多。

插入和刪除操作可能會暫時導致 AA 樹失去平衡（即違反 AA 樹的不變性）。恢復平衡只需要兩種不同的操作："skew"（斜化）和"split"（分裂）。"Skew"是將一個包含左水平鏈接的子樹進行右旋轉，以替換為一個包含右水平鏈接的子樹。"Split"是進行左旋轉並增加 level，以替換一個包含兩個或更多連續的右水平鏈接的子樹，使其變為一個包含兩個較少連續的右水平鏈接的子樹。保持平衡的插入和刪除的實現通過依賴"skew"和"split"操作來僅在需要時修改樹，而不是由調用者決定是否進行"skew"或"split"，從而變得更加簡化。

split（左旋）

出現連續向右的水平方向鏈（連續三個向右的孩子屬於同一 level，節點 R 和節點 X 都是紅色節點）。

此時向左旋轉節點T，把小於等於此 level 的節點看做一個子樹。

1. 子樹的根的右孩子變為新的子樹根；
2. 原來的子樹根變為新子樹根的左孩子；
3. 新的子樹根 level+1。

偽代碼實現

\[ \begin{array}{ll} 1 & \textbf{function } \text{split}(\text{root}) \\ 2 & \qquad \textbf{if } \text{root}\rightarrow\text{right}\rightarrow\text{right}\rightarrow\text{level} == \text{root}\rightarrow\text{level} \\ 3 & \qquad\qquad \text{rotate\_left}(\text{root}) \\ 4 & \textbf{end function} \end{array} \]

skew（右旋）

出現向左的水平方向鏈（連續兩個向左的孩子屬於同一 level）

向右旋轉節點T，把小於等於此 level 的節點看做一個子樹。

1. 子樹的根的左孩子變為新的子樹根；
2. 原來的子樹根變為新子樹根的右孩子。

偽代碼實現

\[ \begin{array}{ll} 1 & \textbf{function } \text{skew}(\text{root}) \\ 2 & \qquad \textbf{if } \text{root}\rightarrow\text{left}\rightarrow\text{level} == \text{root}\rightarrow\text{level} \\ 3 & \qquad\qquad \text{rotate\_right}(\text{root}) \\ 4 & \textbf{end function} \end{array} \]

AA 樹的操作

AA 樹本身是一棵二叉搜索樹，所以搜索操作與其他二叉搜索樹相同。插入和刪除操作與AVL樹相同，首先在樹中將 key 插入或刪除，然後沿着搜索路徑回退到根，並在此過程中重構樹。

插入

偽代碼實現

\[ \begin{array}{ll} 1 & \textbf{function } \text{insert}(\text{root}, \text{add}) \\ 2 & \qquad \textbf{if } \text{root} == \text{NULL} \\ 3 & \qquad\qquad \text{root} \gets \text{add} \\ 4 & \qquad \textbf{else if } \text{add}\rightarrow\text{key} < \text{root}\rightarrow\text{key} \qquad //如果允許重複<= \\ 5 & \qquad\qquad \text{insert}(\text{root}\rightarrow\text{left}, \text{add}) \\ 6 & \qquad \textbf{else if } \text{add}\rightarrow\text{key} > \text{root}\rightarrow\text{key} \\ 7 & \qquad\qquad \text{insert}(\text{root}\rightarrow\text{right}, \text{add}) \\ 8 & \qquad \textbf{end if} \\ 9 & \qquad \text{//如果不允許重複，在每一level上進行skew和split} \\ 10 & \qquad \text{skew}(\text{root}); \\ 11 & \qquad \text{split}(\text{root}); \\ 12 & \textbf{end function} \end{array} \]

刪除

刪除過程與其他二叉平衡樹類似，首先將內部節點的刪除轉換為葉子節點的刪除。具體方法是將內部節點與它最接近的前驅或後繼節點替換。由於 AA 樹的所有 level 大於 1 的節點都有兩個子節點，前驅或後繼節點將位於 level 1，刪除 level 1 的節點較為簡單。

偽代碼實現

\[ \begin{array}{ll} 1 & \text{//To rebalance the tree} \\ 2 & \textbf{if} \ \text{root->left->level} < \text{root->level} -1 \ \textbf{or} \ \text{root->right->level} < \text{root->level} -1 \\ 3 & \{ \\ 4 & \qquad \textbf{if} \ \text{root->right->level} > \text{--root->level} \\ 5 & \qquad \{ \\ 6 & \qquad\qquad \text{root->right->level} \gets \text{root->level} \\ 7 & \qquad \} \\ 8 & \qquad \text{skew}(\text{root}) \\ 9 & \qquad \text{skew}(\text{root->right}) \\ 10 & \qquad \text{skew}(\text{root->right->right}) \\ 11 & \qquad \text{split}(\text{root}) \\ 12 & \qquad \text{split}(\text{root->right}) \\ 13 & \} \\ \end{array} \]

性能

AA 樹的性能與紅黑樹的性能相當。儘管 AA 樹進行的旋轉操作比紅黑樹多，但 AA 樹的算法更簡單，最終導致相近的性能。紅黑樹的性能在各種情況下更加一致，而 AA 樹往往更扁平，這使 AA 樹有稍快的搜索速度。

參考資料

1. AA tree - Wikipedia
2. Introduction to AA trees

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用