【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型

這篇具有很好參考價(jià)值的文章主要介紹了【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

???? 訂閱量破千的火熱 C++ 教程
?? 火速訂閱《C++要笑著學(xué)》?

??? CSDN 累計(jì)訂閱量破千的火爆 C/C++ 教程的 2023 重制版，C 語(yǔ)言入門到實(shí)踐的精品級(jí)趣味教程。
了解更多： ???"不太正經(jīng)" 的專欄介紹?← 試讀第一章
訂閱鏈接： ??《C語(yǔ)言趣味教程》?← 猛戳訂閱！

?? 寫在前面：半年沒更?C++ 專欄了，上一次更新還是去年九月份，被朋友催更很久了hhh

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

本章倒回?cái)?shù)據(jù)結(jié)構(gòu)專欄去講解搜索二叉樹，主要原因是講解 map 和 set 的特性需要二叉搜索樹做鋪墊，理解搜索二叉樹有助于更好地理解 map 和 set 的特性。第二個(gè)原因是為了后期講解查找效率極高的平衡搜索二叉樹，隨后再講完紅黑樹，我們就可以模擬實(shí)現(xiàn) map 和 set 了。二叉樹的基礎(chǔ)知識(shí)講解在我的《樹鋸結(jié)構(gòu)》專欄中有寫，這里放上鏈接方便復(fù)習(xí)。

?? 復(fù)習(xí)鏈接：【數(shù)據(jù)結(jié)構(gòu)】二叉樹的遍歷

? 【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ???本篇博客全站熱榜排名：13

Ⅰ. 搜索二叉樹（SearchBinaryTree）

0x00 搜索二叉樹的概念

?? 概念：搜索二叉樹又稱為二叉排序樹，它或者是一顆空樹，或者是具有以下性質(zhì)的二叉樹：

若其左子樹不是空，則左子樹上所有節(jié)點(diǎn)的值都小于根結(jié)點(diǎn)的值
若其右子樹不是空，則右子樹上所有結(jié)點(diǎn)的值都大于根結(jié)點(diǎn)的值
其左右子樹必須都是二叉搜索樹

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ??

至于叫它 "搜索二叉樹"，還是 "二叉搜索樹"，這個(gè)似乎也沒有特別的規(guī)定，應(yīng)該都是可以的。

但我更喜歡叫它?"搜索二叉樹"，因?yàn)檫@樣翻譯過(guò)來(lái)是 "Search Binary Tree"，

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ?但是我并不是因?yàn)檫@樣可以叫它 SB?樹才喜歡的。

（而且這樣也不文明，而且已經(jīng)有 SB 樹了，Size Balanced Tree）

而是因?yàn)? 叫?"搜索二叉樹 Search Binary Tree" 可以順便記住它的性質(zhì)：

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

Search Binary Tree，S 也可以表示?Small，B?也可以表示 Big，SB 即左邊小右邊大！

（一般而言，搜索二叉樹都是左邊小右邊大的）

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ?這樣可以正好能對(duì)應(yīng)它的性質(zhì)：左子樹的值 < 根?< 右子樹的值

?? 結(jié)論：任意一個(gè)子樹都需要滿足，左子樹的值 < 根?< 右子樹的值，才能構(gòu)成二叉搜索樹。?

0x01 搜索二叉樹的優(yōu)勢(shì)

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

既然叫搜索二叉樹，它肯定是用來(lái)搜索的，當(dāng)滿足搜索二叉樹時(shí)你將可以快速地查找任意的值。

?? 舉個(gè)例子：?查找 7

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

放到以前我們?nèi)绻挥枚植檎?，可能?huì)選擇用暴力的方式去從頭到尾遍歷一遍。

但現(xiàn)在學(xué)了搜索二叉樹，我們就可以輕松找到這個(gè) 7?了，不信你看：

STEP1：7?比 8?(根節(jié)點(diǎn)) 小，根據(jù)搜索二叉樹的性質(zhì)，它必然不會(huì)出現(xiàn)在右子樹 (右邊大) ！

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ?所以，直接 ???鎖定?左子樹開始找：

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

