114 年 國立成功大學資訊管理研究所乙組《資料結構》

核心觀念
此題主要測驗遞迴式的漸進分析，特別是 Master Theorem（主定理）在判斷 $T(n)=a\,T(n/b)+f(n)$ 時，各項的指數關係如何決定最終的 $O$ 繁度。

解題過程

1. 寫出遞迴式的參數

   $T(n)=3\,T\!\left(\frac{n}{2}\right)+n^{0.51}$

   • $a = 3$（子問題數目）
   • $b = 2$（子問題規模縮小比例）
   • $f(n)=n^{0.51}$（合併子問題的額外成本）

2. 計算臨界指數 $\log_b a$

   $\log_b a=\log_2 3 \approx 1.585$

   這代表如果遞迴的合併成本與子問題規模的比較是 $n^{\log_2 3}$，則 $T(n)$ 的漸進上界會以此指數為主。

3. 比較 $f(n)$ 與 $n^{\log_b a}$ 的大小

   • $f(n)=n^{0.51}$
   • $n^{\log_2 3}=n^{1.585}$

   明顯有

   $0.51 \;<\; 1.585$

   因此 $f(n)$ 的增長速度 遠低於 $n^{\log_2 3}$。

4. 套用 Master Theorem 的第一種情況

   Master Theorem（簡化版）：

   • 若 $f(n)=O\!\bigl(n^{\log_b a-\varepsilon}\bigr)$（其中 $\varepsilon>0$），則

核心觀念

本題考查 NP-Hard 與 NP-Complete 的集合關係。

• NP：給定一個候選解後，能在多項式時間內驗證其正確性的問題集合。
• NP-Hard：至少與 NP 中最難的問題一樣難。形式上，對所有 $L \in NP$，皆可在多項式時間內約化至問題 $H$：

• NP-Complete：同時滿足：

因此，每個 NP-Complete 問題必定是 NP-Hard；但 NP-Hard 問題不一定屬於 NP，甚至不一定是決策問題。

集合關係可表示為：

解題方法

直接套用定義：

1. NP-Complete 問題必須屬於 NP。
2. NP-Complete 問題也必須符合 NP-Hard 的難度條件。
3. 所以所有 NP-Complete 問題都是 NP-Hard。
4. 但 NP-Hard 的範圍更大，包含不在 NP 中的問題，因此不能反推所有 NP-Hard 問題都是 NP-Complete。

選項分析

(a) All NP-Hard problems are NP-Complete

錯誤。

NP-Hard 問題只要求至少和 NP 中最難的問題一樣難，不要求本身屬於 NP。若某問題無法在多項式時間內驗證候選解，便不屬於 NP，但仍可能是 NP-Hard，因此不一定是 NP-Complete。

核心觀念

本題考查 External Merge Sort（外部合併排序） 的合併路數與所需 pass 數。

當資料量 $N$ 大於主記憶體容量 $M$ 時，無法一次將全部資料載入記憶體，因此分成兩個階段：

1. 建立初始排序串列（sorted runs）
   每次讀入最多 $M$ 筆資料，在記憶體中排序後寫回外部儲存裝置。初始串列數約為

   $\frac{N}{M}$

2. 多路合併（multiway merge）
   每次利用主記憶體中的輸入緩衝區，合併多個已排序串列。

若主記憶體可配置 $M-1$ 個輸入緩衝區，剩下 $1$ 個緩衝區用於輸出，則每次最多可合併 $M-1$ 個 sorted runs。因此每一輪合併後，串列數約縮小為原來的 $\frac{1}{M-1}$。

解題方法

初始共有

$R_0=\frac{N}{M}$

個 sorted runs。

每經過一輪 $(M-1)$-way merge，串列數量除以 $M-1$。經過 $p$ 輪合併後，串列數約為

$R_p=\frac{N/M}{(M-1)^p}$

當所有資料合併成一個 sorted file 時，需滿足

