C++二叉搜索樹

2023-09-20 09:18 更新

圖 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)。

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

bst_search_step2

bst_search_step3

bst_search_step4

圖 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 的位置。

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

圖 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),可以直接刪除。

在二叉搜索樹中刪除節(jié)點(diǎn)(度為 0 )

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

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

在二叉搜索樹中刪除節(jié)點(diǎn)(度為 1 )

圖 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 。

在二叉搜索樹中刪除節(jié)點(diǎn)(度為 2 )

bst_remove_case3_step2

bst_remove_case3_step3

bst_remove_case3_step4

圖 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ù)組與搜索樹的效率對比

無序數(shù)組二叉搜索樹
查找元素O(n)O(log?n)
插入元素O(1)O(log?n)
刪除元素O(n)O(log?n)

在理想情況下,二叉搜索樹是“平衡”的,這樣就可以在 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)。


以上內(nèi)容是否對您有幫助:
在線筆記
App下載
App下載

掃描二維碼

下載編程獅App

公眾號(hào)
微信公眾號(hào)

編程獅公眾號(hào)