108 年 國立中正大學電機工程學系碩士班計算機工程組《資料結構》

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）的節點表示、刪除操作，以及刪除操作的時間複雜度。

BST 必須滿足以下性質：

• 任一節點左子樹中所有鍵值皆小於該節點鍵值。
• 任一節點右子樹中所有鍵值皆大於該節點鍵值。
• 左、右子樹本身也必須是 BST。

因此，搜尋、插入與刪除都沿著根節點到某條路徑進行，執行時間主要取決於樹高 $h$。

---

i. BST 節點資料結構

假設每個節點的鍵值唯一，可使用 C 語言定義如下：

typedef int KeyType;

typedef struct BSTNode {
    KeyType key;
    struct BSTNode *left;
    struct BSTNode *right;
} BSTNode;

其中：

• key：儲存節點的鍵值。
• left：指向左子節點。
• right：指向右子節點。
• 若沒有左子節點或右子節點，對應指標設為 NULL。

建立新節點的函式如下：

BSTNode *createNode(KeyType key) {
    BSTNode *node = new BSTNode;
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    return node;
}

---

ii. BST 刪除函式

解題方法

刪除節點時，先依 BST 性質搜尋目標鍵值，再根據目標節點的子樹數量分成三種情況：

1. 沒有子節點：直接刪除，回傳 NULL。
2. 只有一個子節點：以唯一子節點取代目前節點。
3. 有兩個子節點：找出右子樹中的最小節點，也就是目前節點的中序後繼（inorder successor），將其鍵值複製到目前節點，再刪除右子樹中的後繼節點。

選擇右子樹最小節點的原因是：它大於目前節點左子樹所有鍵值，且小於右子樹其他節點，替代後仍能維持 BST 性質。

函式定義

BSTNode *deleteNode(BSTNode *root, KeyType target) {
    BSTNode *successor;

    /* 找不到目標節點 */
    if (root == NULL) {
        return NULL;
    }

    /* 目標值在左子樹 */
    if (target < root->key) {
        root->left = deleteNode(root->left, target);
    }

    /* 目標值在右子樹 */
    else if (target > root->key) {
        root->right = deleteNode(root->right, target);
    }

    /* 找到要刪除的節點 */
    else {
        /* 情況一：沒有左子樹 */
        if (root->left == NULL) {
            BSTNode *child = root->right;
            delete root;
            return child;
        }

        /* 情況二：沒有右子樹 */
        if (root->right == NULL) {
            BSTNode *child = root->left;
            delete root;
            return child;
        }

        /* 情況三：同時具有左右子樹 */
        successor = root->right;

        while (successor->left != NULL) {
            successor = successor->left;
        }

        root->key = successor->key;
        root->right = deleteNode(root->right, successor->key);
    }

    return root;
}

若使用標準 C 語言，記憶體釋放部分可改寫為：

free(root);

完整的呼叫方式如下：

root = deleteNode(root, target);

必須將函式回傳值重新指定給 root，原因是刪除根節點或刪除後改變子樹根節點時，整棵樹的根指標可能發生變化。

三種刪除情況

核心觀念

本題考查比較式排序（comparison-based sorting）的複雜度、輸入資料特性，以及實際執行成本。

對 $n$ 個互異元素的比較式排序而言，所有可能排列共有 $n!$ 種。若將每次比較視為二元決策，決策樹高度為 $h$ 時最多只能表示 $2^h$ 種結果，因此必須滿足

$$2^h \geq n!$$

所以

$$h \geq \log_2(n!)=\Theta(n\log n)$$

這表示：對任意輸入都要正確排序時，比較式排序的最壞情況下限為 $\Omega(n\log n)$。因此，$O(n\log n)$ 在大型且無特殊結構的資料上具有漸近優勢，但不代表每個實際情況都比 $O(n^2)$ 方法快。

以 insertion sort 為例：

• 最好情況：資料已排序，時間為 $\Theta(n)$。
• 平均與最壞情況：時間為 $\Theta(n^2)$。
• 額外空間：$O(1)$。
• 若只在嚴格大於時移動元素，則具穩定性。

---

(i) 為何選擇 $O(n^2)$ 排序法

1. 資料量很小時，常數成本較低

