C++ 超詳細(xì)快速掌握二叉搜索樹
更新時(shí)間：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ǎng)h除的結(jié)點(diǎn)可能分下面四種情況：
- 要?jiǎng)h除的結(jié)點(diǎn)無孩子結(jié)點(diǎn)
- 要?jiǎng)h除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)
- 要?jiǎng)h除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)
- 要?jiǎng)h除的結(jié)點(diǎn)只有左、右結(jié)點(diǎn)
實(shí)際情況中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)
- 替代法。在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)（關(guān)鍵碼最?。盟闹堤钛a(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)鍵碼即為需要搜索到的值。比如：給一個(gè)單詞word，判斷該單詞是否拼寫正確。具體方法如下：1.以單詞集合中的每個(gè)單詞作為key，構(gòu)建一棵二叉搜索樹。2.在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯(cuò)誤。
2.KV模型：每一個(gè)關(guān)鍵碼key，都有與之對應(yīng)的值Value，即<Key, Value>的鍵值對。該種方式在現(xiàn)實(shí)生活中非常常見：比如英漢詞典就是英語與中文的對應(yīng)關(guān)系，通過英文可以快速找到與其對應(yīng)的中文，英文單詞與其對應(yīng)的中文<word, chinese>就構(gòu)成一種鍵值對；再比如統(tǒng)計(jì)單詞次數(shù)，統(tǒng)計(jì)成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出現(xiàn)次數(shù)就是<word, count>就構(gòu)成一種鍵值對。
比如：實(shí)現(xiàn)一個(gè)簡單的英漢詞典dict，可以通過英文找到與其對應(yīng)的中文，具體實(shí)現(xiàn)方式如下：1.<單詞，中文含義>為鍵值對構(gòu)造二叉搜索樹，注意：二叉搜索樹需要比較，鍵值對比較時(shí)只比較Key。2.查詢英文單詞時(shí)，只需要給出英文單詞，就可快速找到與其對應(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 << "拼寫錯(cuò)誤，請檢查你的單詞" << endl;
}
else
{
cout << ret->_key <<"->"<< ret->_value << endl;
}
}
}
}
void Test3()
{
//統(tǒng)計(jì)字符串出現(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();
}
二叉樹的性能分析
插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個(gè)操作的性能。
對有n個(gè)結(jié)點(diǎn)的二叉搜索樹，若每個(gè)元素查找的概率相等，則二叉搜索樹平均查找長度是結(jié)點(diǎn)在二叉搜索樹的深度的函數(shù)，即結(jié)點(diǎn)越深，比較的次數(shù)越多。
但對于同一個(gè)關(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)文章
類模版std::function是一種通用的多態(tài)函數(shù)包裝器std::function的實(shí)例可以對任何可以調(diào)用的目標(biāo)實(shí)體進(jìn)行存儲、復(fù)制、和調(diào)用操作，本文詳細(xì)的介紹一下，感興趣的可以了解一下2021-06-06
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)通訊錄管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-12-12
這篇文章主要介紹了codeblocks安裝及使用教程詳解，本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-01-01
C++設(shè)置超時(shí)時(shí)間的簡單實(shí)現(xiàn)方法
這篇文章主要介紹了C++設(shè)置超時(shí)時(shí)間的簡單實(shí)現(xiàn)方法,涉及系統(tǒng)函數(shù)setsockopt對套接口的操作,具有一定的實(shí)用價(jià)值,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了c語言5個(gè)常用的排序算法實(shí)例代碼，分享了相關(guān)代碼示例，小編覺得還是挺不錯(cuò)的，具有一定借鑒價(jià)值，需要的朋友可以參考下2018-02-02
這篇文章主要為大家介紹了C語言 map函數(shù)的基礎(chǔ)用法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
給定N個(gè)權(quán)值作為N個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman?Tree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點(diǎn)離根較近2022-04-04
C++類模板實(shí)戰(zhàn)之vector容器的實(shí)現(xiàn)
本文我們將做一個(gè)類模板實(shí)戰(zhàn)-手寫精簡版vector容器。讓我們自己封裝一個(gè)數(shù)組類，可以適應(yīng)基本數(shù)據(jù)類型和自定義數(shù)據(jù)類型，感興趣的可以了解一下2022-07-07
Qt項(xiàng)目實(shí)戰(zhàn)之方塊游戲的實(shí)現(xiàn)
這篇文章主要為大家詳細(xì)介紹了如何利用Qt實(shí)現(xiàn)簡易的方塊游戲，文中的示例代碼講解詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴可以了解一下2023-03-03
從匯編看c++函數(shù)的默認(rèn)參數(shù)的使用說明
本篇文章介紹了，在c++中函數(shù)的默認(rèn)參數(shù)的使用說明分析。需要的朋友參考下2013-05-05