STEP2：?7?比 3 大，根據(jù)性質(zhì)它肯定不會(huì)出現(xiàn)在左子樹 (左邊小) ！

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ?這次，直接???鎖定 右子樹繼續(xù)找：?

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

STEP3：?我們繼續(xù)對(duì)比，7?比 6?大，所以在右邊，就這么輕輕松松的找到了：

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ?搜索二叉樹查找一個(gè)值的最壞情況，也只是查找高度次。?你就說(shuō)爽不爽吧。

這就是搜索二叉樹，它的搜索功能是真的名副其實(shí)的厲害！

0x02?二叉搜索樹的時(shí)間復(fù)雜度：O(N)

上面的例子舉得太絲滑了，會(huì)讓人誤以為搜索二叉樹的時(shí)間復(fù)雜度是??……

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型但實(shí)際上是?? ?。?！

因?yàn)檫@棵樹是有可能會(huì) 蛻化 (Degenerate) 的，極端情況下會(huì)蛻化成一個(gè) "單邊樹" ：

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ??

?? 最差情況：二叉搜索樹蛻化為單邊樹（或類似單邊），其平均比較次數(shù)為：

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ?但是在好的情況下，其搜索效率也是非?？捎^的：

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

?? 最優(yōu)情況：二叉搜索樹為完全二叉樹（或接近完全二叉樹），其平均比較次數(shù)為：

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ? 對(duì)于時(shí)間復(fù)雜度的分析我們要做一個(gè)悲觀主義者，根據(jù)最差情況去定時(shí)間復(fù)雜度。

?? 總結(jié)：搜索二叉樹的時(shí)間復(fù)雜度為 O(n)?

0x03 搜索二叉樹的改良方案

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ?如果搜索二叉樹蛻化成了單邊樹，其性能也就失去了，能否進(jìn)行改進(jìn)讓它保持性能？

如何做到不論按照上面次序插入關(guān)鍵碼，二叉搜索樹的性能均能達(dá)到最優(yōu)？

搜索二叉樹由于控制不了極端情況，與??失之交臂，但平衡二叉搜索樹做到了。

"平衡二叉樹的搜索效率極高"

嚴(yán)格意義上來(lái)說(shuō)滿二叉樹才是?，完全二叉樹是接近??。

而平衡搜索二叉樹維持左右兩邊均勻程度，讓它接近完全二叉樹，從而讓效率趨近?。

Ⅱ.?搜索二叉樹的實(shí)現(xiàn)

0x00 搜索二叉樹的定義

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ?搜索二叉樹，SearchBinaryTree 名稱實(shí)在是又臭又長(zhǎng)！

我們不如取名為 SBTree，但是 SBTree 聽起來(lái)好像有點(diǎn)不文明，我們還是叫 BSTree 吧。

這里我們用模板，模板參數(shù)我們給了一個(gè) ，表示 key 的意思（模板參數(shù)并非一定要用 T）。

template<class K> 
struct BSTreeNode {
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

	BSTreeNode(const K& key)
		: _left(nullptr)
		, _right(nullptr)
		, _key(key) {}
};

下面我們來(lái)定義整個(gè)樹，BSTreeNode 也有些長(zhǎng)了，我們不如將其 typedef 成 Node?。

這里我們構(gòu)造函數(shù)都沒必要寫，它自己生成的就夠用了：

template<class K> 
class BSTree {
	typedef BSTreeNode<K> Node;
private:
	Node* _root = nullptr;    // 懶得寫構(gòu)造函數(shù)了
};

0x01?搜索二叉樹的插入

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ?我們先來(lái)實(shí)現(xiàn)最簡(jiǎn)單的插入操作：

如果樹為空，則直接新增結(jié)點(diǎn)，賦值給 root 指針。
如果樹不為空，按二叉搜索樹性質(zhì)查找插入位置，插入新節(jié)點(diǎn)。

bool Insert(const K& key);

Insert 的實(shí)現(xiàn)我們可以用遞歸，也可以用非遞歸，這一塊遞歸比非遞歸更難理解。

秉著先難后易的態(tài)度，我們先講比較難理解的非遞歸版本！

?? 分析