$\frac{N/M}{(M-1)^p}\leq 1$

整理得

$(M-1)^p\geq \frac{N}{M}$

兩邊取對數：

$p\geq \log_{M-1}\left(\frac{N}{M}\right)$

由於 pass 數必須是整數，因此所需合併 pass 數為

$p=\left\lceil \log_{M-1}\left(\frac{N}{M}\right)\right\rceil$

題目選項中的 $[\ ]$ 表示取整數 pass 數，故對應：

$\boxed{[\log_{M-1}(N/M)]}$

補充而言，若將「建立初始 sorted runs」的那一趟也計入總 pass 數，總 pass 數會寫成

核心觀念

使用兩個 stack 實作 queue：

• inStack：負責 enqueue
• outStack：負責 dequeue

stack 遵循後進先出（LIFO），queue 要求先進先出（FIFO）。因此，元素先推入 inStack；當需要 dequeue 且 outStack 為空時，將 inStack 中的所有元素逐一 pop，再 push 到 outStack，即可反轉元素順序。

攤銷分析（amortized analysis）關注的是一連串操作的平均成本，而非單次操作的最壞成本。

解題方法

Enqueue

enqueue 時，直接將新元素 push 至 inStack：

Dequeue

dequeue 有兩種情況：

1. outStack 不為空：直接從 outStack pop，成本為 $O(1)$。
2. outStack 為空：將 inStack 的 $k$ 個元素全部搬移至 outStack，需要 $k$ 次 pop 與 $k$ 次 push，成本為 $O(k)$；接著再從 outStack pop 一次。

因此，單次 dequeue 的最壞時間複雜度可能是：

但每個元素最多只會經歷以下步驟：

• 一次 push 至 inStack
• 一次從 inStack pop
• 一次 push 至 outStack
• 一次從 outStack pop

所以，對 $m$ 次 enqueue 與 dequeue 操作，總成本至多與 $m$ 成正比：

平均至每次操作：

因此，dequeue 的攤銷時間複雜度為：

核心觀念

本題考查雜湊表的碰撞處理方式，重點是區分：

• Closed hashing（封閉雜湊）：通常指 open addressing（開放定址法）。所有資料都直接儲存在雜湊表本身，發生碰撞時，依照探測規則尋找其他空位。
• Separate chaining（分離鏈結法）：通常指 open hashing（開放雜湊）。每個雜湊表位置存放一條鏈結串列或其他容器，碰撞資料放在同一個位置的鏈結結構中。

雜湊表的負載因子為：

其中 $n$ 為已儲存元素數量，$m$ 為雜湊表大小。使用開放定址法時，通常要求 $\alpha<1$；當 $\alpha$ 過高，碰撞與探測成本會明顯增加，因此常需擴充表格並重新雜湊。

解題方法

判斷每個選項是否符合封閉雜湊的定義：

1. 是否在雜湊表內直接處理碰撞？
2. 是否使用探測方式尋找空位？
3. 是否包含線性探測、二次探測？
4. 是否把封閉雜湊誤認為分離鏈結法？

只有將 separate chaining 說成 closed hashing 的選項錯誤。

選項分析

(a) 正確

封閉雜湊使用開放定址法處理碰撞。若兩個鍵值經雜湊後得到相同位置，系統會依照探測規則尋找下一個可用位置，並直接將資料放入雜湊表內。

因此，選項所述「在雜湊表本身內搜尋下一個可用位置」符合封閉雜湊的特徵。

(b) 正確

開放定址法的資料全部存放在雜湊表中，當負載因子 $\alpha$ 過高時，可用空位減少，碰撞與探測次數增加，導致插入、搜尋與刪除效率下降。

此時通常會：

核心觀念

Radix Sort（基數排序）不是直接比較元素大小，而是按照元素的每一位數字或字元，分成多個階段進行穩定排序。

若：

