【C++】第十七節—二叉搜索樹(概念+性能分析+增刪查+實現+使用場景)

好久不見，我是云邊有個稻草人

《C++》本文所屬專欄—持續更新中—歡迎訂閱

一、二叉搜索樹的概念

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

三、二叉搜索樹的插入

SearchBinaryTree.h

test.cpp

四、?叉搜索樹的查找

【只有一個3】

【有多個3】?

五、?叉搜索樹的刪除

六、二叉搜索樹的實現代碼

SearchBinaryTree.h

test.cpp?

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

7.1 key搜索場景

7.2 key/value搜索場景

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

.cpp

正文開始——

一、二叉搜索樹的概念

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

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

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

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

最差情況下，?叉搜索樹退化為單?樹(或者類似單?)，其高度為： N

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

那么這樣的效率顯然是?法滿?我們需求的，我們后續需要繼續講解?叉搜索樹的變形，平衡?叉搜索樹AVL樹和紅?樹，才能適?于我們在內存中存儲和搜索數據。

另外需要說明的是，?分查找也可以實現 O(log2 N) 級別的查找效率，但是?分查找有兩?缺陷：

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

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

三、二叉搜索樹的插入

插?的具體過程如下：

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

SearchBinaryTree.h

#pragma once
#include<iostream>
using namespace std;template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
};//class SearchBinaryTree
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;}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;
};

test.cpp

#include"SearchBinaryTree.h"
#include<vector>int main()
{vector<int> a = { 0, 3, 1, 10, 1, 6, 4, 7, 14, 13 };BSTree<int> t;for (auto e : a){t.Insert(e);}t.InOrder();return 0;
}

四、?叉搜索樹的查找

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

【只有一個3】

bool Find(const K& key)
{Node* cur = _root;while (cur){if (key > cur->_key){cur = cur->_right;}else if (key < cur->_key){cur = cur->_left;}else{return true;}}return false;
}

【有多個3】?

查找3，要求查找中序的第一個3。具體后面會講

五、?叉搜索樹的刪除

?先查找元素是否在?叉搜索樹中，如果不存在，則返回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，可以直接刪除。

下面代碼的實現思路：分為3種情況（將上面的情況1歸為情況2或者是情況3），分為情況2，情況3，情況4來進行刪除結點

bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{//找到了，刪除結點//情況2if (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;}//情況3else 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;}//情況4else{// 找右子樹最小節點(最左)替代我的位置Node* minRightParent = cur;Node* minRight = cur->_right;while (minRight->_left){minRightParent = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (minRightParent->_left == minRight){minRightParent->_left = minRight->_right;}else{minRightParent->_right = minRight->_right;}delete minRight;}return true;}}return false;
}

六、二叉搜索樹的實現代碼

SearchBinaryTree.h

#pragma once
#include<iostream>
using namespace std;template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
};//class SearchBinaryTree
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 (key > cur->_key){cur = cur->_right;}else if (key < cur->_key){cur = cur->_left;}else{return true;}}return false;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{//找到了，刪除結點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;}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;}else{// 找右子樹最小節點(最左)替代我的位置Node* minRightParent = cur;Node* minRight = cur->_right;while (minRight->_left){minRightParent = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (minRightParent->_left == minRight){minRightParent->_left = minRight->_right;}else{minRightParent->_right = minRight->_right;}delete minRight;}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;
};

test.cpp?

#include"SearchBinaryTree.h"
#include<vector>int main()
{vector<int> a = { 0, 3, 1, 10, 1, 6, 4, 7, 14, 13 };BSTree<int> t;for (auto e : a){t.Insert(e);}t.InOrder();//if (t.Find(300))//{//	cout << "找到了" << endl;//}//else//{//	cout << "沒找到" << endl;//}t.Erase(8);t.InOrder();t.Erase(14);t.InOrder();t.Erase(1);t.InOrder();for (auto e : a){t.Erase(e);t.InOrder();}return 0;
}

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

7.1 key搜索場景

只有key作為關鍵碼，結構中只需要存儲key即可，關鍵碼即為需要搜索到的值，搜索場景只需要判斷key在不在。key的搜索場景實現的?叉樹搜索樹?持增刪查，但是不?持修改，修改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），單詞存在，則++單詞對應的次數。

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

.h

	template<class K, class V>class BSTree{typedef BSTNode<K, V> Node;public:bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);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, value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}Node* 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 cur;}}return nullptr;}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{//刪除if (cur->_left == nullptr){//if (parent == nullptr)if (cur == _root){_root = cur->_right;}else{// 父親指向我的右if (cur == parent->_right){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete 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;}else{// 找右子樹最小節點(最左)替代我的位置Node* minRightParent = cur;Node* minRight = cur->_right;while (minRight->_left){minRightParent = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (minRightParent->_left == minRight){minRightParent->_left = minRight->_right;}else{minRightParent->_right = minRight->_right;}delete minRight;}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 << " " << root->_value << endl;_InOrder(root->_right);}Node* _root = nullptr;};
}

.cpp

int main()
{string arr[] = { "蘋果","香蕉","香蕉","西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜",
"蘋果", "香蕉", "蘋果", "香蕉","香蕉","香蕉" };key_value::BSTree<string, int> countTree;for (auto& e : arr){//key_value::BSTNode<string, int>* ret = countTree.Find(e);auto ret = countTree.Find(e);if (ret == nullptr){countTree.Insert(e, 1);}else{ret->_value++;}}countTree.InOrder();return 0;
}

完——

冬眠_司南