高考申論題
115年
[資訊處理] 資料結構
第 鿪 題
📖 題組：
給定一棵二元搜尋樹（binary search tree），且該樹同時也是一棵 AVL 樹。 樹的節點在 C 語言中宣告如下： ```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。
給定一棵二元搜尋樹（binary search tree），且該樹同時也是一棵 AVL 樹。 樹的節點在 C 語言中宣告如下： ```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。
下圖為一棵包含 5 個節點且滿足 AVL 平衡特性的二元搜尋樹，圖中顯示每個節點的鍵值。若將鍵值為 70 的新節點插入此樹，為保持 AVL 樹的平衡，會觸發旋轉。請畫出旋轉後的樹狀結構圖。除新插入的節點 70 外，若原有節點的 size 欄位值在旋轉後發生改變，請在旋轉後的圖中，於該節點旁標示其新的 size 欄位值。（5 分）
📝 此題為申論題
思路引導 VIP
考查 AVL 樹的插入與旋轉（Double Rotation）。
- 插入 70 的位置：大於 50(右)，小於 80(左)，大於 60(右)。因此 70 將成為 60 的右子節點。
🤖
AI 詳解
AI 專屬家教
【考點分析】 AVL 樹的插入、平衡判定（Balance Factor）以及 Right-Left (RL) 雙旋轉操作，結合節點子樹大小 (size) 屬性的更新。 【理論/法規依據】
▼ 還有更多解析內容