AVL 樹：插入與搜尋

題目敘述

建立一棵支援插入與搜尋的 AVL 樹。每次插入之後都要用旋轉維持高度平衡，讓搜尋保持 O(log n)。

AVL 樹是一種二元搜尋樹，每次更新後會用旋轉來恢復平衡：任何節點的左、右子樹高度相差都不超過 1，所以即使鍵值依序插入，樹也不會退化成一條鏈。

請提交 avl.h 與 avl.c，實作下列介面（嚴格高度平衡的 AVL 二元搜尋樹）：

typedef struct avl avl;
void avl_init(avl *t);
void avl_insert(avl *t, int key);
int avl_search(avl *t, int key);
void avl_erase(avl *t, int key);
void avl_inorder(avl *t); /* ascending keys, one line */
int avl_height(avl *t); /* empty tree height 0 */

每次 insert 或 erase 之後，整棵樹都必須維持 AVL 平衡。

輸入格式

測試程式（driver）從標準輸入讀取操作並呼叫你的函式。

• 第一行為整數 Q，表示操作數量。
• 接下來 Q 行，每行是下列其中一種操作：
• insert x：插入整數鍵值 x
• search x：若 x 存在則印出 1，否則印出 0
• erase x：若鍵值 x 存在就刪除它（不輸出）
• inorder：以升冪印出所有鍵值，以空白分隔，印在同一行
• height：印出樹的高度（空樹高度為 0）
• 本題以 insert 與 search 為主，但其他操作仍可能出現。

輸出格式

依序輸出每個 search、inorder、height 操作的結果，每個結果各占一行；insert 與 erase 不輸出。

限制

• 1 ≤ Q ≤ 501（高度壓力測試：500 次插入再加一次查詢）
• 產生的壓力測試中，鍵值為 [1, 1000] 內的整數
• 循序壓力測試依序插入鍵值 1, 2, …, 500

行為規範

• avl_init 之後的空樹：高度為 0，所有 search 回傳 0，inorder 印出一個空行。
• 重複插入已存在的鍵值時不做任何事（鍵值不重複）。
• 對不存在的鍵值做 search 要印出 0；做 erase 則什麼都不改變。
• 每次 insert 或 erase 之後，樹都必須滿足 AVL 平衡條件。

時間複雜度

每次 insert 與 search 都應在 O(log n) 時間內完成。

範例

範例 1

輸入

5
insert 10
insert 20
insert 30
search 20
search 99

輸出

1
0

說明

三次插入會觸發旋轉，但搜尋仍依二元搜尋樹的順序進行：20 存在，99 不存在。

範例 2

輸入

4
insert 5
insert 3
insert 7
inorder

輸出

3 5 7

說明

中序走訪會把所有不重複的鍵值由小到大列出。

範例 3

輸入

5
insert 5
insert 3
insert 7
erase 5
inorder

輸出

3 7

說明

刪除有兩個子節點的根節點時，要用其他節點取代並重新平衡，剩下的鍵值仍保持排序。

範例 4

輸入

6
insert 1
insert 2
insert 3
insert 4
insert 5
height

輸出

3

說明

旋轉讓依序插入的五個鍵值只有節點高度 3，而不是 5。

提示

• 每當某個節點的子樹改變，就要重新計算並儲存該節點的高度。
• 依平衡因子與較重子節點的平衡情形，選擇單旋轉或雙旋轉。
• 刪除時，從刪除位置往回走到根的每個祖先都可能需要重新平衡。
• 高度以節點數計算：空樹高度為 0，單一葉節點高度為 1。