繼數據結構的二叉樹學習，本篇進行更進一步的搜索二叉樹，是一種更為常見的結構

1.二叉搜索樹的概念

二叉搜索樹簡單來說就是一個排序樹

它是具有以下性質的二叉樹:

• 若它的左子樹不為空，則左子樹上所有節點的值都小于根節點的值
• 若它的右子樹不為空，則右子樹上所有節點的值都大于根節點的值
• 它的左右子樹也分別為二叉搜索樹

🔥值得注意的是： 每棵子樹都滿足該性質

2.二叉搜索樹的實現

2.1 二叉搜索樹的結構

template<class K>
struct BSTreeNode
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){ }
};

• _left： 指向左子節點的指針。
• _right： 指向右子節點的指針。
• _key： 存儲節點的鍵值

2.2 二叉搜索樹的節點尋找

2.2.1 非遞歸

bool 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 true;}}return false;
}

借助 cur 指針從根節點開始遍歷二叉搜索樹：

• 若 cur->_key 小于 key，則轉向右子樹繼續查找
• 若 cur->_key 大于 key，則轉向左子樹繼續查找
• 若 cur->_key 等于 key，說明找到了目標鍵值，返回 true
• 若遍歷結束 cur 為 nullptr，表示未找到目標鍵值，返回 false

2.2.2 遞歸

bool _FindR(Node* root, const K& key)
{if (root == nullptr)return false;if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return true;}
}

檢查基本情況： 查看當前節點 root 是否為空。若為空，返回 false，遞歸結束
比較鍵值： 若當前節點不為空，將當前節點的鍵值 root->_key 與目標鍵值 key 進行比較重復，每次遞歸調用都會將問題規模縮小，直至滿足基本情況或者找到目標節點

🔥值得注意的是： 注意這些非遞歸要放在 private，因為 root 也是 private，由于要控制子樹，必須要傳入 root，如果是 public 的話，就只能傳入自己的 root，而不是二叉搜索樹的 root，無法保證 root 的正確性

2.3 二叉搜索樹的插入

2.3.1 非遞歸

bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(key);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);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;
}

當 cur 為空時，說明已經找到了插入位置。創建一個新節點，并根據 parent 的鍵和要插入的鍵的大小關系，將新節點插入到 parent 的左子樹或右子樹中

🔥值得注意的是： 首先檢查樹是否為空，如果為空，則直接創建一個新節點作為根節點，并返回 true

2.3.2 遞歸

