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