C++二叉搜索樹

圖 7-19   在二叉搜索樹中刪除節(jié)點（度為 0 ）如圖 7-16 所示，「二叉搜索樹 binary search tree」?jié)M足以下條件。

1. 對于根節(jié)點，左子樹中所有節(jié)點的值 < 根節(jié)點的值 < 右子樹中所有節(jié)點的值。
2. 任意節(jié)點的左、右子樹也是二叉搜索樹，即同樣滿足條件 1. 。

圖 7-16   二叉搜索樹

二叉搜索樹的操作

我們將二叉搜索樹封裝為一個類 ArrayBinaryTree ，并聲明一個成員變量 root ，指向樹的根節(jié)點。

1.   查找節(jié)點

給定目標節(jié)點值 num ，可以根據(jù)二叉搜索樹的性質(zhì)來查找。如圖 7-17 所示，我們聲明一個節(jié)點 cur ，從二叉樹的根節(jié)點 root 出發(fā)，循環(huán)比較節(jié)點值 cur.val 和 num 之間的大小關(guān)系。

• 若 cur.val < num ，說明目標節(jié)點在 cur 的右子樹中，因此執(zhí)行 cur = cur.right 。
• 若 cur.val > num ，說明目標節(jié)點在 cur 的左子樹中，因此執(zhí)行 cur = cur.left 。
• 若 cur.val = num ，說明找到目標節(jié)點，跳出循環(huán)并返回該節(jié)點。

圖 7-17   二叉搜索樹查找節(jié)點示例

二叉搜索樹的查找操作與二分查找算法的工作原理一致，都是每輪排除一半情況。循環(huán)次數(shù)最多為二叉樹的高度，當二叉樹平衡時，使用 $O(\log ?n)$ 時間。

binary_search_tree.cpp

/* 查找節(jié)點 */
TreeNode *search(int num) {
    TreeNode *cur = root;
    // 循環(huán)查找，越過葉節(jié)點后跳出
    while (cur != nullptr) {
        // 目標節(jié)點在 cur 的右子樹中
        if (cur->val < num)
            cur = cur->right;
        // 目標節(jié)點在 cur 的左子樹中
        else if (cur->val > num)
            cur = cur->left;
        // 找到目標節(jié)點，跳出循環(huán)
        else
            break;
    }
    // 返回目標節(jié)點
    return cur;
}

2.   插入節(jié)點

給定一個待插入元素 num ，為了保持二叉搜索樹“左子樹 < 根節(jié)點 < 右子樹”的性質(zhì)，插入操作流程如圖 7-18 所示。

1. 查找插入位置：與查找操作相似，從根節(jié)點出發(fā)，根據(jù)當前節(jié)點值和 num 的大小關(guān)系循環(huán)向下搜索，直到越過葉節(jié)點（遍歷至 None ）時跳出循環(huán)。
2. 在該位置插入節(jié)點：初始化節(jié)點 num ，將該節(jié)點置于 None 的位置。

圖 7-18   在二叉搜索樹中插入節(jié)點

在代碼實現(xiàn)中，需要注意以下兩點。

• 二叉搜索樹不允許存在重復(fù)節(jié)點，否則將違反其定義。因此，若待插入節(jié)點在樹中已存在，則不執(zhí)行插入，直接返回。
• 為了實現(xiàn)插入節(jié)點，我們需要借助節(jié)點 pre 保存上一輪循環(huán)的節(jié)點。這樣在遍歷至 None 時，我們可以獲取到其父節(jié)點，從而完成節(jié)點插入操作。

binary_search_tree.cpp

/* 插入節(jié)點 */
void insert(int num) {
    // 若樹為空，則初始化根節(jié)點
    if (root == nullptr) {
        root = new TreeNode(num);
        return;
    }
    TreeNode *cur = root, *pre = nullptr;
    // 循環(huán)查找，越過葉節(jié)點后跳出
    while (cur != nullptr) {
        // 找到重復(fù)節(jié)點，直接返回
        if (cur->val == num)
            return;
        pre = cur;
        // 插入位置在 cur 的右子樹中
        if (cur->val < num)
            cur = cur->right;
        // 插入位置在 cur 的左子樹中
        else
            cur = cur->left;
    }
    // 插入節(jié)點
    TreeNode *node = new TreeNode(num);
    if (pre->val < num)
        pre->right = node;
    else
        pre->left = node;
}

與查找節(jié)點相同，插入節(jié)點使用 $O(\log ?n)$ 時間。

3.   刪除節(jié)點

先在二叉樹中查找到目標節(jié)點，再將其從二叉樹中刪除。

與插入節(jié)點類似，我們需要保證在刪除操作完成后，二叉搜索樹的“左子樹 < 根節(jié)點 < 右子樹”的性質(zhì)仍然滿足。

因此，我們需要根據(jù)目標節(jié)點的子節(jié)點數(shù)量，共分為 0、1 和 2 這三種情況，執(zhí)行對應(yīng)的刪除節(jié)點操作。

如圖 7-19 所示，當待刪除節(jié)點的度為 0 時，表示該節(jié)點是葉節(jié)點，可以直接刪除。

圖 7-19   在二叉搜索樹中刪除節(jié)點（度為 0 ）