• $n$：待排序元素個數
• $k$：最大元素的位數或字串長度
• 每一位使用 Counting Sort 等線性排序方法處理

則 Radix Sort 必須處理 $k$ 個位數。每一位的排序需要掃描所有 $n$ 個元素，因此單一位的時間複雜度為 $O(n)$。處理全部 $k$ 位後：

因此本題答案為 $O(n\times k)$。

解題方法

Radix Sort 的總時間複雜度可寫成：

其中 $r$ 是每一位可使用的符號數，例如十進位數字的 $r=10$，英文字母則可視為固定大小的字元集合。

當 $r$ 為常數時：

本題只提供 $n$ 與 $k$，且未將 radix 或字元種類數視為變動參數，因此採用標準假設：每一位的分桶與整理成本為線性，答案為：

選項分析

解說
正交串列（orthogonal list）是一種同時以「列」與「行」為基礎的稀疏矩陣儲存方式。其特點是只為非零元素建立結點，並分別以兩條鏈結串接，同時保存指向同一列與同一行的前驅/後繼。此結構的核心目的在於 節省空間，適用於 稀疏圖/矩陣（零元素佔大多數），而非密集矩陣。

核心觀念

本題考查：

1. NP-complete 的證明架構

   • 先證明問題屬於 NP。
   • 再證明某個已知的 NP-complete 問題可在多項式時間內歸約至本問題。

2. Partition Problem（分割問題）

   給定正整數集合

   $A=\{a_1,a_2,\ldots,a_n\},$

   將其分成兩個不相交子集合 $A_1,A_2$，使兩邊總和相等：

   $\sum_{a_i\in A_1}a_i=\sum_{a_i\in A_2}a_i.$

   為了討論 NP-complete，採用其決策版本：

   是否存在一種分割，使兩個子集合的總和完全相等？

3. Subset Sum Problem（子集合總和問題）

   給定正整數集合 $A$ 與目標值 $B$，判斷是否存在子集合 $X\subseteq A$，使得

   $\sum_{x\in X}x=B.$

   Subset Sum 已知為 NP-complete。

解題方法：由 Subset Sum 歸約至 Partition

給定一個 Subset Sum 實例：

$A=\{a_1,a_2,\ldots,a_n\},$

目標值為 $B$。令所有數字總和為

$S=\sum_{i=1}^{n}a_i.$

若 $B>S/2$，可將目標值改為 $S-B$。因為：

$\sum_{x\in X}x=B$

成立，當且僅當其補集合總和為

$S-B.$

因此不失一般性，可假設

$B\leq \frac{S}{2}.$

接著建立 Partition 實例：

$A'=A\cup\{S-2B\}.$

令新增的數字為

$d=S-2B.$

由於 $B\leq S/2$，所以 $d\geq 0$。

$A'$ 的總和為

$S+d=S+(S-2B)=2S-2B=2(S-B).$

因此，若 $A'$ 可以被分成兩組總和相等的子集合，則每一組的總和必須為

$S-B.$

證明一：Subset Sum 有解 $\Rightarrow$ Partition 有解

假設原本的 Subset Sum 有解，存在子集合 $X\subseteq A$，滿足

$\sum_{x\in X}x=B.$

其補集合 $A-X$ 的總和為

$\sum_{a\in A-X}a=S-B.$

將 $X$ 與新增元素 $d=S-2B$ 放在同一組，得到：

另一組則放入補集合 $A-X$，其總和也是

$S-B.$

所以 $A'$ 可以被分割成兩組等和的子集合，Partition 有解。

證明二：Partition 有解 $\Rightarrow$ Subset Sum 有解

核心觀念

本題的核心考點為**最小堆積（Min-Heap）**的完整定義與性質判定。一個資料結構要成為標準的 Min-Heap，必須同時滿足以下兩大基本性質：