Step1：首先檢查是否有根結(jié)點(diǎn) _root，如果沒有我們就 new 一個(gè)結(jié)點(diǎn)出來(lái)作為根結(jié)點(diǎn)。
此時(shí)插入成功，返回 true。

Step2：插入就需要找到插入位置，我們定義一個(gè) cur 變量，從根節(jié)點(diǎn)開始，
根據(jù)搜索二叉樹 "SB" 性質(zhì)，將 cur 結(jié)點(diǎn)的值與插入的值 ?進(jìn)行大小比較。

如果插入的值大于當(dāng)前結(jié)點(diǎn)值，則將 cur 結(jié)點(diǎn)向右移動(dòng)?cur=cur->_right?；
如果插入的值小于當(dāng)前節(jié)點(diǎn)值，就將 cur 結(jié)點(diǎn)向左移動(dòng) cur=cur->_left。

值得注意的是，我們還需要額外記錄一下 cur 的父結(jié)點(diǎn)，因?yàn)槟悴恢朗裁磿r(shí)候會(huì)碰? 結(jié)束。
并且當(dāng)我們找到插入位置后，僅僅 new 上一個(gè)新結(jié)點(diǎn)給 cur 是完成不了插入操作的！
因?yàn)橹苯舆@么做 cur 也只是一個(gè)局部變量而已，你需要?cur 跟上一層（cur 的父親）相鏈接才行！
為了能找到上一層，所以我們還需要額外定義一個(gè) prev 變量來(lái)記錄 cur 的父結(jié)點(diǎn)，
在我們更換 cur 結(jié)點(diǎn)時(shí)記錄父結(jié)點(diǎn)的位置 prev=cur?即可。
當(dāng)然了，還有一種插入失敗的情況，就是判斷大小時(shí)出現(xiàn)等于的情況，返回 false 即可。
（重復(fù)的值是不允許插入的，默認(rèn)情況是不允許冗余的！但是也有針對(duì)這個(gè)的變形，后續(xù)再說(shuō)）

Step3：插入！new 一個(gè)新結(jié)點(diǎn)給 cur，此時(shí) cur 只是一個(gè)局部變量，必須要和父親鏈接，
此時(shí)應(yīng)該鏈接父親的左邊，還是鏈接父親的右邊？我們不知道，所以我們需要再做一個(gè)比較！

如果父節(jié)點(diǎn)的值大于插入的值，則將 cur 鏈接到父親左邊 prev->_left=cur；
反之將 cur 鏈接到父親右邊? prev->_right=cur。

最后，插入成功返回?true，我們的插入操作就大功告成了。

?? 代碼演示：Insert 接口的實(shí)現(xiàn)

/* 插入 */
bool Insert(const K& x) {
    /* 檢查是否由根節(jié)點(diǎn) */
    if (_root == nullptr) {    // 如果根節(jié)點(diǎn)為空指針
        _root = new Node(x);   // 創(chuàng)建一個(gè)新結(jié)點(diǎn)作為根結(jié)點(diǎn)
        return true;           // 插入成功，返回真
    }

    Node* prev = nullptr;      // 用于記錄cur的父親
    Node* cur = _root;         // 從根節(jié)點(diǎn)開始

    /* 找到插入位置 */
    while (cur != nullptr) {
        if (x > cur->_key) {          // 如果插入的值大于當(dāng)前結(jié)點(diǎn)值，則向右移動(dòng)
            prev = cur;               // 保存父節(jié)點(diǎn)
            cur = cur->_right;        // 令cur右滑
        }
        else if (x < cur->_key) {     // 如果插入的值小于當(dāng)前結(jié)點(diǎn)值，則向左移動(dòng)
            prev = cur;      
            cur = cur->_left;         // 令cur左滑
        }
        else {                        // 相等的情況，禁插
            return false;             // 插入失敗，返回假
        }
    }

    /* 插入位置已找到，準(zhǔn)備進(jìn)行鏈接操作 */
    cur = new Node(x);      // 創(chuàng)建一個(gè)新結(jié)點(diǎn)，賦給cur，此時(shí)cur為局部，需與父結(jié)點(diǎn)鏈接
    if (prev->_key > x) {   // 如果父結(jié)點(diǎn)的值大于插入的值，則將cur鏈接到左邊
        prev->_left = cur;
    } 
    else {                  // 如果父節(jié)點(diǎn)的值小于插入的值，則將cur鏈接到右邊
        prev->_right = cur;
    }

    return true;   // 插入成功，返回真
}

