【C++進階】---- 二叉搜索樹

1.二叉搜索樹的概念

?叉搜索樹?稱?叉排序樹，它或者是?棵空樹，或者是具有以下性質的?叉樹:
? 若它的左?樹不為空，則左?樹上所有結點的值都?于等于根結點的值
? 若它的右?樹不為空，則右?樹上所有結點的值都?于等于根結點的值
? 它的左右?樹也分別為?叉搜索樹
? ?叉搜索樹中可以?持插?相等的值，也可以不?持插?相等的值，具體看使?場景定義，后續我們學習map/set/multimap/multiset系列容器底層就是?叉搜索樹，其中map/set不?持插?相等值，multimap/multiset?持插?相等值

下圖中，左側的是二叉搜索樹，右側的不是二叉搜索樹。
在這里插入圖片描述

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

最優情況下，?叉搜索樹為完全?叉樹(或者接近完全?叉樹)，其?度為：log2 N
最差情況下，?叉搜索樹退化為單?樹(或者類似單?)，其?度為：N
在這里插入圖片描述

所以綜合???叉搜索樹增刪查改時間復雜度為：O(N)
那么這樣的效率顯然是?法滿?我們需求的，我們后續課程需要繼續講解?叉搜索樹的變形，平衡?叉搜索樹AVL樹和紅?樹，才能適?于我們在內存中存儲和搜索數據。另外需要說明的是，?分查找也可以實現O(log2 N) 級別的查找效率，但是?分查找有兩?缺陷：

需要存儲在?持下標隨機訪問的結構中，并且有序。
插?和刪除數據效率很低，因為存儲在下標隨機訪問的結構中，插?和刪除數據?般需要挪動數據。這?也就體現出了平衡?叉搜索樹的價值。

3.二叉搜索樹的實現

3.1節點和框架

// 結構
template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;// 默認構造BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};template<class K>
class BSTree
{// typedef BSTNode<K> Node;using Node = BSTNode<K>;
private:Node* _root = nullptr;
};

3.2二叉搜索樹的插入

插?的具體過程如下：

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

注意：需提前保存父節點，這樣找到插入點后，能夠正確的將新節點連接到樹中。

	// 不允許插入相同的數字bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;// 新節點需要插入到空位置while (cur != nullptr){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else return false;}// 找到插入位置了cur = new Node(key);if (key < parent->_key) parent->_left = cur;else parent->_right = cur;return true;}

3.3二叉搜索樹的查找

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

// 不支持插入相同的二叉搜索樹
bool Find(const K& key)
{Node* cur = _root;while (cur != nullptr){if (cur->_key == key) return true;else if (cur->_key > key) cur = cur->_left;else cur = cur->_right;}return false;
}

3.4二叉搜索樹的刪除

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

要刪除結點N左右孩?均為空
要刪除的結點N左孩?位空，右孩?結點不為空
要刪除的結點N右孩?位空，左孩?結點不為空
要刪除的結點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，可以直接刪除。

上述四種情況可以歸類成兩種

刪除節點只有至多一個孩子（沒有孩子或者只有一個孩子）
刪除節點有兩個孩子

下圖這種情況就是至多有一個孩子的，我們第一步需要改變要刪除的節點的父節點的指向，然后刪除該節點，如果要刪除的節點有孩子，其父節點指向其孩子，如果要刪除的節點沒有孩子，其父節點指向空。
（需要特殊考慮刪除的是否是根節點）
在這里插入圖片描述
下圖這種情況就是有兩個孩子的情況，我們需要先找到替代節點，此節點可以是左子樹的最右節點，也可以是右子樹的最左節點，下圖是以找右子樹的最左節點作為替代節點為例。
我們找到替代節點后，需要先將要刪除的節點的key值變為替代節點的key值，第二步我們需要改變替代節點的父節點的指向，因為替代節點可能存在孩子，我們需要將其父節點與其子節點之間進行連接。最后我們釋放掉替代節點。
（同樣需要特殊注意要刪除的節點是否是父節點）
在這里插入圖片描述

bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur != nullptr){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;}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;}// 有兩個孩子,需要挑選左子樹的最右節點/右子樹的最左節點充當該節點else{// 找右子樹的最左節點Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left != nullptr){replaceParent = replace;replace = replace->_left;}// 交換刪除節點和替代節點的值cur->_key = replace->_key;//需要考慮這個最左節點有沒有右孩子,同時也需要改變其父節點的指向if(replaceParent->_right==replace)// 右子樹沒有左孩子的情況replaceParent->_right = replace->_right;else replaceParent->_left = replace->_right; // 刪除替換節點即可delete replace;}return true;}}// 數據不存在return false;
}

3.4二叉搜索樹的中序遍歷

