目錄

??叉搜索樹的概念

?二叉搜索數的性能分析

二叉搜索樹的模擬實現

定義二叉樹節點結構

?二叉搜索樹的插入

二叉搜索樹的查找

?二叉搜索樹的刪除

中序遍歷?

全部代碼

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

?key搜索場景：

key/value搜索場景：

key/value?叉搜索樹代碼實現

---

?二叉搜索樹的概念

?叉搜索樹?稱?叉排序樹，它或者是?棵空樹，或者是具有以下性質的?叉樹:
? 若它的左?樹不為空，則左?樹上所有結點的值都?于等于根結點的值
? 若它的右?樹不為空，則右?樹上所有結點的值都?于等于根結點的值
? 它的左右?樹也分別為?叉搜索樹
? ?叉搜索樹中可以?持插?相等的值，也可以不?持插?相等的值，具體看使?場景定義

后續我們學習map/set/multimap/multiset系列容器底層就是?叉搜索樹，其中map/set不?持插?相等值，multimap/multiset?持插?相等值?。

?二叉搜索數的性能分析

最優情況：二叉搜索樹為完全二叉樹(或者接近完全二叉樹），其高度為：?log2 N

最差情況：二叉搜索樹為單支數，其高度為N

所以所以綜合???叉搜索樹增刪查改時間復雜度為： O(N)

那么這樣的效率顯然是?法滿?我們需求的，我們后續課程需要繼續講解?叉搜索樹的變形，平衡?叉搜索樹AVL樹和紅?樹，才能適?于我們在內存中存儲和搜索數據。
另外需要說明的是，?分查找也可以實現 O(log2 N) 級別的查找效率，但是?分查找有兩?缺陷：
1. 需要存儲在?持下標隨機訪問的結構中，并且有序。
2. 插?和刪除數據效率很低，因為存儲在下標隨機訪問的結構中，插?和刪除數據?般需要挪動數
據。
這?也就體現出了平衡?叉搜索樹的價值。

二叉搜索樹的模擬實現

定義二叉樹節點結構

定義一個二叉樹節點類，包含節點的值、左子節點指針和右子節點指針。

template<class T>
struct BSNode
{T _data;BSNode<T>* _left;BSNode<T>* _right;
//初始化節點，定義成有參的，后面新增節點需要調用BSNode(const T& data):_data(data), _left(nullptr), _right(nullptr){}
};

?二叉搜索樹的插入

插?的具體過程如下：
1. 樹為空，則直接新增結點，賦值給root指針
2. 樹不空，按?叉搜索樹性質，插?值?當前結點?往右?，插?值?當前結點?往左?，找到空位置，插?新結點。
3. 如果?持插?相等的值，插?值跟當前結點相等的值可以往右?，也可以往左?，找到空位置，插?新結點。（要注意的是要保持邏輯?致性，插?相等的值不要?會往右?，?會往左?）

template<class T>
class BSTree
{typedef BSNode<T> Node;
public:
//此插入不插入相同的bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_data > data){parent = cur;cur = cur->_left;}else if (cur->_data < data){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(data);if (parent->_data > data){parent->_left = cur;}else{parent->_right = cur;}return true;}
//相同的向右走
/*bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_data > data){parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}cur = new Node(data);if (parent->_data > data){parent->_left = cur;}else{parent->_right = cur;}return true;}*/
//相同的向左走
/*bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_data < data){parent = cur;cur = cur->_right;}else{parent = cur;cur = cur->_left;}}cur = new Node(data);if (parent->_data < data){parent->_right = cur;}else{parent->_left = cur;}return true;}*/
private:Node* _root=nullptr;
};

二叉搜索樹的查找

1. 從根開始?較，查找x，x?根的值?則往右邊?查找，x?根值?則往左邊?查找。
2. 最多查找?度次，?到到空，還沒找到，這個值不存在。
3. 如果不?持插?相等的值，找到x即可返回
4. 如果?持插?相等的值，意味著有多個x存在，?般要求查找中序的第?個x。

    bool Find(const T&data){Node* cur = _root;while (cur){if (cur->_data > data){cur = cur->_left;}else if ((cur->_data < data)){cur = cur->_right;}elsereturn true;}return false;}

?二叉搜索樹的刪除

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

1. 要刪除結點N左右孩?均為空
2. 要刪除的結點N左孩?位空，右孩?結點不為空
3. 要刪除的結點N右孩?位空，左孩?結點不為空
4. 要刪除的結點N左右孩?結點均不為空

對應以上四種情況的解決?案：

1. 把N結點的?親對應孩?指針指向空，直接刪除N結點
2. 把N結點的?親對應孩?指針指向N的右孩?，直接刪除N結點
3. 把N結點的?親對應孩?指針指向N的左孩?，直接刪除N結點
4. ?法直接刪除N結點，因為N的兩個孩??處安放，只能?替換法刪除。找N左?樹的值最?結點R(最右結點)或者N右?樹的值最?結點R(最左結點)替代N，因為這兩個結點中任意?個，放到N的位置，都滿??叉搜索樹的規則。替代N的意思就是N和R的兩個結點的值交換，轉?變成刪除R結點，可以直接刪除。

    bool Erase(const T& data){if (!Find(data)){return false;}Node* parent = nullptr;//漏了分號，編譯器報錯錯誤。Node*cur = _root;while (cur){if (cur->_data > data){parent = cur;cur=cur->_left;}else if (cur->_data < data){parent = cur;cur = cur->_right;}else{//開始刪除//cur只有右節點if (cur->_left==nullptr){if (cur == _root){_root = cur->_right;}else{if (cur == parent->_right){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;return true;}//cur只有左節點else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;return true;}else{//cur的左右子樹都不為空//找右子樹的最小節點（最左節點）代替Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace=replace->_left;}swap(cur->_data, replace->_data);//replace 已經是最左節點了，所以replace只可能是葉子節點后者只有右節點if (replaceParent->_left == replace){replaceParent->_left = replace->_right;}else{replaceParent->_right= replace->_right;}delete replace;return true;}}}return false;}

中序遍歷?

用中序遍歷我們就可以得到從小到大的排序。

void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_data << " ";_InOrder(root->_right);}

全部代碼

#include<iostream>
//cout endl swap都在這個頭文件中
using namespace std;
template<class T>
struct BSNode
{T _data;BSNode<T>* _left;BSNode<T>* _right;BSNode(const T& data):_data(data), _left(nullptr), _right(nullptr){}
};
template<class T>
class BSTree
{typedef BSNode<T> Node;
public:bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_data > data){parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}cur = new Node(data);if (parent->_data > data){parent->_left = cur;}else{parent->_right = cur;}return true;}bool Find(const T&data){Node* cur = _root;while (cur){if (cur->_data > data){cur = cur->_left;}else if ((cur->_data < data)){cur = cur->_right;}elsereturn true;}return false;}bool Erase(const T& data){if (!Find(data)){return false;}Node* parent = nullptr;//漏了分號，編譯器報錯錯誤。Node*cur = _root;while (cur){if (cur->_data > data){parent = cur;cur=cur->_left;}else if (cur->_data < data){parent = cur;cur = cur->_right;}else{//開始刪除//cur有0/1個孩子if (cur->_left==nullptr){if (cur == _root){_root = cur->_right;}else{if (cur == parent->_right){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;return true;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;return true;}else{//cur的左右子樹都不為空（有兩個孩子//找右子樹的最小節點（最左節點）代替Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace=replace->_left;}swap(cur->_data, replace->_data);//replace 已經是最左節點了，所以replace只可能是葉子節點或者還有右節點if (replaceParent->_left == replace){replaceParent->_left = replace->_right;}else{replaceParent->_right= replace->_right;}delete replace;return true;}}}return false;}void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_data << " ";_InOrder(root->_right);}
private:Node* _root=nullptr;
};

