108 年 國立暨南國際大學資訊工程學系碩士班《資料結構與演算法》

核心觀念

本題考查兩個重要觀念：

1. 具有 $n$ 個節點之不同二元樹數量：使用 Catalan number（卡特蘭數）。
2. 二元樹的最小高度：利用高度為 $h$ 時最多能容納的節點數，求出能容納 $N$ 個節點的最小高度。

---

a. 由 5 個節點可形成多少種不同二元樹？

解題方法

令 $T(n)$ 表示由 $n$ 個節點形成的不同二元樹數量。

一棵二元樹若選定根節點，剩餘的 $n-1$ 個節點會分配到：

• 左子樹：$i$ 個節點；
• 右子樹：$n-1-i$ 個節點。

因此：

$$T(n)=\sum_{i=0}^{n-1}T(i)T(n-1-i)$$

其中空樹也要計算，因此定義：

$$T(0)=1$$

逐步計算：

$$T(1)=T(0)T(0)=1$$ $$T(2)=T(0)T(1)+T(1)T(0)=2$$ $$T(3)=T(0)T(2)+T(1)T(1)+T(2)T(0)=5$$ $$T(4)=1\cdot5+1\cdot2+2\cdot1+5\cdot1=14$$ $$\begin{aligned} T(5) &=T(0)T(4)+T(1)T(3)+T(2)T(2)\\ &\quad+T(3)T(1)+T(4)T(0)\\ &=1\cdot14+1\cdot5+2\cdot2+5\cdot1+14\cdot1\\ &=14+5+4+5+14\\ &=42 \end{aligned}$$

也可直接使用 Catalan number 公式：

$$C_n=\frac{1}{n+1}\binom{2n}{n}$$

對於 $n=5$：

$$C_5=\frac{1}{6}\binom{10}{5} =\frac{1}{6}\times252 =42$$

解題技巧

二元樹節點數量的排列為：

$$1,\ 1,\ 2,\ 5,\ 14,\ 42,\ldots$$

這就是 Catalan number 序列。考試中若題目問「由 $n$ 個節點可形成多少種不同二元樹」，通常直接套用：

$$\boxed{C_n=\frac{1}{n+1}\binom{2n}{n}}$$

此處的「不同」採標準定義，指樹的形狀不同。若題目另指 5 個節點具有不同標籤，則還需再乘上 $5!$；本題依二元樹結構計數，答案為 $42$。

---

(a) 建立 2-3-4 樹與詳細解說

核心觀念與規則：
2-3-4 樹為階數 (order) 為 4 的 B-tree。本解法採用 Top-Down（由上而下）預先分裂策略：搜尋插入位置時，若遇到含有 3 個 key 的滿節點 (4-node)，先將中間鍵值向上提升 (promote) 至父節點，將該 4-node 分裂為兩個 2-node，再繼續往下插入。若 key 值重複，依據 $\le$ 置於左子樹處理。

關鍵建構步驟（字元序列：ADIAMONDISFOREVER）：

1. 插入 A, D, I：節點滿載為 4-node [A, D, I]。
2. 插入 A：根節點 [A, D, I] 滿載，預先分裂中間值 D 成為新根。
   • 分裂後：根 [D]，左子 [A]，右子 [I]。
   • 插入 A 後左子成為 [A, A]。
3. 插入 M, O：M 與 O 依序進入右子，形成 4-node [I, M, O]。
4. 插入 N：搜尋至 [I, M, O] 發現滿載，將 M 提升至根節點。
   • 分裂後：根 [D, M]，子節點由左至右為 [A, A]、[I]、[O]。
   • 插入 N 至 [O] 形成 [N, O]。
5. 插入 D, I, S, F：
   • 插入 D 至 [A, A] 形成 4-node [A, A, D]。
   • 插入 I 至 [I] 形成 [I, I]。
   • 插入 S 至 [N, O] 形成 4-node [N, O, S]。
   • 插入 F 至 [I, I] 形成 4-node [F, I, I]。
6. 插入 O：搜尋至 [N, O, S] 發現滿載，將 O 提升至根節點。
   • 分裂後：根 [D, M, O] 滿載，子節點由左至右為 [A, A, D]、[F, I, I]、[N]、[S]。
   • 插入 O 至 [N] 形成 [N, O]。
7. 插入 R：根節點 [D, M, O] 滿載，預先分裂中間值 M 成為新根。
   • 分裂後：根 [M]；左子 [D] 下接 [A, A, D] 與 [F, I, I]；右子 [O] 下接 [N, O] 與 [S]。
   • 插入 R 至 [S] 形成 [R, S]。
