???C++?表情包趣味教程?👉?《C++要笑著學》

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

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

🔗 復習鏈接：【數(shù)據(jù)結構】二叉樹的遍歷

---

Ⅰ. 搜索二叉樹（SearchBinaryTree）

0x00 搜索二叉樹的概念

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

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

??

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

但我更喜歡叫它?"搜索二叉樹"，因為這樣翻譯過來是 "Search Binary Tree"，

?但是我并不是因為這樣可以叫它 SB?樹才喜歡的。

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

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

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

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

?這樣可以正好能對應它的性質(zhì)：左子樹的值 < 根?< 右子樹的值

🔺 結論：任意一個子樹都需要滿足，左子樹的值 < 根?< 右子樹的值，才能構成二叉搜索樹。?

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

既然叫搜索二叉樹，它肯定是用來搜索的，當滿足搜索二叉樹時你將可以快速地查找任意的值。

💭 舉個例子：?查找?

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

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

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

?所以，直接 🔒?鎖定?左子樹開始找：

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

?這次，直接?🔒鎖定 右子樹繼續(xù)找：?

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

?搜索二叉樹查找一個值的最壞情況，也只是查找高度次。?你就說爽不爽吧。

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

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

上面的例子舉得太絲滑了，會讓人誤以為搜索二叉樹的時間復雜度是??……

但實際上是?? ！！！

因為這棵樹是有可能會 蛻化 的，極端情況下會蛻化成一個 "單邊樹" ：

??

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

?但是在好的情況下，其搜索效率也是非?？捎^的：

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

? 對于時間復雜度的分析我們要做一個悲觀主義者，根據(jù)最差情況去定時間復雜度。

🔺 總結：搜索二叉樹的時間復雜度為?

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

?如果搜索二叉樹蛻化成了單邊樹，其性能也就失去了，能否進行改進讓它保持性能？

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

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

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

嚴格意義上來說滿二叉樹才是?，完全二叉樹是接近??。

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

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

0x00 搜索二叉樹的定義

?搜索二叉樹，SearchBinaryTree 名稱實在是又臭又長！

我們不如取名為 SBTree，但是 SBTree 聽起來好像有點不文明，我們還是叫 BSTree 吧。

這里我們用模板，模板參數(shù)我們給了一個 ，表示 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) {}
};

下面我們來定義整個樹，BSTreeNode 也有些長了，我們不如將其 typedef 成 Node?。

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

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

0x01?搜索二叉樹的插入

?我們先來實現(xiàn)最簡單的插入操作：

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

bool Insert(const K& key);

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

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

💡 分析

Step1：首先檢查是否有根結點 _root，如果沒有我們就 new 一個結點出來作為根結點。
此時插入成功，返回 true。

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

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

值得注意的是，我們還需要額外記錄一下 cur 的父結點，因為你不知道什么時候會碰? 結束。
并且當我們找到插入位置后，僅僅 new 上一個新結點給 cur 是完成不了插入操作的！
因為直接這么做 cur 也只是一個局部變量而已，你需要?cur 跟上一層（cur 的父親）相鏈接才行！
為了能找到上一層，所以我們還需要額外定義一個 prev 變量來記錄 cur 的父結點，
在我們更換 cur 結點時記錄父結點的位置 prev=cur?即可。
當然了，還有一種插入失敗的情況，就是判斷大小時出現(xiàn)等于的情況，返回 false 即可。
（重復的值是不允許插入的，默認情況是不允許冗余的！但是也有針對這個的變形，后續(xù)再說）

Step3：插入！new 一個新結點給 cur，此時 cur 只是一個局部變量，必須要和父親鏈接，
此時應該鏈接父親的左邊，還是鏈接父親的右邊？我們不知道，所以我們需要再做一個比較！

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

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

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

/* 插入 */
bool Insert(const K& x) {/* 檢查是否由根節(jié)點 */if (_root == nullptr) {    // 如果根節(jié)點為空指針_root = new Node(x);   // 創(chuàng)建一個新結點作為根結點return true;           // 插入成功，返回真}Node* prev = nullptr;      // 用于記錄cur的父親Node* cur = _root;         // 從根節(jié)點開始/* 找到插入位置 */while (cur != nullptr) {if (x > cur->_key) {          // 如果插入的值大于當前結點值，則向右移動prev = cur;               // 保存父節(jié)點cur = cur->_right;        // 令cur右滑}else if (x < cur->_key) {     // 如果插入的值小于當前結點值，則向左移動prev = cur;      cur = cur->_left;         // 令cur左滑}else {                        // 相等的情況，禁插return false;             // 插入失敗，返回假}}/* 插入位置已找到，準備進行鏈接操作 */cur = new Node(x);      // 創(chuàng)建一個新結點，賦給cur，此時cur為局部，需與父結點鏈接if (prev->_key > x) {   // 如果父結點的值大于插入的值，則將cur鏈接到左邊prev->_left = cur;} else {                  // 如果父節(jié)點的值小于插入的值，則將cur鏈接到右邊prev->_right = cur;}return true;   // 插入成功，返回真
}

再寫一個中序遍歷來測試一下插入的效果：

void InOrder(Node* root) {if (root == nullptr) {return;}InOrder(root->_left);            // 左cout << root->_key << " ";       // 值InOrder(root->_right);           // 右
}

模擬出一個測試用例：

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();  ? 沒法傳根
}

此時會出現(xiàn)一個問題，因為根是私有的，我們沒辦法把根傳過去。

此時我們可以選擇在類內(nèi)部寫一個成員函數(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;
};

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

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

如此一來我們在類外就可以直接調(diào)用 InOrder，并且也不需要傳遞參數(shù)了。

int main(void)
{TestBSTree();return 0;
}