再寫一個(gè)中序遍歷來(lái)測(cè)試一下插入的效果：

void InOrder(Node* root) {
    if (root == nullptr) {
        return;
    }

    InOrder(root->_left);            // 左
    cout << root->_key << " ";       // 值
    InOrder(root->_right);           // 右
}

模擬出一個(gè)測(cè)試用例：

void TestBSTree() {
	BSTree<int> t;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a) {
		t.Insert(e);
	}
	t.InOrder();  ? 沒法傳根
}

此時(shí)會(huì)出現(xiàn)一個(gè)問(wèn)題，因?yàn)楦撬接械?，我們沒辦法把根傳過(guò)去。

此時(shí)我們可以選擇在類內(nèi)部寫一個(gè)成員函數(shù) GetRoot 去取根，但是這里我們可以選擇這么做：

	void InOrder() {
		_InOrder(_root);
	}

private:
    // 改為內(nèi)部函數(shù)
	void _InOrder(Node* root) {
		if (root == nullptr) {
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

	Node* _root = nullptr;
};

干脆將剛才我們實(shí)現(xiàn)的中序設(shè)為 private 私有，然后再寫一個(gè) InOrder 放在公有的區(qū)域。

這就是在類內(nèi)訪問(wèn) _root 了，沒有什么問(wèn)題。

如此一來(lái)我們?cè)陬愅饩涂梢灾苯诱{(diào)用 InOrder，并且也不需要傳遞參數(shù)了。

int main(void)
{
	TestBSTree();

	return 0;
}

?? 運(yùn)行結(jié)果：

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

0x02 搜索二叉樹的查找

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ?find 實(shí)現(xiàn)很容易，用和剛才一樣的思路，從根結(jié)點(diǎn)開始查找。?

從根開始，如果要查找的值大于 cur 目前的值，則讓 cur 往右走，反之往左走。

當(dāng)查找得值與 cur 的值相等時(shí)則說(shuō)明找到了，返回 true。

當(dāng) cur 觸及到空（while 循環(huán)結(jié)束）則說(shuō)明找不到，返回 false。

?? 代碼實(shí)現(xiàn)：搜索二叉樹的查找

/* 查找 */
bool Find(const K& target) {
    Node* cur = _root;                    // 從根結(jié)點(diǎn)開始查找

    while (cur != nullptr) {      
        if (target > cur->_key) {         // 如果目標(biāo)值比當(dāng)前結(jié)點(diǎn)值大，cur↘
            cur = cur->_right;       
        }
        else if (target < cur->_key) {    // 如果目標(biāo)值比當(dāng)前結(jié)點(diǎn)值小，cur↙
            cur = cur->_left;
        }
        else {                            // 如果目標(biāo)值等于結(jié)點(diǎn)值，說(shuō)明找到了
            /* 找到了，返回真 */
            return true;
        }
    }
    /* 沒找到，返回假 */
    return false;
}

0x03 搜索二叉樹刪除

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型搜索二叉樹真正困難的是刪除，搜索二叉樹刪除的實(shí)現(xiàn)是有很有難度的。

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型刪除的實(shí)現(xiàn)就需要一些 "奇技淫巧" 了，斷然刪除會(huì)毀樹。

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型沒有孩子或者只有一個(gè)孩子，可以直接刪除，孩子托管給父親。

兩個(gè)還是沒辦法給父親，父親養(yǎng)不了這么多孩子，但是可以找個(gè)人替代父親養(yǎng)孩子。

當(dāng)然，也不能隨便找，找的人必須仍然維持搜索二叉樹的性質(zhì)，這是原則。

"你不能說(shuō)搞得我都不是搜索二叉樹了，那還玩?zhèn)€錘子"

必須比左邊的大，比右邊的小。所以在家族中找是最合適的。

找左子樹的最大值結(jié)點(diǎn)，或者右子樹的最小值結(jié)點(diǎn)。

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型首先要查找元素是否在二叉搜索樹中，如果不存在，則返回。

如果存在，那么刪除的結(jié)點(diǎn)可能分為下面四種情況：

a. 要?jiǎng)h除的結(jié)點(diǎn)無(wú)孩子結(jié)點(diǎn)
b. 要?jiǎng)h除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)
c. 要?jiǎng)h除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)
d. 要?jiǎng)h除的結(jié)點(diǎn)有左孩子結(jié)點(diǎn)也有右孩子結(jié)點(diǎn)

