作者的個人gitee??

作者的算法講解主頁??

每日一言：“人生如逆旅，我亦是行人。🌸🌸”

---

🔴一、二叉搜索樹的概念

二叉搜索樹（Binary Search Tree，BST）是一種特殊的二叉樹，具有以下性質：

• 若左子樹不為空，則左子樹上所有結點的值都小于等于根結點的值。
• 若右子樹不為空，則右子樹上所有結點的值都大于等于根結點的值。
• 左右子樹也分別為二叉搜索樹。
• 二叉搜索樹中可以支持插入相等的值，也可以不支持，具體取決于使用場景的定義。如，在C++標準模板庫中，map和set不支持插入相等值，而multimap和multiset支持插入相等值。

🔴二、二叉搜索樹的性能分析

二叉搜索樹的性能主要取決于其高度。以下是不同情況下的性能分析：

情況	高度	增刪查改時間復雜度
最優	logN	O(logN)
最差	N	O(N)
平均	取決于插入順序	取決于插入順序

• 最優情況：當二叉搜索樹為完全二叉樹或接近完全二叉樹時，其高度為log2N。此時增刪查改的時間復雜度為 O(log2N)。
• 最差情況：當二叉搜索樹退化為單支樹或類似單支時，其高度為N。此時增刪查改的時間復雜度為O(N)。
• 平均情況：在實際應用中，二叉搜索樹的高度取決于插入數據的順序。如果插入數據是隨機的，那么平均情況下二叉搜索樹的性能接近最優情況；但如果插入數據是有序的，那么二叉搜索樹可能會退化為單支樹，性能接近最差情況。

🔴三、二叉搜索樹的操作

（一）插入

插入操作的步驟如下：

1. 樹為空：如果二叉搜索樹為空，則直接創建一個新的結點，并將其賦值給根指針。
2. 樹不為空：從根結點開始，按照二叉搜索樹的性質進行比較：
   • 如果插入值小于當前結點的值，則向左子樹移動。
   • 如果插入值大于當前結點的值，則向右子樹移動。
   • 如果插入值等于當前結點的值（支持插入相等值的情況），可以選擇向左或向右移動，但需要保持邏輯一致性。
3. 找到空位置：當找到一個空位置時，創建一個新的結點，并將其插入到該位置。

（二）查找

查找操作的步驟如下：

1. 從根開始：從根結點開始，將目標值與當前結點的值進行比較。
2. 比較并移動：
   • 如果目標值小于當前結點的值，則向左子樹移動。
   • 如果目標值大于當前結點的值，則向右子樹移動。
3. 查找結果：
   • 如果在某個結點找到目標值，則返回該結點。
   • 如果走到空結點仍未找到目標值，則說明目標值不存在。

（三）刪除

刪除操作相對復雜，需要分情況處理：

情況	描述	解決方案
1	要刪除結點N左右孩子均為空	把N結點的父母對應孩子指針指向空，直接刪除N結點
2	要刪除的結點N左孩子為空，右孩子結點不為空	把N結點的父母對應孩子指針指向N的右孩子，直接刪除N結點
3	要刪除的結點N右孩子為空，左孩子結點不為空	把N結點的父母對應孩子指針指向N的左孩子，直接刪除N結點
4	要刪除的結點N左右孩子結點均不為空	無法直接刪除N結點，用替換法刪除。找N左子樹的值最大結點R（最右結點）或者N右子樹的值最小結點R（最左結點）替代N，然后變成刪除R結點，R結點符合情況2或情況3，可以直接刪除

🔴四、二叉搜索樹的實現代碼

（一）結構體 BSTNode

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

（二）類 BSTree

template<class K>
class BSTree
{typedef BSTNode<K> Node;
public: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;}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; // 未找到目標值}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{// 情況1：左右孩子均為空if (cur->_left == nullptr && cur->_right == nullptr){if (parent == nullptr){_root = nullptr;}else{if (parent->_left == cur)parent->_left = nullptr;elseparent->_right = nullptr;}delete cur;return true;}// 情況2：左孩子為空，右孩子不為空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;return true;}// 情況3：右孩子為空，左孩子不為空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;return true;}// 情況4：左右孩子均不為空else{Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;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 << " ";_InOrder(root->_right);}Node* _root = nullptr;
};

🔴五、二叉搜索樹的應用場景

（一）key搜索場景

在key搜索場景中，二叉搜索樹僅存儲關鍵碼（key），用于判斷某個值是否存在。

• 小區無人值守車庫：將買了車位的業主車牌號錄入后臺系統，車輛進入時掃描車牌號，判斷其是否存在于系統中，從而決定是否抬桿。
• 英文單詞拼寫檢查：將詞庫中的所有單詞放入二叉搜索樹，讀取文章中的單詞，查找其是否存在于二叉搜索樹中，若不存在則提示拼寫錯誤。

（二）key/value搜索場景

在key/value搜索場景中，二叉搜索樹的每個結點不僅存儲關鍵碼（key），還存儲與之對應的值（value）。搜索時以key為關鍵字進行比較，可以快速找到key對應的value。

• 中英互譯字典：在樹的結點中存儲英文單詞（key）和對應的中文翻譯（value），搜索時輸入英文單詞，即可找到其對應的中文翻譯。
• 商場無人值守車庫：入口進場時掃描車牌號，記錄車牌號和入場時間（key/value），出口離場時掃描車牌號，查找入場時間，計算停車時長和費用。
• 統計文章中單詞出現次數：讀取一個單詞，查找其是否存在于二叉搜索樹中，若不存在則插入該單詞并將其出現次數初始化為1，若存在則將其對應的出現次數加1。

🔴六、總結

二叉搜索樹是一種重要的數據結構，具有插入、查找、刪除等操作。其性能在最優情況下接近O(log2N)，但在最差情況下會退化為O(N)。為了提高二叉搜索樹的性能，后續可以學習其進階，如平衡二叉搜索樹（AVL樹）、B樹和紅黑樹。

---

如果有幫助的話麻煩點個贊和關注吧，秋梨膏QAQ!