1. 二叉搜索樹的概念

二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹：

1. 若它的左子樹不為空，則左子樹上所有結點的值都小于等于根結點的值。
2. 若它的右子樹不為空，則右子樹上所有結點的值都大于等于根結點的值。
3. 它的左右子樹也分別為二叉搜索樹。
4. ?叉搜索樹中可以支持插入相等的值，也可以不支持插入相等的值，具體看使用場景定義，map/set/multimap/multiset系列容器底層就是二叉搜索樹，其中map/set不支持插入相等值，multimap/multiset支持插入相等值。
   

2. 二叉搜索樹的性能分析

最優情況下，二叉搜索樹為完全二叉樹(或者接近完全二叉樹)，其高度為： log2 N
最差情況下，二叉搜索樹退化為單支樹(或者類似單支)，其高度為： N
所以綜合而二叉搜索樹增刪查改時間復雜度為： O(N)

二分查找也可以實現 O(log2 N) 級別的查找效率，但是二分查找有兩大缺陷：

1. 需要存儲在支持下標隨機訪問的結構中，并且有序。

2. 插入和刪除數據效率很低，因為存儲在下標隨機訪問的結構中，插入和刪除數據?般需要挪動數據。

這里也就體現出了平衡二叉搜索樹的價值。

3.二叉搜索樹的插入

• 樹為空，則直接新增結點，賦值給root指針
• 樹不空，按二叉搜索樹性質，插入值比當前結點大往右走，插入值比當前結點小往左走找到空位置，插入新結點。
• 如果支持插入相等的值，插入值跟當前結點相等的值可以往右走，也可以往左走，找到空位置，插入新結點。（要注意的是要保持邏輯一致性，插入相等的值不要一會往右走，一會往左走）

4. 二叉搜索樹的查找

• 從根開始比較，查找x，x比根的值大則往右邊走查找，x比根值小則往左邊走查找。
• 最多查找高度次，走到到空，還沒找到，這個值不存在。
• 如果不支持插入相等的值，找到x即可返回
• 如果支持插入相等的值，意味著有多個x存在，一般要求查找中序的第一個x。

5. 二叉搜索樹的刪除

首先查找元素是否在二叉搜索樹中，如果不存在，則返回false。
如果查找元素存在則分以下四種情況分別處理：（假設要刪除的結點為N）

1. 要刪除結點N左右孩子均為空
2. 要刪除的結點N左孩子位空，右孩子結點不為空
3. 要刪除的結點N右孩子位空，左孩子結點不為空
4. 要刪除的結點N左右孩子結點均不為空
   對應以上四種情況的解決方案：

• 把N結點的父親對應孩子指針指向空，直接刪除N結點（情況1可以當成2或者3處理，效果是一樣的）
• 把N結點的父親對應孩子指針指向N的右孩子，直接刪除N結點
• 把N結點的父親對應孩子指針指向N的左孩子，直接刪除N結點
• 無法直接刪除N結點，因為N的兩個孩子無處安放，只能用替換法
  刪除。找N左子樹的值最大結點R(最右結點)或者N右子樹的值最小結點R(最左結點)替代N，因為這兩個結點中任意一個，放到N的位置，都滿足二叉搜索樹的規則。替代N的意思就是N和R的兩個結點的值交換，轉二變成刪除R結點，R結點符合情況2或情況3，可以直接刪除。
  
  
  

6.二叉搜索樹的實現代碼

template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
};
// Binary Search Tree
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{// 0-1個孩?的情況// 刪除情況1 2 3均可以直接刪除，改變?親對應孩?指針指向即可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;}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;}else				{// 2個孩?的情況// 刪除情況4，替換法刪除// 假設這?我們取右?樹的最?結點作為替代結點去刪除// 這?尤其要注意右?樹的根就是最?情況的情況的處理，對應課件圖中刪除8的情況// ?定要把cur給rightMinP，否會報錯。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);}private:Node * _root = nullptr;};

7. 二叉搜索樹key和key/value使用場景

7.1 key搜索場景：

場景1：小區無人值守車庫，那么物業會把買了車位的業主的
車牌號錄入后臺系統，車輛進入時掃描車牌在不在系統中，在則抬桿，不在則提示非本小區車輛，無法進入。
場景2：檢查?篇英文章單詞拼寫是否正確，將詞庫中所有單詞放?二叉搜索樹，讀取文章中的單詞，查找是否在二叉搜索樹中，不在則波浪線標紅提示。

7.2 key/value搜索場景：

每一個關鍵碼key，都有與之對應的值value，value可以任意類型對象。樹的結構中(結點)除了需要存儲key還要存儲對應的value，增/刪/查還是以key為關鍵字走二叉搜索樹的規則進行比較，可以快速查
找到key對應的value。key/value的搜索場景實現的二叉樹搜索樹支持修改，但是不支持修改key，修改key破壞搜索樹性質了，可以修改value。
場景1：簡單中英互譯字典，樹的結構中(結點)存儲key(英?)和vlaue(中文)，搜索時輸入英文，則同時查找到了英文對應的中文。
場景2：商場無人值守車庫，入口進場時掃描車牌，記錄車牌和入場時間，出口離場時，掃描車牌，查找入場時間，用當前時間-入場時間計算出停車時長，計算出停車費用，繳費后抬桿，車輛離場。
場景3：統計?篇?章中單詞出現的次數，讀取?個單詞，查找單詞是否存在，不存在這個說明第一次出現，（單詞，1），單詞存在，則++單詞對應的次數。