看起來(lái)有待刪除節(jié)點(diǎn)有 4 種情況，但實(shí)際上 a 和 b，或 a 和 c 可以合并。

?? 因此，真正的刪除過(guò)程如下：

情況B：刪除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)的父結(jié)點(diǎn)指向被刪除節(jié)點(diǎn)的左孩子結(jié)點(diǎn) —— 直接刪除。
情況C：刪除該節(jié)點(diǎn)且使被刪除結(jié)點(diǎn)的父節(jié)點(diǎn)指向被刪除節(jié)點(diǎn)的右孩子結(jié)點(diǎn) —— 直接刪除。
情況D：在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)（值最?。?，用它的值填補(bǔ)到被刪除結(jié)點(diǎn)中，再來(lái)處理該結(jié)點(diǎn)的刪除問(wèn)題 —— 替換法刪除。

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

① 該結(jié)點(diǎn)無(wú)左孩子

如果要?jiǎng)h除下面這顆二叉樹的 10 節(jié)點(diǎn)和 4 節(jié)點(diǎn)：

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型我們還是定義一個(gè) cur 變量，當(dāng) cur 找到 10 結(jié)點(diǎn)后，如果左側(cè)為空情況如下：

若該結(jié)點(diǎn)為 root，直接讓 root 等于它的右孩子結(jié)點(diǎn)。
對(duì)于刪除 10 結(jié)點(diǎn)：若 cur==father->right，則令?parent->right = cur->right （如圖所示）
對(duì)于刪除 4 結(jié)點(diǎn)：若 cur==father->left，則令 parent->left=cur->right （如圖所示）
最后刪除 cur 結(jié)點(diǎn)

?? 代碼演示：

if (cur->_left == nullptr) {
    /* 判斷要?jiǎng)h除的結(jié)點(diǎn)是否為根結(jié)點(diǎn) */
    if (cur == _root) {
        _root = cur->_right;
    }
    else {
        if (cur == father->_right) {
            /* 如果 cur 比 father 大 */
            father->_right = cur->_right;
        }
        else {
            father->_left = cur->_right;
        }
    }
    delete cur;
    cur = nullptr;
}

② 該結(jié)點(diǎn)無(wú)右孩子

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型 ?如果要?jiǎng)h除 14 結(jié)點(diǎn)，刪除邏輯和刪除左孩子是類似的：

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

?? 代碼演示：

else if (cur->_right == nullptr) {
    /* 判斷是否為根結(jié)點(diǎn) */
    if (cur == _root) {
        _root = cur->_left;
    }
    else {
        if (cur == father->_right) {
            /* cur 比父結(jié)點(diǎn)大 */
            father->_right = cur->_left;
        }
        else {
            father->_left = cur->_left;
        }
    }
    delete cur;
    cur = nullptr;
}

③ 該結(jié)點(diǎn)有左右兩個(gè)孩子

如果刪除的結(jié)點(diǎn)有左右兩個(gè)孩子，我們就在它的右子樹中尋找中序的第一個(gè)結(jié)點(diǎn)。

即與右子樹的最小值進(jìn)行替換，當(dāng)然也可以選擇左子樹的最大值進(jìn)行替換。

?? 例子：比如下面這顆子樹，我們要?jiǎng)h除 3 結(jié)點(diǎn)：

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型如果該結(jié)點(diǎn)有兩個(gè)孩子，則采用如下替換法：

