前言
作者：小蝸牛向前沖
?如果覺的博主的文章還不錯(cuò)的話，還請(qǐng)
點(diǎn)贊，收藏，關(guān)注??支持博主。如果發(fā)現(xiàn)有問題的地方歡迎?大家在評(píng)論區(qū)指正。
目錄
一、二叉搜索樹的基本知識(shí)
1、什么是二叉搜索樹
2、二叉搜索樹的性能分析?
二、底層模擬實(shí)現(xiàn)
1、構(gòu)建二叉搜索樹
2、二叉搜索樹的查找
3、二叉搜索樹的插入
4、二叉搜索樹的刪除節(jié)點(diǎn)
?5、完整代碼實(shí)現(xiàn)
三、二叉搜索樹的應(yīng)用
1、K模型
2、KV模型
?本期學(xué)習(xí)目標(biāo)：清楚什么是二叉搜索樹，模擬實(shí)現(xiàn)二叉搜索樹，理解二叉搜索樹的K模型和KV模型。
一、二叉搜索樹的基本知識(shí)
1、什么是二叉搜索樹
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹:
- 若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
- 若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
- 它的左右子樹也分別為二叉搜索樹
二叉搜索樹的這種特性使得在其中進(jìn)行搜索、插入和刪除操作具有高效性能。通過對(duì)節(jié)點(diǎn)值的比較，我們可以迅速定位目標(biāo)節(jié)點(diǎn)或確定應(yīng)插入的位置。
![[數(shù)據(jù)結(jié)構(gòu)]-二叉搜索樹,數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),c++,1024程序員節(jié)](https://imgs.yssmx.com/Uploads/2023/10/718431-4.png)
上圖中就是二叉搜索樹的構(gòu)成，他滿足所有左葉子節(jié)點(diǎn)比跟小，所以的右葉子節(jié)點(diǎn)比根要大。
為了更好的理解二叉搜索樹，下面將帶來大家底層實(shí)現(xiàn)二叉搜索樹的查找，插入，刪除。
2、二叉搜索樹的性能分析?
對(duì)有n個(gè)結(jié)點(diǎn)的二叉搜索樹，若每個(gè)元素查找的概率相等，則二叉搜索樹平均查找長度是結(jié)點(diǎn)在二 叉搜索樹的深度的函數(shù)，即結(jié)點(diǎn)越深，則比較次數(shù)越多
但對(duì)于同一個(gè)關(guān)鍵碼集合，如果各關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹：
![[數(shù)據(jù)結(jié)構(gòu)]-二叉搜索樹,數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),c++,1024程序員節(jié)](https://imgs.yssmx.com/Uploads/2023/10/718431-5.png)
- ?最優(yōu)情況下，二叉搜索樹為完全二叉樹(或者接近完全二叉樹)，其平均比較次數(shù)為：O(log n)
- 最差情況下，二叉搜索樹退化為單支樹(或者類似單支)，其平均比較次數(shù)為O(n)
二、底層模擬實(shí)現(xiàn)
1、構(gòu)建二叉搜索樹
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public://函數(shù)
private:
Node* _root = nullptr;
}這里我們定義好節(jié)點(diǎn)，和樹的主體就好了，下面我的二叉搜索樹的功能函數(shù)多在類中實(shí)現(xiàn)。
2、二叉搜索樹的查找
現(xiàn)在給我們一顆搜索二叉樹，那我們是如何讓他查找到我們想要的元素
查找原則：
- 從根開始比較，查找，比根大則往右邊走查找，比根小則往左邊走查找。
- 最多查找高度次，走到到空，還沒找到，這個(gè)值不存在。
順著這個(gè)思路我們很容易思路就可以寫出查找：?
普通寫法：
//查找
bool 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 true;
}
}
return false;
}遞歸寫法：
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
return _FindR(root->_right, key);
}
else if (root->_key > key)
{
return _FindR(root->_left, key);
}
else
{
return true;
}
}這二種寫法，在這里好像看不出來特別大的差別。
3、二叉搜索樹的插入
這里我們思考一下，如果我們要在1處插入?0
![[數(shù)據(jù)結(jié)構(gòu)]-二叉搜索樹,數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),c++,1024程序員節(jié)](https://imgs.yssmx.com/Uploads/2023/10/718431-8.png)
我們要找到插入的位置。然后在new一個(gè)節(jié)點(diǎn)進(jìn)連接就可以
插入的具體過程如下：
a. 樹為空，則直接新增節(jié)點(diǎn)，賦值給root指針
b. 樹不空，按二叉搜索樹性質(zhì)查找插入位置，插入新節(jié)點(diǎn)
普通寫法：?
bool Inert(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->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
//創(chuàng)建節(jié)點(diǎn)
cur = new Node(key);
//連接樹
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}遞歸寫法：
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
{
return _InsertR(root->_right, key);
}
else if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}遞歸寫法最讓我們感到絕妙的是我們?cè)谶@里傳root用的是引用，因?yàn)橛眠f歸時(shí)(如果沒有用root的引用)并沒有傳父親節(jié)點(diǎn)，這也就在連接的時(shí)候會(huì)遇到到問題，但是我們這里傳了root的引用就可以解決這個(gè)問題
這里當(dāng)我們要插入9，到我們遞歸到root == 10時(shí)候,在進(jìn)行遞歸時(shí)，會(huì)往root->left遞歸，指向空,就可以插入，而&root是root->left指針的別名，就可以完美的連接起來。![[數(shù)據(jù)結(jié)構(gòu)]-二叉搜索樹,數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),c++,1024程序員節(jié)](https://imgs.yssmx.com/Uploads/2023/10/718431-9.png)
4、二叉搜索樹的刪除節(jié)點(diǎn)
這里是本次模擬的難點(diǎn)所在，大家可以細(xì)細(xì)品味：
首先查找元素是否在二叉搜索樹中，如果不存在，則返回, 否則要?jiǎng)h除的結(jié)點(diǎn)可能分下面四種情 況：
- a. 要?jiǎng)h除的結(jié)點(diǎn)無孩子結(jié)點(diǎn)
- b. 要?jiǎng)h除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)
- c. 要?jiǎng)h除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)
- d. 要?jiǎng)h除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)
其實(shí)我們可以總結(jié)為3種刪除情況：
![[數(shù)據(jù)結(jié)構(gòu)]-二叉搜索樹,數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),c++,1024程序員節(jié)](https://imgs.yssmx.com/Uploads/2023/10/718431-10.png)
- 情況1：刪除該結(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除節(jié)點(diǎn)的左孩子結(jié)點(diǎn)--直接刪除
- 情況2：刪除該結(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的右孩子結(jié)點(diǎn)--直接刪除
- 情況3：在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小)，用它的值填補(bǔ)到被刪除節(jié)點(diǎn) 中，再來處理該結(jié)點(diǎn)的刪除問題--替換法刪除
普通寫法：
這里我們重點(diǎn)注意第三種情況，這里我們是找左樹的最大或者說是右樹的最小和我們要?jiǎng)h除的數(shù)，進(jìn)行替換在刪除就可以了。
//刪除
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
//先找到要?jiǎng)h除的數(shù)
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
//1、左為空
//2、右為空
// 1.2都可以直接刪除
//在直接刪除前，我們還要做好cur的左右節(jié)點(diǎn)的鏈接工作，并處理特殊情況(cur==_root)
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;
}遞歸寫法：
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
//先找到要?jiǎng)h除的位置
if (root->_key < key)
{
return _EraseR(root->_right, key);
}
else if (root->_key > key)
{
return _EraseR(root->_left, key);
}
else
{
Node* del = root;
if (root->_right == nullptr)
{
root = root->_left;
}
else if (root->_left == nullptr)
{
root = root->_right;
}
else
{
Node* minRight = root->_right;
while (minRight->_left)
{
minRight = minRight->_left;
}
swap(root->_key, minRight->_key);
//轉(zhuǎn)換為在子樹中刪除節(jié)點(diǎn)
return _EraseR(root->_right, key);
}
delete del;
return true;
}
}?5、完整代碼實(shí)現(xiàn)
namespace K
{
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
//默認(rèn)構(gòu)造
BSTree()
:_root(nullptr)
{}
//構(gòu)造函數(shù)
BSTree(const BSTree<K>& t)
{
_root = Copy(t._root);
}
//賦值重載
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
//析構(gòu)函數(shù)
~BSTree()
{
Destroy(_root);
_root = nullptr;
}
//搜索二插樹插入
bool Inert(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->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
//創(chuàng)建節(jié)點(diǎn)
cur = new Node(key);
//連接樹
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
//查找
bool 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 true;
}
}
return false;
}
//刪除
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
//先找到要?jiǎng)h除的數(shù)
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
//1、左為空
//2、右為空
// 1.2都可以直接刪除
//在直接刪除前，我們還要做好cur的左右節(jié)點(diǎn)的鏈接工作，并處理特殊情況(cur==_root)
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;
}
//3、左右都不為空
//找cur右子數(shù)的最小節(jié)點(diǎn)
else
{
Node* parent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
parent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
//連接
if (parent->_left == minRight)
{
parent->_left = minRight->_right;
}
else
{
parent->_right = minRight->_right;
}
//刪除節(jié)點(diǎn)
delete minRight;
}
return true;
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
bool FindR(const K& key)
{
return _FindR(_root, key);
}
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
//遞歸寫法完成增刪查改
private:
void Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
//拷貝節(jié)點(diǎn)
Node* Copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* newRoot = new Node(root->_key);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
{
return _InsertR(root->_right, key);
}
else if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
return _FindR(root->_right, key);
}
else if (root->_key > key)
{
return _FindR(root->_left, key);
}
else
{
return true;
}
}
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
//先找到要?jiǎng)h除的位置
if (root->_key < key)
{
return _EraseR(root->_right, key);
}
else if (root->_key > key)
{
return _EraseR(root->_left, key);
}
else
{
Node* del = root;
if (root->_right == nullptr)
{
root = root->_left;
}
else if (root->_left == nullptr)
{
root = root->_right;
}
else
{
Node* minRight = root->_right;
while (minRight->_left)
{
minRight = minRight->_left;
}
swap(root->_key, minRight->_key);
//轉(zhuǎn)換為在子樹中刪除節(jié)點(diǎn)
return _EraseR(root->_right, key);
}
delete del;
return true;
}
}
private:
Node* _root = nullptr;
};
}三、二叉搜索樹的應(yīng)用
1、K模型
K模型：K模型即只有key作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲(chǔ)Key即可，關(guān)鍵碼即為需要搜索到 的值。 比如：給一個(gè)單詞word，判斷該單詞是否拼寫正確，具體方式如下： 以詞庫中所有單詞集合中的每個(gè)單詞作為key，構(gòu)建一棵二叉搜索樹 在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯(cuò)誤。
這里就是我們完整實(shí)現(xiàn)的二叉樹，這里我們用二叉搜索樹的查找功能，如果該單詞存在樹中就會(huì)返回true，否則返回false。
2、KV模型
KV模型：每一個(gè)關(guān)鍵碼key，都有與之對(duì)應(yīng)的值Value，即的鍵值對(duì)。該種方 式在現(xiàn)實(shí)生活中非常常見：
- 比如英漢詞典就是英文與中文的對(duì)應(yīng)關(guān)系，通過英文可以快速找到與其對(duì)應(yīng)的中文，英 文單詞與其對(duì)應(yīng)的中文就構(gòu)成一種鍵值對(duì)；
- 再比如統(tǒng)計(jì)單詞次數(shù)，統(tǒng)計(jì)成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出 現(xiàn)次數(shù)就是就構(gòu)成一種鍵值對(duì)。
這里我們上面代碼進(jìn)行簡單改造就可以得到我們的KV模型：
namespace KV
{
template<class K, class V>
struct BSTreeNode
{
BSTreeNode<K, V>* _left;
BSTreeNode<K, V>* _right;
K _key;
V _value;
BSTreeNode(const K& key, const V& value)
:_key(key)
, _value(value)
, _left(nullptr)
, _right(nullptr)
{}
};
//BSTree<string, vector<string>> bookInfo;
template<class K, class V>
class BSTree
{
typedef BSTreeNode<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;
}
void Inorder()
{
_Inorder(_root);
}
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_Inorder(root->_right);
}
private:
Node* _root = nullptr;
};
}
void TestBSTree2()
{
// Key/Value的搜索模型,通過Key查找或修改Valu
KV::BSTree<string, string> dict;
dict.Insert("sort", "排序");
dict.Insert("string", "字符串");
dict.Insert("left", "左邊");
dict.Insert("right", "右邊");
string str;
while (cin >> str)
{
KV::BSTreeNode<string, string>* ret = dict.Find(str);
if (ret)
{
cout << ret->_value << endl;
}
else
{
cout << "無此單詞" << endl;
}
}
}![[數(shù)據(jù)結(jié)構(gòu)]-二叉搜索樹,數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),c++,1024程序員節(jié)](https://imgs.yssmx.com/Uploads/2023/10/718431-11.png)
文章來源：http://www.zghlxwxcb.cn/news/detail-718431.html
這里我們對(duì)改造的二叉搜索樹，就可以進(jìn)行通過英文快速找到英文。文章來源地址http://www.zghlxwxcb.cn/news/detail-718431.html
到了這里，關(guān)于[數(shù)據(jù)結(jié)構(gòu)]-二叉搜索樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu)]-二叉搜索樹](https://imgs.yssmx.com/Uploads/2024/02/718431-1.png)