bool _InsertR(Node*& root, const K& key)
{if (root == nullptr){root = new Node(key);return true;}if (root->_key < key){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else{return false;}
}

這里遞歸的流程和查找的遞歸代碼幾乎一樣，唯一不同的是要傳入的 root 需要加引用，這是因為這里的代碼只執行了節點尋找創建的操作，那么當我們找到空節點并創建的時候，由于 root 是上一個 _InsertR 函數 root->_left 或 root->_right 的別名，創建的時候相當于 root->_left = new Node(key) 或 root->_right = new Node(key)，這樣才能完成鏈接

2.4 二叉搜索樹的刪除

2.4.1 非遞歸

bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{if (cur->_left == nullptr){// 左為空if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}}// 右為空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}}// 左右都不為空 else{Node* parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}swap(leftMax->_key, cur->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;return true;}}return false;
}

首先先找到需要刪除的節點，接著就需要分了討論：

1. 要刪除的結點無孩子結點
2. 要刪除的結點只有左孩子結點
3. 要刪除的結點只有右孩子結點
4. 要刪除的結點有左、右孩子結點

🔥值得注意的是： 第一點可以直接看成只有一個節點的情況，即鏈接的是空節點

刪除該結點且使被刪除節點的雙親結點指向被刪除節點的左孩子結點–直接刪除

如果待刪除節點 cur 的左子樹為空，分兩種情況處理：
如果 cur 就是根節點，那么將根節點更新為 cur 的右子樹；如果 cur 不是根節點，則根據 cur 是其父節點 parent 的左子節點還是右子節點，相應地將 parent 的左指針或右指針指向 cur 的右子樹

刪除該結點且使被刪除節點的雙親結點指向被刪除結點的右孩子結點–直接刪除

如果待刪除節點 cur 的右子樹為空，同樣分兩種情況：

若 cur 是根節點，將根節點更新為 cur 的左子樹；若 cur 不是根節點，根據 cur 是 parent 的左子節點還是右子節點，將 parent 的左指針或右指針指向 cur 的左子樹

在刪除節點的左子樹中尋找最大節點或者在它的右子樹中尋找最小節點，用它的值填補到被刪除節點中，再來處理該節點的刪除問題–替換法刪除

當待刪除節點 cur 的左右子樹都不為空時，為了保持二叉搜索樹的性質，找到 cur 左子樹中的最大節點 leftMax（即左子樹中最右側的節點）。通過一個 while 循環找到 leftMax，并記錄其父親節點 parent。然后交換 leftMax 和 cur 的鍵值，這樣就將刪除 cur 節點的問題轉化為刪除 leftMax 節點的問題，leftMax 由于是最大的節點，所以要么沒有節點，要么只有左節點

🔥值得注意的是：

Node* parent = cur 而不是 Node* parent = nullptr，因為如果第一個左子節點就是 leftMax，那么 parent 就不會改變，使用 parent 的時候就會出問題

2.4.2 遞歸

bool _EraseR(Node*& root, const K& key)
{if (root == nullptr)return false;if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;// 1、左為空// 2、右為空// 3、左右都不為空if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftMax = root->_left;while (leftMax->_right){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _EraseR(root->_left, key);}delete del;return true;}
}

將即 root 和 leftMax 的鍵值進行交換，此時原本 leftMax 節點處的鍵值變為要刪除的 key，由于交換后要刪除的節點在左子樹中，所以遞歸調用 _EraseR(root->_left, key) 繼續在左子樹中查找并刪除這個鍵值為 key 的節點。因為在左子樹中刪除節點時，可能又會遇到不同的情況（如左子樹為空、右子樹為空或左右子樹都不為空），所以遞歸調用可以繼續處理這些情況，直到成功刪除節點或者確定節點不存在

🔥值得注意的是：

這里 return _EraseR(root->_left, key) 不能寫成 return _EraseR(leftMax, key)

因為 leftMax 只是個局部變量，對其進行操作沒法改變 8 與 1 的鏈接

2.5 二叉搜索樹的拷貝

Node* Copy(Node* root)
{if (root == nullptr)return nullptr;Node* copyroot = new Node(root->_key);copyroot->_left = Copy(root->_left);copyroot->_right = Copy(root->_right);return copyroot;
}

1. 為當前節點創建一個新的節點 copyroot，新節點的鍵值和原節點 root 的鍵值相同
2. 遞歸調用 Copy 函數來拷貝原節點 root 的左子樹，將拷貝結果賦值給新節點 copyroot 的左子節點指針 _left
3. 同樣地，遞歸調用 Copy 函數來拷貝原節點 root 的右子樹，把拷貝結果賦值給新節點 copyroot 的右子節點指針 _right
4. 最后返回新創建的節點 copyroot，該節點及其子樹構成了原節點及其子樹的深拷貝

3.二叉樹的應用

🚩K模型： 即只有 key 作為關鍵碼，結構中只需要存儲 key 即可，關鍵碼即為需要搜索到的值，主要判斷在不在的場景

比如： 給一個單詞 word，判斷該單詞是否拼寫正確，具體方式如下：

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

🚩KV模型： 每一個關鍵碼 key，都有與之對應的值 value，即 <key, value> 的鍵值對，通過一個值找另外一個值

• 比如英漢詞典就是英文與中文的對應關系，通過英文可以快速找到與其對應的中文，英文單詞與其對應的中文 <word, chinese> 就構成一種鍵值對；
• 再比如統計單詞次數，統計成功后，給定單詞就可快速找到其出現的次數，單詞與其出現次數就是 <word, count> 就構成一種鍵值對

namespace key_value
{template<class K, class V>struct BSTreeNode{BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;K _key;V _value;BSTreeNode(const K& key, const V& value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};template<class K, class V>class BSTree{typedef BSTreeNode<K, V> Node;public:BSTree():_root(nullptr){}void InOrder(){_InOrder(_root);cout << endl;}Node* FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key, const V& value){return _InsertR(_root, key, value);}bool EraseR(const K& key){return _EraseR(_root, key);}private:bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;// 1、左為空// 2、右為空// 3、左右都不為空if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftMax = root->_left;while (leftMax->_right){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _EraseR(root->_left, key);}delete del;return true;}}bool _InsertR(Node*& root, const K& key, const V& value){if (root == nullptr){root = new Node(key, value);return true;}if (root->_key < key){return _InsertR(root->_right, key, value);}else if (root->_key > key){return _InsertR(root->_left, key, value);}else{return false;}}Node* _FindR(Node* root, const K& key){if (root == nullptr)return nullptr;if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return root;}}void _InOrder(Node* root){if (root == NULL){return;}_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}private:Node* _root;};

key_value 模型主要是通過一個節點里包含兩個值：key 和 value 實現的，只要找到了key 就能順便找到 value，其余的函數邏輯等都與 K 模型幾乎一致

🔥值得注意的是： 二叉搜索樹的性能是不錯的，插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個操作的性能，

• 最優情況下，二叉搜索樹為完全二叉樹(或者接近完全二叉樹)，其平均比較次數為：$lo{g}_{2}N$
• 最差情況下，二叉搜索樹退化為單支樹(或者類似單支)，其平均比較次數為：$\frac{N}{2}$

如果退化成單支樹，二叉搜索樹的性能就失去了。那能否進行改進，不論按照什么次序插入關鍵碼，二叉搜索樹的性能都能達到最優？那么我們涉及到后續章節學習的 AVL樹 和 紅黑樹

---

希望讀者們多多三連支持

小編會繼續更新

你們的鼓勵就是我前進的動力！