1. 結構性質（Shape Property / Complete Binary Tree Property）：
   • 堆積必須是一棵完全二元樹（Complete Binary Tree, CBT）。
   • 二元樹限制每個節點的分支度（degree）最多為 $2$（至多只能有左、右兩個子節點）。
   • 完全二元樹要求除最底層外，其餘各層的節點必須完全填滿；最底層的所有節點必須由左至右連續緊密排列，中間不得有任何缺口（hole）。
2. 堆積順序性質（Heap-Order Property）：
   • 對於樹中除根節點（root）外的任一節點 $i$，其父節點（parent）的值必須小於或等於節點 $i$ 的值，即：
   $$\text{key}(\text{parent}(i)) \le \text{key}(i)$$
   • 樹的最小值必然位於根節點。

解題方法

本題題幹附圖提供一棵候選樹狀圖，要求判斷「必須採取何種操作才能確保該樹符合最小堆積的要求」。

解題切入點依循以下階層式檢查流程：

1. 檢查是否符合二元樹結構：檢視樹中所有節點的子節點數量是否皆 $\le 2$。若某內部節點同時連接了 $3$ 個子節點（例如圖中某節點下同時掛有 $u, v, w$ 三個子分支），則該圖形根本不屬於二元樹。二元樹不可容納三叉分支，因此首要且必須採取的修正動作便是移除多餘的分支（即 $u, v, w$ 其中之一）。
2. 檢查是否符合完全二元樹性質：若分支度皆 $\le 2$，進一步檢視最底層節點是否由左至右緊湊排列。若存在位置不合法、造成結構空缺的額外節點（例如多餘的節點 $x$ 掛在非連續位置），則需移除該節點以恢復完全二元樹結構。

核心觀念

最小堆（min-heap）須同時符合兩個條件：樹形是由上而下、由左而右填入的完全二元樹；每個父節點的鍵值都不大於子節點。執行 removeMin() 時，移除根節點，再將最後一個節點移到根部，並反覆與較小的子節點交換，直到恢復堆序。

解題方法

圖中 $p$ 為根，$q、r$ 為其子節點；$q$ 的子節點為 $s、t$，$r$ 的子節點為 $u、v、w$，而 $s$ 的子節點為 $x$。移除 $w$ 後，節點可依層序排列為 $[p,q,r,s,t,u,v,x]$，符合完全二元樹的形狀；依字母順序，這些節點也符合最小堆的堆序。

執行一次 removeMin()：

1. 移除根節點 $p$，將最後一個節點 $x$ 移到根部。
2. 比較 $x$ 的子節點 $q、r$，較小者為 $q$，因此交換 $x、q$。

這題描述的是堆積排序（Heap Sort）的過程，並詢問其時間複雜度。

堆積排序的步驟如下：

1. 建立堆積 (Build Heap)： 將待排序的 $n$ 個元素插入到一個空的堆積中，形成一個最小堆積（或最大堆積，取決於排序順序）。
2. 排序 (Sort)： 重複從堆積中移除最小值（或最大值）的節點，並將其放入排序好的陣列中，直到堆積變空。

我們需要分析這兩個步驟的時間複雜度。

步驟 1：建立堆積
有兩種方法可以建立堆積：

• 逐個插入 (Insert each element one by one)： 每次插入一個元素到堆積中，需要進行上浮（sift-up 或 bubble-up）操作，以維持堆積性質。插入操作的時間複雜度是 $O(\log n)$（因為堆的高度是 $\log n$）。對 $n$ 個元素進行插入，總時間複雜度是 $n \times O(\log n) = O(n \log n)$。
• Heapify： 從最後一個非葉節點開始，自底向上進行下沉（sift-down 或 heapify-down）操作。這種方法的時間複雜度是 $O(n)$。

題目描述為「sequentially inserts each number into the heap」，這更傾向於「逐個插入」的方法，其複雜度是 $O(n \log n)$。

優先佇列的典型應用：

• 作業系統排程：依優先權選取下一個執行緒。
• Dijkstra 最短路徑：每次取出距離最小的節點。
• Huffman 編碼：以最小頻率建立合併樹。