$O(n\log n)$ 方法通常包含遞迴、分割、合併、額外陣列配置、函式呼叫或堆積維護等成本。

$O(n^2)$ 的 insertion sort 程式結構簡單，對小型陣列只需少量比較與移動，實際執行時間常比完整的 merge sort 或 heap sort 更短。許多高效排序法也會在子陣列很小時改用 insertion sort。

2. 資料已排序或接近排序時，insertion sort 具有適應性

令 $I$ 表示輸入序列中的 inversion 數量，即滿足

$$i<j,\quad A[i]>A[j]$$

的元素配對數。Insertion sort 的移動次數正好與 inversion 數量相關，因此其實際時間可表示為

$$\Theta(n+I)$$

當資料已排序時，$I=0$，時間為 $\Theta(n)$；當資料只有少量錯位時，$I$ 很小，仍接近線性時間。

3. 額外空間需求小

Insertion sort 可在原陣列中直接完成排序，只需儲存目前插入的元素，因此額外空間為

$$O(1)$$

以需要額外暫存陣列的 merge sort 為例，其額外空間通常為 $O(n)$。在記憶體有限、資料需原地處理的情況下，$O(n^2)$ 方法具有優勢。

4. 穩定且適合線上處理

Insertion sort 可以逐一讀入資料，維持目前已讀取部分的排序狀態，因此適合：

• 資料持續到達的線上排序。
• 已有排序資料中插入少量新資料。
• 需要保留相同鍵值原始順序的穩定排序。

5. 記憶體區域性良好

陣列版 insertion sort 主要在相鄰位置進行比較與移動，快取使用效率高，實際成本容易預測。某些理論上較佳的排序法，因為遞迴、隨機存取或額外資料結構，實際表現未必在小型資料上勝出。

---

(ii) 具體例子

考慮資料

$$A=[1,2,3,4,5,7,6,8]$$

這是一個幾乎已排序的序列，只有 $7$ 與 $6$ 的位置顛倒，因此 inversion 數量為

$$I=1$$

使用 insertion sort

Insertion sort 依序將每個元素插入前方已排序的區段。

核心觀念

本題考查「多重鏈結串列（multi-linked list）」：

• 每個資料節點同時具有兩種排序關係。
• nameNext：依姓名遞增串接。
• phoneNext：依電話號碼遞增串接。
• 同一個節點必須同時存在於兩條鏈結中，但兩條鏈結使用不同的指標。
• 表頭節點不存放一般資料，只保存兩條鏈結的起點。

以下假設姓名與電話號碼皆為唯一；若有相同值，程式採「插入於相同值之後」的穩定插入方式。

i. 資料結構

typedef struct MultiNode {
    char *name;                    // 姓名字串
    int phone;                     // 電話號碼

    struct MultiNode *nameNext;    // 依姓名遞增的下一個節點
    struct MultiNode *phoneNext;   // 依電話號碼遞增的下一個節點
} MultiNode;

/* 表頭節點 */
typedef struct {
    MultiNode *nameHead;           // 姓名排序鏈結的起點
    MultiNode *phoneHead;          // 電話號碼排序鏈結的起點
} MultiList;

結構關係如下：

nameHead  →  依姓名排序的節點鏈結
phoneHead →  依電話排序的節點鏈結

例如資料節點可同時形成：

姓名順序：Bob → Liu → Pol → Zac
電話順序：Zac → Pol → Liu → Bob

兩條鏈結中的節點是相同的資料節點，只是分別透過 nameNext 與 phoneNext 連接。

ii. 插入函式

解題方法

插入一筆資料時，處理步驟如下：

1. 建立新節點並複製姓名字串。
2. 依姓名順序尋找插入位置，調整 nameNext。
3. 依電話號碼順序尋找插入位置，調整 phoneNext。
4. 若插入位置在最前端，更新表頭對應的指標。
5. 若串列為空，兩個表頭指標都指向新節點。

輔助函式：複製字串

char *copyString(const char *src)
{
    int i, len = 0;
    char *dest;

    while (src[len] != '\0')
        len++;

    dest = (char *)malloc((len + 1) * sizeof(char));
    if (dest == NULL)
        return NULL;

    for (i = 0; i <= len; i++)
        dest[i] = src[i];

    return dest;
}

插入函式