C++二叉搜索樹

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

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

圖 7-16   二叉搜索樹

二叉搜索樹的操作

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

1.   查找節(jié)點(diǎn)

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

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

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

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

binary_search_tree.cpp

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

2.   插入節(jié)點(diǎn)

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

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

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

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

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

binary_search_tree.cpp

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

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

3.   刪除節(jié)點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

binary_search_tree.cpp

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

4.   中序遍歷有序

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

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

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

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

二叉搜索樹的效率

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

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

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

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

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

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

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