如圖 7-20 所示，當待刪除節(jié)點的度為 $1$ 時，將待刪除節(jié)點替換為其子節(jié)點即可。

圖 7-20   在二叉搜索樹中刪除節(jié)點（度為 1 ）

當待刪除節(jié)點的度為 2 時，我們無法直接刪除它，而需要使用一個節(jié)點替換該節(jié)點。由于要保持二叉搜索樹“左 < 根 < 右”的性質(zhì)，因此這個節(jié)點可以是右子樹的最小節(jié)點或左子樹的最大節(jié)點。

假設(shè)我們選擇右子樹的最小節(jié)點（即中序遍歷的下一個節(jié)點），則刪除操作流程如圖 7-21 所示。

1. 找到待刪除節(jié)點在“中序遍歷序列”中的下一個節(jié)點，記為 tmp 。
2. 將 tmp 的值覆蓋待刪除節(jié)點的值，并在樹中遞歸刪除節(jié)點 tmp 。

圖 7-21   在二叉搜索樹中刪除節(jié)點（度為 2 ）

刪除節(jié)點操作同樣使用 $O(\log ?n)$ 時間，其中查找待刪除節(jié)點需要 $O(\log ?n)$ 時間，獲取中序遍歷后繼節(jié)點需要 $O(\log ?n)$ 時間。

binary_search_tree.cpp

/* 刪除節(jié)點 */
void remove(int num) {
    // 若樹為空，直接提前返回
    if (root == nullptr)
        return;
    TreeNode *cur = root, *pre = nullptr;
    // 循環(huán)查找，越過葉節(jié)點后跳出
    while (cur != nullptr) {
        // 找到待刪除節(jié)點，跳出循環(huán)
        if (cur->val == num)
            break;
        pre = cur;
        // 待刪除節(jié)點在 cur 的右子樹中
        if (cur->val < num)
            cur = cur->right;
        // 待刪除節(jié)點在 cur 的左子樹中
        else
            cur = cur->left;
    }
    // 若無待刪除節(jié)點，則直接返回
    if (cur == nullptr)
        return;
    // 子節(jié)點數(shù)量 = 0 or 1
    if (cur->left == nullptr || cur->right == nullptr) {
        // 當子節(jié)點數(shù)量 = 0 / 1 時， child = nullptr / 該子節(jié)點
        TreeNode *child = cur->left != nullptr ? cur->left : cur->right;
        // 刪除節(jié)點 cur
        if (cur != root) {
            if (pre->left == cur)
                pre->left = child;
            else
                pre->right = child;
        } else {
            // 若刪除節(jié)點為根節(jié)點，則重新指定根節(jié)點
            root = child;
        }
        // 釋放內(nèi)存
        delete cur;
    }
    // 子節(jié)點數(shù)量 = 2
    else {
        // 獲取中序遍歷中 cur 的下一個節(jié)點
        TreeNode *tmp = cur->right;
        while (tmp->left != nullptr) {
            tmp = tmp->left;
        }
        int tmpVal = tmp->val;
        // 遞歸刪除節(jié)點 tmp
        remove(tmp->val);
        // 用 tmp 覆蓋 cur
        cur->val = tmpVal;
    }
}

4.   中序遍歷有序

如圖 7-22 所示，二叉樹的中序遍歷遵循“左 → 根 → 右”的遍歷順序，而二叉搜索樹滿足“左子節(jié)點 < 根節(jié)點 < 右子節(jié)點”的大小關(guān)系。

這意味著在二叉搜索樹中進行中序遍歷時，總是會優(yōu)先遍歷下一個最小節(jié)點，從而得出一個重要性質(zhì)：二叉搜索樹的中序遍歷序列是升序的。

利用中序遍歷升序的性質(zhì)，我們在二叉搜索樹中獲取有序數(shù)據(jù)僅需 O(n) 時間，無須進行額外的排序操作，非常高效。

圖 7-22   二叉搜索樹的中序遍歷序列

二叉搜索樹的效率

給定一組數(shù)據(jù)，我們考慮使用數(shù)組或二叉搜索樹存儲。觀察表 7-2 ，二叉搜索樹的各項操作的時間復(fù)雜度都是對數(shù)階，具有穩(wěn)定且高效的性能表現(xiàn)。只有在高頻添加、低頻查找刪除的數(shù)據(jù)適用場景下，數(shù)組比二叉搜索樹的效率更高。

表 7-2   數(shù)組與搜索樹的效率對比

在理想情況下，二叉搜索樹是“平衡”的，這樣就可以在 log?n 輪循環(huán)內(nèi)查找任意節(jié)點。

然而，如果我們在二叉搜索樹中不斷地插入和刪除節(jié)點，可能導(dǎo)致二叉樹退化為圖 7-23 所示的鏈表，這時各種操作的時間復(fù)雜度也會退化為 O(n) 。

圖 7-23   二叉搜索樹的退化

二叉搜索樹常見應(yīng)用

• 用作系統(tǒng)中的多級索引，實現(xiàn)高效的查找、插入、刪除操作。
• 作為某些搜索算法的底層數(shù)據(jù)結(jié)構(gòu)。
• 用于存儲數(shù)據(jù)流，以保持其有序狀態(tài)。