🚩 運行結果：

0x02 搜索二叉樹的查找

?find 實現(xiàn)很容易，用和剛才一樣的思路，從根結點開始查找。?

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

當查找得值與 cur 的值相等時則說明找到了，返回 true。

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

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

/* 查找 */
bool Find(const K& target) {Node* cur = _root;                    // 從根結點開始查找while (cur != nullptr) {      if (target > cur->_key) {         // 如果目標值比當前結點值大，cur↘cur = cur->_right;       }else if (target < cur->_key) {    // 如果目標值比當前結點值小，cur↙cur = cur->_left;}else {                            // 如果目標值等于結點值，說明找到了/* 找到了，返回真 */return true;}}/* 沒找到，返回假 */return false;
}

0x03 搜索二叉樹刪除

搜索二叉樹真正困難的是刪除，搜索二叉樹刪除的實現(xiàn)是有很有難度的。

刪除的實現(xiàn)就需要一些 "奇技淫巧" 了，斷然刪除會毀樹。

沒有孩子或者只有一個孩子，可以直接刪除，孩子托管給父親。

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

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

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

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

找左子樹的最大值結點，或者右子樹的最小值結點。

首先要查找元素是否在二叉搜索樹中，如果不存在，則返回。

如果存在，那么刪除的結點可能分為下面四種情況：

a. 要刪除的結點無孩子結點
b. 要刪除的結點只有左孩子結點
c. 要刪除的結點只有右孩子結點
d. 要刪除的結點有左孩子結點也有右孩子結點

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

📌 因此，真正的刪除過程如下：

• 情況B：刪除該結點且使被刪除結點的父結點指向被刪除節(jié)點的左孩子結點 —— 直接刪除。
• 情況C：刪除該節(jié)點且使被刪除結點的父節(jié)點指向被刪除節(jié)點的右孩子結點 —— 直接刪除。
• 情況D：在它的右子樹中尋找中序下的第一個結點（值最小），用它的值填補到被刪除結點中，再來處理該結點的刪除問題 —— 替換法刪除。

① 該結點無左孩子

如果要刪除下面這顆二叉樹的 10 節(jié)點和 4 節(jié)點：

我們還是定義一個 cur 變量，當 cur 找到 10 結點后，如果左側為空情況如下：

1. 若該結點為 root，直接讓 root 等于它的右孩子結點。
2. 對于刪除 10 結點：若 cur==father->right，則令?parent->right = cur->right （如圖所示）
3. 對于刪除 4 結點：若 cur==father->left，則令 parent->left=cur->right （如圖所示）
4. 最后刪除 cur 結點

💬 代碼演示：

if (cur->_left == nullptr) {/* 判斷要刪除的結點是否為根結點 */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;
}

② 該結點無右孩子

?如果要刪除 14 結點，刪除邏輯和刪除左孩子是類似的：

💬 代碼演示：

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

③ 該結點有左右兩個孩子

如果刪除的結點有左右兩個孩子，我們就在它的右子樹中尋找中序的第一個結點。

即 與右子樹的最小值進行替換，當然也可以選擇左子樹的最大值進行替換。

💭 例子：比如下面這顆子樹，我們要刪除 3 結點：

如果該結點有兩個孩子，則采用如下替換法：

該結點和右子樹的最小值或左子樹的最大值進行值的替換，然后刪除替換后的結點。

這里我們采用與右子樹的最小值進行替換。

💬 代碼演示：非遞歸版本的 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é)點沒有左孩子   情況二：該節(jié)點沒有右孩子 */if (cur->_left == nullptr) {/* 判斷是否為根結點 */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) {/* 判斷是否為根結點 */if (cur == _root) {_root = cur->_left;}else {if (cur == father->_right) {/* 如果 cur 比父結點大 */father->_right = cur->_left;}else {father->_left = cur->_left;}}delete cur;cur = nullptr;}else {/* 有兩個節(jié)點，替換 */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 結點中右子樹的最小結點，替換它們的值。定義 MinParNode 為 cur，MinNode 為 cur 的右節(jié)點。首先讓 MinNode 指向 3 的右孩子（1），然后一直向左邊找知道找到 nullptr 為止，此時 MinNode 指向的就是最小的結點了，此時讓 3 與 MinNode 的值交換即可。

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

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

Ⅲ. 搜索二叉樹的應用

0x00 K 模型

?模型，即只有 key?作為關鍵碼，結構中只需存儲 key?即可，關鍵碼就是需要搜索到的值。

💭 舉個例子：對于單詞 word，我們需要判斷該單詞是否拼寫正確

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

0x01 KV 模型

?模型，每一個關鍵碼 key，都有與之對應的值 Value，即 <Key, Value> 的鍵值對。

這就像 Python 中的 dict 字典類型一樣，key 和 value 對應。

這在生活中也是非常常見的，比如英漢詞典就是英文與中文的對應關系，通過英文可以快讀檢索到對應的中文，英文單詞也可以與其對應的中文構建出一種鍵值對：

<word, chinese>

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

<word, count>

💬 代碼演示：我們實現(xiàn)一個簡單的英漢詞典 dict，可以通過英文找到對應的中文。

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

• <單詞, 中文含義>? 以鍵值對構造搜索二叉樹，值得注意的是，搜索二叉樹需要比較，鍵值對比較時只比較 Key。
• 查詢英文單詞時，只需給出英文單詞，就可以快速檢索到對應的 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{// 找到，準備開始刪除if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_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;elseparent->_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;elseminParent->_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 << "對應中文解釋：" << ret->_value << endl;}else{cout << "無此單詞" << endl;}}}void TestBSTree2(){// 統(tǒng)計水果出現(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();}
}

---

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

📜 參考資料? 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].?