核心觀念

本題考查 Heap Sort 的建堆成本、時間複雜度、演算法分類，以及穩定性。

以最大堆積排序為例：

1. 先將所有元素建立成最大堆積。
2. 將堆積頂端的最大值與陣列末端交換。
3. 缩小堆積範圍，重新調整成最大堆積。
4. 重複上述步驟，完成遞增排序。

Heap Sort 的整體時間複雜度為：

且其額外空間複雜度通常為：

解題方法

判斷本題各選項時，應分別檢查：

• 建立初始堆積的時間複雜度；
• Heap Sort 是否會利用輸入資料的既有排序程度；
• Heap Sort 的演算法設計分類；
• Heap Sort 是否能保留相同鍵值元素的原始相對順序。

其中最容易混淆的是「建堆」與「每次調整堆積」的複雜度。

建立初始堆積

若使用自底向上的 Build-Heap：

• 葉節點不需調整；
• 越靠近底部的節點，可能下沉的高度越小；
• 只有少數靠近根節點的元素可能移動較長距離。

因此所有節點調整成本的總和為：

而不是將 $n$ 個元素都個別插入堆積所得到的：

排序階段共有 $n-1$ 次取出最大值，每次重新調整堆積最多需要：

所以排序階段為：

整體複雜度為：

選項分析

(a) Building the initial heap takes $O(n\log(n))$ time.

錯誤。

以自底向上的方式建立初始堆積時，Build-Heap 的時間複雜度是：

雖然單一節點向下調整最壞可能需要 $O(\log n)$，但並非所有節點都需要移動 $\log n$ 層。大量節點位於樹的底部，能移動的高度很小，因此總成本為線性時間。

補充而言，若採用「逐一插入元素」建立堆積，才會得到：

但題目談的是建立初始堆積的一般最佳方法，正確複雜度應為 $O(n)$。

(b) Heap sort's complexity improves when the input is nearly sorted.

錯誤。

Heap Sort 並不會因為輸入資料已接近排序完成而明顯減少工作量。即使資料幾乎已排序，仍須：

• 建立堆積；
• 重複取出堆積頂端元素；
• 重新調整堆積。

核心觀念

Trie（字典樹）是一種依照字串中「每個字元」逐層儲存資料的樹狀結構。每一層通常代表字串中的一個字元，因此搜尋長度為 $m$ 的字串時，會依序檢查其 $m$ 個字元。

Trie 搜尋的時間複雜度主要取決於「搜尋字串的長度」，而不是 Trie 中總共有多少個字串。

解題方法

設搜尋字串為：

Trie 搜尋時，從根節點開始：

1. 檢查第 $1$ 個字元 $s_1$ 是否存在。
2. 移動至對應的子節點。
3. 檢查第 $2$ 個字元 $s_2$ 是否存在。
4. 持續處理直到第 $m$ 個字元。

每個字元只需被處理一次，因此總共最多進行 $m$ 次節點查找：

共有 $m$ 項，所以：

若搜尋過程中某個字元不存在，會提前結束，但最壞情況仍須檢查到第 $m$ 個字元，因此時間複雜度為：

此分析假設每個節點尋找下一個字元的操作為 $O(1)$，例如使用陣列或雜湊表儲存子節點。若使用需要排序查找的結構，單次子節點查找成本可能不同，但本題標準 Trie 複雜度答案為 $O(m)$。

選項分析

(a) $O(n\log(n))$

錯誤。

核心觀念

本題的核心考點為**最小堆積（Min-Heap）**的完整定義與性質判定。一個資料結構要成為標準的 Min-Heap，必須同時滿足以下兩大基本性質：