該結(jié)點(diǎn)和右子樹的最小值或左子樹的最大值進(jìn)行值的替換，然后刪除替換后的結(jié)點(diǎn)。

這里我們采用與右子樹的最小值進(jìn)行替換。

?? 代碼演示：非遞歸版本的 Erase

bool Erase(const K& key) {
    Node* father = nullptr;
    Node* cur = _root;
    while (cur != nullptr) {
        if (cur->_key < key) {
            father = cur;
            cur = cur->_right;
        }
        else if (cur->_key > key)
        {
            father = cur;
            cur = cur->_left;
        }
        else {
            /* 找到了！ 情況一：該節(jié)點(diǎn)沒有左孩子   情況二：該節(jié)點(diǎn)沒有右孩子 */
            if (cur->_left == nullptr) {
                /* 判斷是否為根結(jié)點(diǎn) */
                if (cur == _root) {
                    _root = cur->_right;
                }
                else {
                    if (cur == father->_right) {
                        //cur 比 father大
                        father->_right = cur->_right;
                    }
                    else {
                        father->_left = cur->_right;
                    }
                }
                delete cur;
                cur = nullptr;
            }
            else if (cur->_right == nullptr) {
                /* 判斷是否為根結(jié)點(diǎn) */
                if (cur == _root) {
                    _root = cur->_left;
                }
                else {
                    if (cur == father->_right) {
                        /* 如果 cur 比父結(jié)點(diǎn)大 */
                        father->_right = cur->_left;
                    }
                    else {
                        father->_left = cur->_left;
                    }
                }
                delete cur;
                cur = nullptr;
            }
            else {
                /* 有兩個(gè)節(jié)點(diǎn)，替換 */
                Node* MinParNode = cur;
                Node* MinNode = cur->_right;
                while (MinNode->_left) {
                    MinParNode = MinNode;
                    MinNode = MinNode->_left;
                }
                swap(cur->_key, MinNode->_key);

                if(MinParNode->_left == MinNode) {
                    MinParNode->_left = MinNode->_right;
                }
                else {
                    MinParNode->_right = MinNode->_right;
                }
                delete MinNode;
                MinNode = nullptr;
            }
            return true;
        }
    }
    return false;
}

?? 解讀：找到 3 結(jié)點(diǎn)中右子樹的最小結(jié)點(diǎn)，替換它們的值。定義 MinParNode 為 cur，MinNode 為 cur 的右節(jié)點(diǎn)。首先讓 MinNode 指向 3 的右孩子（1），然后一直向左邊找知道找到 nullptr 為止，此時(shí) MinNode 指向的就是最小的結(jié)點(diǎn)了，此時(shí)讓 3 與 MinNode 的值交換即可。

交換后，刪除 3 就變成了刪除 MinNode，我們需要弄清 MinNode? 和 MinParNode 的指向關(guān)系：

如果 MinParNode 的左孩子是 MinNode，則讓 MinParNode 的左指向 MinNode 的右。
如果 MinParNode 的右孩子是 MinNode，則讓 MinParNode 的右指向 MinNode 的右。（這里讓 MinParNode 指向 MinNode 的右的原因是?MinNode 已是最小結(jié)點(diǎn)，不可能有左孩子了）

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

Ⅲ. 搜索二叉樹的應(yīng)用

0x00 K 模型

?模型，即只有 key?作為關(guān)鍵碼，結(jié)構(gòu)中只需存儲(chǔ) key?即可，關(guān)鍵碼就是需要搜索到的值。

?? 舉個(gè)例子：對(duì)于單詞 word，我們需要判斷該單詞是否拼寫正確

以單詞集合中的每個(gè)單詞作為 key，構(gòu)建一個(gè)搜索二叉樹。
在二叉樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯(cuò)誤。

0x01 KV 模型

?模型，每一個(gè)關(guān)鍵碼 key，都有與之對(duì)應(yīng)的值 Value，即 <Key, Value> 的鍵值對(duì)。

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型這就像 Python 中的 dict 字典類型一樣，key 和 value 對(duì)應(yīng)。