上文中的T相當于就是下文中的K，_data相當于key。

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

?key搜索場景：

只有key作為關鍵碼，結構中只需要存儲key即可，關鍵碼即為需要搜索到的值，搜索場景只需要判斷key在不在。key的搜索場景實現的?叉樹搜索樹支持增刪查，但是不支持修改，修改key破壞搜索樹結構了。

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

key/value搜索場景：

每?個關鍵碼key，都有與之對應的值value，value可以任意類型對象。樹的結構中(結點)除了需要存儲key還要存儲對應的value，增/刪/查還是以key為關鍵字??叉搜索樹的規則進??較，可以快速查找到key對應的value。key/value的搜索場景實現的?叉樹搜索樹?持修改，但是不?持修改key修改key破壞搜索樹性質了，可以修改value。

場景1：簡單中英互譯字典，樹的結構中(結點)存儲key(英文)和vlaue(中文），搜索時輸入英文，則同時查找到了英文對應的中文。
場景2：商場無人值守車庫，入口進場時掃描車牌，記錄車牌和入場時間，出口離場時，掃描車牌，查找?場時間，?當前時間-入場時間計算出停車時長，計算出停車費用，繳費后抬桿，車輛離場。
場景3：統計?篇文章中單詞出現的次數，讀取?個單詞，查找單詞是否存在，不存在這個說明第?次出現，（單詞，1），單詞存在，則++單詞對應的次數。

key/value?叉搜索樹代碼實現

#include<iostream>
using namespace std;
template <class K,class V>
struct BSNode {BSNode<K,V>* _left;BSNode<K, V>* _right;K _key;V _value;BSNode(const K& key, const V& value):_left(nullptr), _right(nullptr), _key(key), _value(value){}
};
template< class K, class V>
class BSTree
{typedef BSNode<K, V> Node;
public:void destroy(Node* root){if (root == nullptr){return;}destroy(root->_left);destroy(root->_right);delete root;}~BSTree(){destroy(_root);_root = nullptr;}bool Insert(const K& key, const V& val){if (_root == nullptr){_root = new Node(key, val);return true;}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{return false;}}cur = new Node(key, val);if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}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->_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;}}delete cur;return true;}else if(cur->_right==nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;return true;}else{Node* repalceP = cur;Node* repalce = repalceP->_right;while (repalce->left){repalceP = repalce;repalce = repalce->_left;}cur->_key = repalce->_key;cur->_value = repalce->_value;if (repalceP->_left == repalce){repalceP->_left = repalce->_right;}else{repalceP->_right = repalce->_right;}delete repalce;return true;}}}return false;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl; _InOrder(root->_right);}void InOrder(){_InOrder(_root);cout << endl;}
private:Node* _root = nullptr;
};