1. 結構性質（Shape Property / Complete Binary Tree Property）：
   • 堆積必須是一棵完全二元樹（Complete Binary Tree, CBT）。
   • 二元樹限制每個節點的分支度（degree）最多為 $2$（至多只能有左、右兩個子節點）。
   • 完全二元樹要求除最底層外，其餘各層的節點必須完全填滿；最底層的所有節點必須由左至右連續緊密排列，中間不得有任何缺口（hole）。
2. 堆積順序性質（Heap-Order Property）：
   • 對於樹中除根節點（root）外的任一節點 $i$，其父節點（parent）的值必須小於或等於節點 $i$ 的值，即：
   $$\text{key}(\text{parent}(i)) \le \text{key}(i)$$
   • 樹的最小值必然位於根節點。

解題方法

本題題幹附圖提供一棵候選樹狀圖，要求判斷「必須採取何種操作才能確保該樹符合最小堆積的要求」。

解題切入點依循以下階層式檢查流程：

1. 檢查是否符合二元樹結構：檢視樹中所有節點的子節點數量是否皆 $\le 2$。若某內部節點同時連接了 $3$ 個子節點（例如圖中某節點下同時掛有 $u, v, w$ 三個子分支），則該圖形根本不屬於二元樹。二元樹不可容納三叉分支，因此首要且必須採取的修正動作便是移除多餘的分支（即 $u, v, w$ 其中之一）。
2. 檢查是否符合完全二元樹性質：若分支度皆 $\le 2$，進一步檢視最底層節點是否由左至右緊湊排列。若存在位置不合法、造成結構空缺的額外節點（例如多餘的節點 $x$ 掛在非連續位置），則需移除該節點以恢復完全二元樹結構。

核心觀念

最小堆（min-heap）須同時符合兩個條件：樹形是由上而下、由左而右填入的完全二元樹；每個父節點的鍵值都不大於子節點。執行 removeMin() 時，移除根節點，再將最後一個節點移到根部，並反覆與較小的子節點交換，直到恢復堆序。

解題方法

圖中 $p$ 為根，$q、r$ 為其子節點；$q$ 的子節點為 $s、t$，$r$ 的子節點為 $u、v、w$，而 $s$ 的子節點為 $x$。移除 $w$ 後，節點可依層序排列為 $[p,q,r,s,t,u,v,x]$，符合完全二元樹的形狀；依字母順序，這些節點也符合最小堆的堆序。

執行一次 removeMin()：

1. 移除根節點 $p$，將最後一個節點 $x$ 移到根部。
2. 比較 $x$ 的子節點 $q、r$，較小者為 $q$，因此交換 $x、q$。

這題描述的是堆積排序（Heap Sort）的過程，並詢問其時間複雜度。

堆積排序的步驟如下：

1. 建立堆積 (Build Heap)： 題目描述為「begins with an empty heap, sequentially inserts each number into the heap」。這意味著對 $n$ 個元素，逐個插入堆積。

   • 每次插入一個元素到堆積中，需要進行上浮（sift-up）操作，以維持堆積性質。插入操作的時間複雜度是 $O(\log k)$，其中 $k$ 是堆積中當前元素的數量。
   • 對 $n$ 個元素進行插入，總時間複雜度是 $\sum_{k=1}^{n} O(\log k) = O(n \log n)$。
   • （注意：如果題目採用「Heapify」方法建立堆積，則時間複雜度是 $O(n)$。但題目明確描述為「sequentially inserts」，所以我們應採用 $O(n \log n)$。）

2. 排序 (Sort)： 題目描述為「repeatedly removes and outputs the smallest number from the heap until it is empty」。

核心觀念

拓樸排序是將有向圖的所有節點排成線性順序，使每一條有向邊 $u\to v$ 都符合「$u$ 排在 $v$ 前面」。只有**有向無環圖（DAG）**才存在拓樸排序。

解題方法

沿著圖中的箭頭可找到一個有向環：

拓撲排序（Topological Sort）是對有向無環圖（DAG）的頂點進行的線性排序。
有兩種常見的演算法可以進行拓撲排序：

