給定一棵二元搜尋樹（binary search tree），且該樹同時也是一棵AVL 樹。 樹的節點在C 語言中宣告如下： typedef struct Nod…

題目

給定一棵二元搜尋樹（binary search tree），且該樹同時也是一棵AVL 樹。 樹的節點在C 語言中宣告如下： typedef struct Node { int key; // 節點的鍵值，所有節點的鍵值皆互不相同 int size; // 以該節點為根的子樹節點總數(包含自己) struct Node *left; // 指向左子節點 struct Node *right; // 指向右子節點 } Node; 並定義以下函式： int size (Node *node)： 若傳入的node 為NULL，則回傳0；否則回傳node -> size。 int count_less_equal (Node *node, int val)： 回傳以node 為根的子樹中，所有鍵值小於等於val 的節點總數。 Node* select (Node *node, int r)： 回傳以node 為根的子樹中，第r 小的節點指標，r 從1 開始算。 Node* greater_k_smallest (Node *root, int val, int k)： 找出以root 為根的整棵樹中，所有鍵值大於val 的節點裡，第k 小的 節點，k 從1 開始算。若第k 小的節點不存在，則回傳NULL。 完成下列程式碼的空格。（20 分） int count_less_equal(Node *node, int val) { if (node == NULL) return 0; if (node->key > val) return count_less_equal(node->left, val); else return size(node->left)+ (1) ; } Node* select(Node *node, int r) { int left_size = size(node->left); if (r == (2) ) return node; else if (r <= left_size) return select(node->left, r); else return (3) ; } Node* greater_k_smallest(Node *root, int val, int k){ int x = count_less_equal(root, val); int y = (4) ; if (y > size(root)) return NULL; return select(root, y); } 下圖為一棵包含5 個節點且滿足AVL 平衡特性的二元搜尋樹，圖中 顯示每個節點的鍵值。若將鍵值為70 的新節點插入此樹，為保持AVL 樹的平衡，會觸發旋轉。請畫出旋轉後的樹狀結構圖。除新插入的節 點70 外，若原有節點的size 欄位值在旋轉後發生改變，請在旋轉後 的圖中，於該節點旁標示其新的size 欄位值。（5 分）

參考解答（AI 生成，非官方）

• 一、空格答案：（1）1 + count_less_equal(node->right, val)；（2）left_size + 1；（3）select(node->right, r - left_size - 1)；（4）x + k。以上四式即為count_less_equal、select與greater_k_smallest的核心邏輯。
• 二、函式意義與邊界：count_less_equal回傳鍵值小於等於val的節點數；select利用左子樹大小判斷第r小在左子樹、根或右子樹；greater_k_smallest先算小於等於val的數量x，則第k個大於val者之全域排名為x+k，若超過size(root)即不存在，回傳NULL。
• 三、AVL旋轉的判定與限制：題目所述5節點AVL樹之鍵值與連結圖未顯示，無法唯一判定70插入位置、旋轉型態及各節點新size；題目資料缺漏，無法得出唯一樹形。若補上原圖，應先找出插入路徑上最低的不平衡節點，再依其與插入位置的關係判定LL、RR、LR或RL型。
• 四、四種旋轉與繪圖：LL型對最低不平衡節點右旋；RR型左旋；LR型先對左子節點左旋再對根右旋；RL型先對右子節點右旋再對根左旋。繪圖時先標新根，再畫左右子樹，保持二元搜尋樹（binary search tree, BST）中序遞增；新節點70以圓圈標示，並在size變動節點旁寫出新值。
• 五、size更新：旋轉後由下往上計算size(x)=size(x->left)+size(x->right)+1。僅受旋轉影響的子樹根（含新根及其子節點）需要更新，未參與旋轉的子樹size不變；若某節點新size與原值相同則不必特別標示。考場上應先完成旋轉圖，再逐點標size，以免漏算。

AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。

官方資料

• 官方試題 PDF