8. 插入 E：搜尋走右子 [F, I, I] 發現滿載，將 I 提升至父節點 [D]（成為 [D, I]），[F, I, I] 分裂為 [F] 與 [I]。
   • 插入 E 至 [F] 形成 [E, F]。
9. 插入 V, E：
   • 插入 V 至 [R, S] 形成 4-node [R, S, V]。
   • 插入 E 至 [E, F] 形成 4-node [E, E, F]。
10. 插入 R：搜尋至 [R, S, V] 發現滿載，將 S 提升至父節點 [O]（成為 [O, S]），[R, S, V] 分裂為 [R] 與 [V]。
    • 插入 R 至 [R] 形成 [R, R]。

【答案】最終 2-3-4 樹結構如下：

$$\begin{gathered} \text{[M]} \\ / \quad \backslash \\ \text{[D, I]} \qquad \qquad \text{[O, S]} \\ / \quad | \quad \backslash \qquad \qquad / \quad | \quad \backslash \\ \text{[A, A, D]} \ \text{[E, E, F]} \ \text{[I]} \quad \text{[N, O]} \ \text{[R, R]} \ \text{[V]} \end{gathered}$$

---

核心觀念

AVL 樹要求每一個節點都滿足平衡條件。定義節點 $v$ 的平衡因子為：

$$BF(v)=height(v.left)-height(v.right)$$

對 AVL 樹而言，必須有：

$$BF(v)\in\{-1,0,1\}$$

插入新節點後，若某節點 $z$ 的平衡因子變成 $2$ 或 $-2$，表示 $z$ 失衡。此時必須根據「失衡節點 $z$」與「較高子樹的方向」判斷旋轉類型。

四種情況如下：

情況	失衡方向	子樹方向	修正方式
L-L	左子樹過高	左子樹的左側過高	對 $z$ 做右旋
R-R	右子樹過高	右子樹的右側過高	對 $z$ 做左旋
L-R	左子樹過高	左子樹的右側過高	先對左子節點左旋，再對 $z$ 右旋
R-L	右子樹過高	右子樹的左側過高	先對右子節點右旋，再對 $z$ 左旋

其中 L、R 表示新節點插入路徑的左、右方向；R-R 並不是「向右旋轉兩次」。

---

解題方法

先找出插入後第一個失衡的祖先節點 $z$，計算：

$$BF(z)=height(z.left)-height(z.right)$$

• $BF(z)>1$：左子樹過高，屬於 L 開頭的情況。
• $BF(z)<-1$：右子樹過高，屬於 R 開頭的情況。

接著檢查較高子節點的平衡因子，即可判斷第二個方向。

C-like pseudo-code

typedef enum {
    LL,
    RR,
    LR,
    RL
} RotationType;

int balanceFactor(Node *v) {
    if (v == NULL)
        return 0;

    return height(v->left) - height(v->right);
}

RotationType determineRotation(Node *z) {
    int bfZ = balanceFactor(z);

    // 左子樹過高
    if (bfZ > 1) {
        int bfLeft = balanceFactor(z->left);

        if (bfLeft >= 0)
            return LL;    // L-L
        else
            return LR;    // L-R
    }

    // 右子樹過高
    if (bfZ < -1) {
        int bfRight = balanceFactor(z->right);

        if (bfRight <= 0)
            return RR;    // R-R
        else
            return RL;    // R-L
    }

    return NONE;          // 尚未失衡
}

若需直接執行修正，可寫成：

Node *rebalance(Node *z) {
    int bfZ = balanceFactor(z);

    // L-L：單右旋
    if (bfZ > 1 &&
        balanceFactor(z->left) >= 0) {
        return rotateRight(z);
    }

    // L-R：先左旋，再右旋
    if (bfZ > 1 &&
        balanceFactor(z->left) < 0) {
        z->left = rotateLeft(z->left);
        return rotateRight(z);
    }

    // R-R：單左旋
    if (bfZ < -1 &&
        balanceFactor(z->right) <= 0) {
        return rotateLeft(z);
    }

    // R-L：先右旋，再左旋
    if (bfZ < -1 &&
        balanceFactor(z->right) > 0) {
        z->right = rotateRight(z->right);
        return rotateLeft(z);
    }

    return z;
}

---

四種情況說明

1. L-L 情況

若：

$$BF(z)>1$$

代表 $z$ 的左子樹過高。若：

$$BF(z.left)\ge 0$$

表示左子節點的左側不低於右側，失衡路徑為：

$$z\rightarrow left\rightarrow left$$

因此屬於 L-L，對 $z$ 做一次右旋即可。

        z                 y
       / \               / \
      y   D     →       A   z
     / \                   / \
    A   C                 C   D

---