1. 基於深度優先搜尋 (DFS) 的方法：

   • 對圖進行 DFS 遍歷。
   • 當一個節點的所有鄰居都被訪問過（即 DFS 遞迴調用返回）後，將該節點添加到一個鏈結串列的開頭。
   • 最終鏈結串列中的順序就是一個拓撲排序。
   • DFS 遍歷的時間複雜度是 $O(V+E)$，其中 $V$ 是節點數，$E$ 是邊數。
   • 將節點添加到鏈結串列開頭的操作是 $O(1)$。
   • 因此，基於 DFS 的拓撲排序時間複雜度是 $O(V+E)$。

2. 基於入度 (In-degree) 的方法（Kahn's Algorithm）：

   • 計算所有節點的入度。
   • 將所有入度為 0 的節點放入一個佇列（或堆疊）。

這題要求根據提供的圖來判斷其性質。圖中的邊有方向箭頭，並且有權重。

我們來逐一分析每個選項：

a) Directed
圖中的邊有明確的方向箭頭（例如 A -> B）。這表明圖是定向的。因此，這個敘述是正確的。

b) Weakly connected
一個有向圖是弱連通的，如果將所有有向邊視為無向邊後，得到的無向圖是連通的。
我們將圖中的邊視為無向邊：(A,B), (A,D), (B,C), (B,D), (C,D), (C,E), (D,E)。
從 A 可以到達 B, D。
從 B 可以到達 A, C, D。
從 C 可以到達 B, D, E。
從 D 可以到達 A, B, C, E。
從 E 可以到達 C, D。
所有節點都可以通過無向邊互相到達。例如，從 A 到 E，可以走 A -> D -> E。
因此，將邊視為無向圖後，圖是連通的。這個敘述是正確的。

c) Undirected
圖中的邊有方向箭頭，所以它不是無向圖。這個敘述是錯誤的。

在不允許自迴環的有向圖中，每個節點可指向除自身外的 $V-1$ 個其他節點，全部

在無自迴線的無向圖中，若圖必須連通，則其邊數不能少於形成一棵樹所需的邊數。

最低度＝每個節點連接至除自身外的 $V-1$ 個節點，再加上一條自環。自環在無向圖中貢獻 2 度。

核心觀念

二元搜尋樹（Binary Search Tree, BST）插入元素時，必須從根節點開始，依序比較鍵值：

• 若新元素小於目前節點，往左子樹移動。
• 若新元素大於目前節點，往右子樹移動。
• 找到空的位置後，將新節點插入。

因此，插入所需時間取決於從根節點走到插入位置的路徑長度，也就是二元搜尋樹的高度 $h$。

解題方法

一般情況

若二元搜尋樹大致平衡，高度約為：

此時插入只需沿著一條由根至葉節點的路徑搜尋，因此時間複雜度為：

最壞情況

若輸入資料已經排序，例如依序插入：

二元搜尋樹會退化成單鏈結串列：

1
 \
  2
   \
    3
     \
      4
       \
        5

此時樹高為：

核心觀念

本題考查二元搜尋樹的前序走訪（pre-order traversal）與時間複雜度分析。

前序走訪順序為：

二元搜尋樹的結構會影響搜尋效率，但不影響「走訪全部節點」所需處理的節點數量。

解題方法

設二元搜尋樹共有 $n$ 個節點。執行前序走訪時：

1. 根節點會被處理一次。
2. 左子樹中的每個節點各被處理一次。
3. 右子樹中的每個節點各被處理一次。

因此，整棵樹的每個節點恰好被拜訪一次。每次拜訪所執行的工作為常數時間 $O(1)$，所以總時間為：

得到：

而且要輸出或處理所有 $n$ 個節點，至少需要花費 $\Omega(n)$ 時間，因此更精確地表示為：

這題要求根據後序遍歷序列和 AVL 樹的性質（完全樹）來構造和繪製該 AVL 樹。