因為遍歷二叉搜索樹需要根節點，而根節點_root是類里的私有成員變量，所以我們可以寫一個富輔助函數。
Inorder()是共有的接口函數，用于對外提供中序遍歷的功能
_Inorder()是私有的輔助函數，負責實際的遞歸遍歷邏輯

	void Inorder(){// 因為遍歷需要頭節點，但_root是私有的,在外面不能直接調用_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;

3.5二叉搜索樹的拷貝構造

因為拷貝構造需要用到根節點_root，又因為_root是私有成員變量，所以我們可以寫一個輔助函數來完成拷貝構造
Copy()是私有輔助函數，用于完成二叉搜索樹的拷貝
BSTree(const BSTree& t)是共有的接口函數，用于對外提供拷貝功能
(如果不寫拷貝構造函數的話，默認是淺拷貝，即兩個指針指向同一塊地址)
(因為寫了拷貝構造，不會生成默認構造函數，會導致創建對象的時候沒有合適的默認構造可以使用，C++11支持強制生成)
默認函數=default即可強制生成想要的默認函數

	// 因為寫了拷貝構造，不會生成默認構造函數，C++11支持強制生成BSTree() = default;// 強制生成默認構造BSTree(const BSTree& t){_root = Copy(t._root);}
private:Node* Copy(Node* root){if (root == nullptr) return nullptr;// Node* newRoot = root;的話是淺拷貝Node* newRoot = new Node(root->_key);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}

3.5二叉搜索樹的復制運算符重載

這邊我們的形參用的是臨時對象，對形參的改變不會影響實參，所以我們可以直接將根節點進行交換，原本的_root給給了tmp，出了這個函數后tmp也會自動銷毀

	BSTree& operator=(BSTree tmp){swap(_root, tmp._root);return *this;}

3.6二叉搜索樹的析構

因為析構需要用到根節點，所以我們使用輔助函數來完成析構。
析構我們采用的是先序后序遍歷，先析構左右孩子在析構根節點，保證所有節點都得到析構。

	~BSTree(){Destory(_root);_root = nullptr;}
private:void Destory(Node* root){if (root == nullptr) return;Destory(root->_left);Destory(root->_right);delete root;}

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

4.1key搜索場景

只有key作為關鍵碼，結構中只需要存儲key即可，關鍵碼即為需要搜索到的值，搜索場景只需要判斷key在不在。key的搜索場景實現的?叉樹搜索樹?持增刪查，但是不?持修改，修改key破壞搜索樹結構了。
場景1：?區??值守?庫，?區?庫買了?位的業主?才能進?區，那么物業會把買了?位的業主的?牌號錄?后臺系統，?輛進?時掃描?牌在不在系統中，在則抬桿，不在則提??本?區?輛，?法進?。
場景2：檢查?篇英? 章單詞拼寫是否正確，將詞庫中所有單詞放??叉搜索樹，讀取?章中的單詞，查找是否在?叉搜索樹中，不在則波浪線標紅提?。
（上述第三點講的就是key二叉搜索樹的實現）

4.2key_value搜索場景

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

namespace key_value
{// 結構template<class K,class V>struct BSTNode{K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;// 默認構造BSTNode(const K& key,const V& value):_key(key), _value(value), _left(nullptr), _right(nullptr){}};template<class K,class V>class BSTree{// typedef BSTNode<K> Node;using Node = BSTNode<K,V>;public:// 因為寫了拷貝構造，不會生成默認構造函數，C++11支持強制生成BSTree() = default;// 強制生成默認構造BSTree(const BSTree& t){_root = Copy(t._root);}BSTree& operator=(BSTree tmp){swap(_root, tmp._root);return *this;}~BSTree(){Destory(_root);_root = nullptr;}// 不允許插入相同的數字bool Insert(const K& key,const V& value){if (_root == nullptr){_root = new Node(key,value);return true;}Node* cur = _root;Node* parent = nullptr;// 新節點需要插入到空位置while (cur != nullptr){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else return false;}// 找到插入位置了cur = new Node(key,value);if (key < parent->_key) parent->_left = cur;else parent->_right = cur;return true;}Node* Find(const K& key){Node* cur = _root;while (cur != nullptr){if (cur->_key == key) return cur;else if (cur->_key > key) cur = cur->_left;else cur = cur->_right;}return nullptr;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur != nullptr){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;}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;}// 有兩個孩子,需要挑選左子樹的最右節點/右子樹的最左節點充當該節點else{// 找右子樹的最左節點Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left != nullptr){replaceParent = replace;replace = replace->_left;}// 交換刪除節點和替代節點的值cur->_key = replace->_key;//需要考慮這個最左節點有沒有右孩子,同時也需要改變其父節點的指向if (replaceParent->_right == replace)// 右子樹沒有左孩子的情況replaceParent->_right = replace->_right;elsereplaceParent->_left = replace->_right;// 刪除替換節點即可delete replace;}return true;}}// 數據不存在return false;}// 中序遍歷二叉搜索樹void Inorder(){// 因為遍歷需要頭節點，但_root是私有的,在外面不能直接調用_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);}Node* Copy(Node* root){if (root == nullptr) return nullptr;Node* newRoot = new Node(root->_key,root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}void Destory(Node* root){if (root == nullptr) return;Destory(root->_left);Destory(root->_right);delete root;}Node* _root = nullptr;};
}