這在生活中也是非常常見的，比如英漢詞典就是英文與中文的對(duì)應(yīng)關(guān)系，通過(guò)英文可以快讀檢索到對(duì)應(yīng)的中文，英文單詞也可以與其對(duì)應(yīng)的中文構(gòu)建出一種鍵值對(duì)：

<word, chinese>

再比如統(tǒng)計(jì)單詞次數(shù)，統(tǒng)計(jì)成功后，給定的單詞就課快速找到其出現(xiàn)的次數(shù)，單詞與其出現(xiàn)的次數(shù)就構(gòu)建出了一種鍵值對(duì)：

<word, count>

?? 代碼演示：我們實(shí)現(xiàn)一個(gè)簡(jiǎn)單的英漢詞典 dict，可以通過(guò)英文找到對(duì)應(yīng)的中文。

具體實(shí)現(xiàn)方式如下：

<單詞, 中文含義>? 以鍵值對(duì)構(gòu)造搜索二叉樹，值得注意的是，搜索二叉樹需要比較，鍵值對(duì)比較時(shí)只比較 Key。
查詢英文單詞時(shí)，只需給出英文單詞，就可以快速檢索到對(duì)應(yīng)的 Key

namespace KV
{
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _value;

		//pair<K, V> _kv;

		BSTreeNode(const K& key, const V& value)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value)
		{}
	};

	template<class K, class V>
	struct BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		BSTree()
			:_root(nullptr)
		{}

		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;

			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(key, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;
		}

		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;
				}
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;

			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					// 找到，準(zhǔn)備開始刪除
					if (cur->_left == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
								parent->_left = cur->_right;
							else
								parent->_right = cur->_right;
						}

						delete cur;
					}
					else if (cur->_right == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
								parent->_left = cur->_left;
							else
								parent->_right = cur->_left;
						}

						delete cur;
					}
					else
					{
						Node* minParent = cur;
						Node* min = cur->_right;
						while (min->_left)
						{
							minParent = min;
							min = min->_left;
						}

						cur->_key = min->_key;
						cur->_value = min->_value;


						if (minParent->_left == min)
							minParent->_left = min->_right;
						else
							minParent->_right = min->_right;

						delete min;
					}

					return true;
				}
			}

			return false;
		}

	

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root;
	};

	void TestBSTree1()
	{
		// 字典KV模型
		BSTree<string, string> dict;
		dict.Insert("sort", "排序");
		dict.Insert("left", "左邊");
		dict.Insert("right", "右邊");
		dict.Insert("map", "地圖、映射");
		//...

		string str;
		while (cin>>str)
		{
			BSTreeNode<string, string>* ret = dict.Find(str);
			if (ret)
			{
				cout << "對(duì)應(yīng)中文解釋：" << ret->_value << endl;
			}
			else
			{
				cout << "無(wú)此單詞" << endl;
			}
		}
	}

	void TestBSTree2()
	{
		// 統(tǒng)計(jì)水果出現(xiàn)次數(shù)
		string arr[] = { "蘋果", "西瓜","草莓", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };
		BSTree<string, int> countTree;
		for (auto& str : arr)
		{
			//BSTreeNode<string, int>* ret = countTree.Find(str);
			auto ret = countTree.Find(str);
			if (ret != nullptr)
			{
				ret->_value++;
			}
			else
			{
				countTree.Insert(str, 1);
			}
		}

		countTree.InOrder();
	}
}

【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型

?? [ 筆者 ]? ?王亦優(yōu)
?? [ 更新 ]? ?2023.4.8
? [ 勘誤 ]?? /* 暫無(wú) */
?? [ 聲明 ]? ?由于作者水平有限，本文有錯(cuò)誤和不準(zhǔn)確之處在所難免，
              本人也很想知道這些錯(cuò)誤，懇望讀者批評(píng)指正！

?? 參考資料?

C++reference[EB/OL]. []. http://www.cplusplus.com/reference/.

Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

百度百科[EB/OL]. []. https://baike.baidu.com/.

比特科技. C++[EB/OL]. 2021[2021.8.31].?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-412488.html

到了這里，關(guān)于【C++要笑著學(xué)】搜索二叉樹 (SBTree) | K 模型 | KV 模型的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！