基本概念：

• AVL 樹： 一種自平衡二元搜尋樹（BST），它通過旋轉操作來維持其平衡，確保任何節點的左右子樹高度差不超過 1。
• 完全二元樹 (Complete Binary Tree)： 在這裡，題目提到 AVL 樹「known to be a complete tree」。這是一個重要的線索。完全二元樹是指除了最後一層，其他層都完全填滿，最後一層的所有節點都盡可能靠左排列。
• 後序遍歷 (Post-order Traversal)： 訪問順序是：左子樹 -> 右子樹 -> 根節點。
• 中序遍歷 (In-order Traversal)： 訪問順序是：左子樹 -> 根節點 -> 右子樹。對於 BST，中序遍歷的結果是節點值從小到大排序的序列。

已知資訊：

1. 樹是一個 AVL 樹，這意味著它也是一個 BST。
2. 樹是一個完全二元樹。
3. 後序遍歷序列：11, 33, 22, 55, 77, 66, 44。

構造步驟：
後序遍歷序列的最後一個元素總是根節點。
所以，根節點是 44。

現在我們知道根節點是 44。後序遍歷序列是 (Left Subtree) (Right Subtree) Root。
序列：11, 33, 22, 55, 77, 66, 44
根節點：44
左子樹的後序遍歷序列是 44 之前的所有元素，但需要根據 44 在該序列中的位置來劃分左右子樹。
由於 44 是最後一個元素，所以它代表整個樹的根。
左子樹的後序遍歷序列是 11, 33, 22。
右子樹的後序遍歷序列是 55, 77, 66。

現在我們需要知道左子樹和右子樹的節點數量，以便劃分中序遍歷序列。
由於樹是一個完全二元樹，並且我們知道根節點是 44，節點總數是 7。
根節點 1 個。
剩餘 6 個節點，平均分配給左右子樹。
左子樹節點數 = 3。
右子樹節點數 = 3。

接下來，我們需要中序遍歷序列。但是題目沒有給出中序遍歷。
這是個問題。通常，構造 BST 需要後序和中序，或者前序和中序。
只給後序遍歷，而且知道是完全二元樹，這是一個挑戰。

利用「完全二元樹」的性質：
一個完全二元樹的結構是固定的，一旦知道節點總數，就可以確定其結構。
總節點數 = 7。
層次結構：
第 1 層：1 個節點 (根)
第 2 層：2 個節點
第 3 層：4 個節點
總共 $1+2+4 = 7$ 個節點。這是一棵滿二元樹，也是完全二元樹。

我們有後序遍歷序列：[11, 33, 22] [55, 77, 66] 44
左子樹後序：11, 33, 22 (3 個節點)
右子樹後序：55, 77, 66 (3 個節點)

由於這是 AVL 樹，它也是 BST。
在 BST 中，中序遍歷是排序的。
我們需要找到左子樹和右子樹的中序遍歷。
但我們沒有中序遍歷序列。

核心觀念

二元搜尋樹（BST）中，每個節點的左子樹鍵值都小於該節點，右子樹鍵值都大於該節點。插入時依大小比較一路往下，直到找到空位；刪除時則須維持此大小關係。

刪除有兩個子節點的節點時，可用其中序後繼（右子樹的最小值）替代，再刪除原本後繼所在的葉節點。本題依此慣例處理刪除 84。

解題方法

依序執行各項操作，並在每一步維持 BST 性質：

1. 插入 2：$2<47$，往左到 16；$2<16$，往左到 3；$2<3$，插入為 3 的左子節點。
2. 刪除 49：49 是葉節點，直接移除。64 的左子節點變為空。
3. 刪除 35：35 只有左子節點 28。將 28 移到 35 原本的位置，再移除葉節點 28；因此 37 的左子節點改為 28。
4. 插入 85：$85>47$，往右到 84；$85>84$，往右到 86；$85<86$，插入為 86 的左子節點。