C++ 超詳細(xì)快速掌握二叉搜索樹
更新時間：2022年03月24日 14:41:37 作者：ymz123_
從這篇博客開始，我就要和大家介紹有關(guān)二叉搜索樹的知識，它還衍生出了兩棵樹——AVL樹和紅黑樹，在后面兩篇博客我都會介紹。今天先從二叉搜索樹開始引入
二叉搜索樹概念與操作
二叉搜索樹的概念
二叉搜索樹又稱二叉排序樹，若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值；若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值，它的左右子樹也分別未二叉搜索樹。也可以是一顆空樹。
int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
二叉搜索樹的操作
查找
迭代：
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;
}
遞歸：
Node* _FindR(Node* root, const K& key)
{
if (root == nullptr)
return nullptr;
if (root->_key < key)
return _FindR(root->_right, key);
else if (root->_key > key)
return _FindR(root->_left, key);
else
return root;
}
插入
樹為空，則直接插入
樹不為空，按二叉搜索樹性質(zhì)查找插入位置，插入新節(jié)點(diǎn)
迭代：
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 < cur->_key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
遞歸：
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
else
{
if (root->_key < key)
{
return _InsertR(root->_left, key);
}
else if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
}
刪除
首先查找元素是否在二叉搜索樹中，如果不存在，則返回，否則要刪除的結(jié)點(diǎn)可能分下面四種情況：
- 要刪除的結(jié)點(diǎn)無孩子結(jié)點(diǎn)
- 要刪除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)
- 要刪除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)
- 要刪除的結(jié)點(diǎn)只有左、右結(jié)點(diǎn)
實際情況中1和2或3可以合并，因此真正的刪除過程如下：
- 刪除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的左孩子結(jié)點(diǎn)
- 刪除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的右孩子結(jié)點(diǎn)
- 替代法。在它的右子樹中尋找中序下的第一個結(jié)點(diǎn)（關(guān)鍵碼最?。?，用它的值填補(bǔ)到被刪除結(jié)點(diǎn)中，再來處理該結(jié)點(diǎn)的刪除問題。
迭代：
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 (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
}
else
{
//找到右樹最小節(jié)點(diǎn)去替代刪除
Node* minRightParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
minRightParent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (minRight == minRightParent->_left)
minRightParent->_left = minRight->_right;
else
minRightParent->_right = minRight->_right;
delete minRight;
}
return true;
}
}
return false;
}
遞歸：
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
return false;
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->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
//替代法刪除
Node* minRight = root->_right;
while (minRight->_left)
{
minRight = minRight->_left;
}
root->_key = minRight->_key;
//轉(zhuǎn)換成遞歸在右子樹中刪除最小節(jié)點(diǎn)
return _EraseR(root->_right, minRight->_key);
}
delete del;
return true;
}
}
二叉搜索樹的應(yīng)用
1.K模型：K模型即只有key作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲key即可，關(guān)鍵碼即為需要搜索到的值。比如：給一個單詞word，判斷該單詞是否拼寫正確。具體方法如下：1.以單詞集合中的每個單詞作為key，構(gòu)建一棵二叉搜索樹。2.在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯誤。
2.KV模型：每一個關(guān)鍵碼key，都有與之對應(yīng)的值Value，即<Key, Value>的鍵值對。該種方式在現(xiàn)實生活中非常常見：比如英漢詞典就是英語與中文的對應(yīng)關(guān)系，通過英文可以快速找到與其對應(yīng)的中文，英文單詞與其對應(yīng)的中文<word, chinese>就構(gòu)成一種鍵值對；再比如統(tǒng)計單詞次數(shù)，統(tǒng)計成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出現(xiàn)次數(shù)就是<word, count>就構(gòu)成一種鍵值對。
比如：實現(xiàn)一個簡單的英漢詞典dict，可以通過英文找到與其對應(yīng)的中文，具體實現(xiàn)方式如下：1.<單詞，中文含義>為鍵值對構(gòu)造二叉搜索樹，注意：二叉搜索樹需要比較，鍵值對比較時只比較Key。2.查詢英文單詞時，只需要給出英文單詞，就可快速找到與其對應(yīng)的Key。
namespace KEY_VALUE {
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)
:_left(nullptr)
,_right(nullptr)
,_key(key)
,_value(value)
{}
};
template<class K, class V>
class BSTree {
typedef BSTreeNode<K, V> Node;
public:
V& operator[](const K& key)
{
pair<Node*, bool> ret = Insert(key, V());
return ret.first->_value;
}
pair<Node*, bool> Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
return make_pair(_root, 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 make_pair(cur, false);
}
}
cur = new Node(key, value);
if (parent->_key < cur->_key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return make_pair(cur, 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* cur = _root;
Node* parent = nullptr;
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 (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else
{
//找到右樹最小結(jié)點(diǎn)去替代刪除
Node* minRightParent = cur;
Node* minRight = cur->_left;
while (minRight->_left)
{
minRightParent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (minRight = minRightParent->_left)
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);
}
private:
Node* _root = nullptr;
};
}
void Test2()
{
KEY_VALUE::BSTree<string, string> dict;
dict.Insert("sort", "排序");
dict.Insert("insert", "插入");
dict.Insert("tree", "樹");
dict.Insert("right", "右邊");
string str;
while (cin >> str)
{
if (str == "q")
{
break;
}
else
{
auto ret = dict.Find(str);
if (ret == nullptr)
{
cout << "拼寫錯誤，請檢查你的單詞" << endl;
}
else
{
cout << ret->_key <<"->"<< ret->_value << endl;
}
}
}
}
void Test3()
{
//統(tǒng)計字符串出現(xiàn)次數(shù)，也是經(jīng)典key/value
string str[] = { "sort", "sort", "tree", "insert", "sort", "tree", "sort", "test", "sort" };
KEY_VALUE::BSTree<string, int> countTree;
//for (auto& e : str)
//{
// auto ret = countTree.Find(e);
// if (ret == nullptr)
// {
// countTree.Insert(e, 1);
// }
// else
// {
// ret->_value++;
// }
//}
for (auto& e : str)
{
countTree[e]++;
}
countTree.InOrder();
}
二叉樹的性能分析
插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個操作的性能。
對有n個結(jié)點(diǎn)的二叉搜索樹，若每個元素查找的概率相等，則二叉搜索樹平均查找長度是結(jié)點(diǎn)在二叉搜索樹的深度的函數(shù)，即結(jié)點(diǎn)越深，比較的次數(shù)越多。
但對于同一個關(guān)鍵碼集合，如果關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹
最優(yōu)情況下，二叉搜索樹為完全二叉樹，其平均比較次數(shù)為：logN
最差情況下，二叉搜索樹退化為單支樹，其平均比較次數(shù)為：N/2
到此這篇關(guān)于C++ 超詳細(xì)快速掌握二叉搜索樹 的文章就介紹到這了,更多相關(guān)C++ 二叉搜索樹 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++基于OpenCV手勢識別的實現(xiàn)源碼,這里用到背景減法模型知識，具體實例代碼跟隨小編一起看看吧2021-09-09
這篇文章主要介紹了C語言實現(xiàn)順序表的插入刪除，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-05-05
C++算法之海量數(shù)據(jù)處理方法的總結(jié)分析
本篇文章是對海量數(shù)據(jù)處理方法進(jìn)行了詳細(xì)的總結(jié)與分析，需要的朋友參考下2013-05-05
C語言中變量與其內(nèi)存地址對應(yīng)的入門知識簡單講解
這篇文章主要介紹了C語言中變量與其內(nèi)存地址對應(yīng)的入門知識簡單講解,同時這也是掌握指針部分知識的基礎(chǔ),需要的朋友可以參考下2015-12-12
Qt實現(xiàn)數(shù)據(jù)導(dǎo)出到xls的示例代碼
導(dǎo)入導(dǎo)出數(shù)據(jù)到csv由于語法簡單，適用場景有限，于是本文將為大家介紹Qt如何實現(xiàn)導(dǎo)出數(shù)據(jù)到xls，感興趣的小伙伴可以跟隨小編一起試一試2022-01-01
這篇文章主要介紹了C++ Boost.Range與Adapters庫使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-11-11
這篇文章主要為大家詳細(xì)介紹了C++基于特征向量的KNN分類算法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-12-12
解決在Mac下直接解壓C++靜態(tài)庫出現(xiàn)的問題
最近在研究C++的各種編譯構(gòu)建過程，學(xué)習(xí)了一下cmake，gyp/ninja這些自動化構(gòu)建工具后，想著自己試下用純命令行跑一遍編譯流程。在試圖把C++靜態(tài)庫編譯為動態(tài)庫的過程中遇到了棘手的問題，找了好久后發(fā)現(xiàn)是跟Mac平臺相關(guān)的，這里記錄一下，望對遇到類似問題的童鞋有幫助。2016-12-12
當(dāng)自旋鎖嘗試獲取鎖時以忙等待（busy waiting）的形式不斷地循環(huán)檢查鎖是否可用，下面這篇文章主要給大家介紹了關(guān)于利用C++11原子量如何實現(xiàn)自旋鎖的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考下2018-06-06
VS C++頭文件引用提示“未定義標(biāo)識符”的問題解決
本文主要介紹了VS C++頭文件引用提示“未定義標(biāo)識符”的問題解決，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07