詳解C++二叉搜索樹的原理及實(shí)現(xiàn)
一、二叉搜索樹的概念
二叉搜索樹又稱二叉排序樹，二叉搜索樹是一種二叉樹，其中每個節(jié)點(diǎn)的值大于其左子樹中的任何節(jié)點(diǎn)，并且小于其右子樹中的任何節(jié)點(diǎn)。這個特性使得二叉搜索樹具有高效的查找、插入和刪除操作。下圖即為二叉搜索樹：
二、二叉搜索樹的操作及實(shí)現(xiàn)
由于二叉搜索樹的特性，使得二叉搜索樹具有高效的查找、插入和刪除操作。在我們分析各個操作的效率和實(shí)現(xiàn)原理之前，我們先把二叉樹的大體結(jié)構(gòu)列出，代碼如下：
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree()
:_root(nullptr)
{}
private:
Node* _root;
};2.1 二叉搜索樹的插入
2.1.1 插入的原理
插入一個新的值時，我們需要遵守二叉搜索樹的特性。首先，我們從根節(jié)點(diǎn)開始找到合適的插入位置。具體操作是，將新值與當(dāng)前節(jié)點(diǎn)的值比較，若新值小于當(dāng)前節(jié)點(diǎn)的值，則往左子樹方向找到合適的葉子節(jié)點(diǎn)進(jìn)行插入；反之，若新值大于當(dāng)前節(jié)點(diǎn)的值，則往右子樹方向找到合適的葉子節(jié)點(diǎn)進(jìn)行插入。
合適的葉子節(jié)點(diǎn)指的是一直往下查找，直到該位置為空（nullptr）時，此時新值就應(yīng)該插入該位置。即使我們找到了合適的位置，如果不知道該位置的父節(jié)點(diǎn)的話，似乎并不能連接到該樹中。所以在查找合適位置的同時，還需要維護(hù)一個父節(jié)點(diǎn)。但是我們需要注意，二叉搜索樹中沒有重復(fù)的值。如果插入重復(fù)的值，那么就會插入失敗。
同時，我們再插入前，要判斷該樹是否為空。否則就會出現(xiàn)意想不到的bug。
2.1.2 插入的代碼實(shí)現(xiàn)
我們看代碼實(shí)現(xià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 < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}2.2 二叉搜索樹的查找
2.2.1 查找的原理
其實(shí)在上述的插入中，我們不就進(jìn)行了查找嗎？！為了查找一個特定的值，我們從根節(jié)點(diǎn)開始向下遍歷二叉樹，根據(jù)當(dāng)前節(jié)點(diǎn)的值與目標(biāo)值的大小關(guān)系來選擇往左子樹或者右子樹進(jìn)行遍歷。如果找到目標(biāo)值，則返回成功；否則，如果遍歷到葉子節(jié)點(diǎn)還未找到目標(biāo)值，則返回失敗。
2.2.2 查找的代碼實(shí)現(xiàn)
bool 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 true;
}
}
return false;
}2.3 二叉搜索樹的刪除
2.3.1 刪除的原理
刪除操作是相對復(fù)雜的，因?yàn)槲覀冃枰幚聿煌那闆r。具體步驟如下：
- 如果要刪除的節(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)。
對上述的情況在進(jìn)行分析和總結(jié)，一共可分為如下情況：
- 要刪除的結(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)的雙親結(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)的刪除問題--替換法刪除
為什么是上述的三種情況呢？我們詳細(xì)分析一下是為什么。
假如我們要刪除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)，我們可以把這種情況看成要刪除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)或者只有右孩子結(jié)點(diǎn)。把另一個存在的孩子看成空（nullptr）。這樣刪除后，直接可讓其父節(jié)點(diǎn)指向空（nullptr），而不是野指針。
要刪除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)或者要刪除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)是兩種不同的情況。因?yàn)樗麄兊牟僮魇遣煌摹?/p>
要刪除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)這種情況較為復(fù)雜。首先我們應(yīng)該找到能夠填充該位置的節(jié)點(diǎn)。根據(jù)二叉搜索樹的特性每個節(jié)點(diǎn)的值大于其左子樹中的任何節(jié)點(diǎn)，并且小于其右子樹中的任何節(jié)點(diǎn)，我們找到的值應(yīng)該也滿足此特點(diǎn)。有兩個節(jié)點(diǎn)的只滿足該情況：該節(jié)點(diǎn)左子樹的最大值、該節(jié)點(diǎn)右子樹的最小值。本篇文章講述的是左子樹的最大值。找左子樹的最大值，就是該子樹最右邊的節(jié)點(diǎn)。找到后交值換再刪除。
要刪除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)這種情況，在找左子樹的最大值時也應(yīng)該維護(hù)一個父節(jié)點(diǎn)。為什么呢？因?yàn)槲覀冋业阶笞訕涞淖畲笾禃r，與要刪除的節(jié)點(diǎn)的值交換后，要刪除該節(jié)點(diǎn)（交換前的左子樹最大值的節(jié)點(diǎn)）。此時該節(jié)點(diǎn)的右節(jié)點(diǎn)一定為空（nullptr），只需要關(guān)心左節(jié)點(diǎn)就行。
2.3.2 刪除的代碼實(shí)現(xià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 (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
}// 右為空
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
} // 左右都不為空
else
{
// 找替代節(jié)點(diǎn)
Node* parent = cur;
Node* leftMax = cur->_left;
while (leftMax->_right)
{
parent = leftMax;
leftMax = leftMax->_right;
}
swap(cur->_key, leftMax->_key);
if (parent->_left == leftMax)
{
parent->_left = leftMax->_left;
}
else
{
parent->_right = leftMax->_left;
}
cur = leftMax;
}
delete cur;
return true;
}
}
return false;
}2.4 二叉搜索樹的中序遍歷
二叉搜索樹又稱二叉排序樹，為什么又名二叉排序樹呢？二叉搜索樹的中序遍歷的結(jié)果就是一個有序的結(jié)果。代碼如下：
public:
Inorder()
{
_Inorder(_root);
}
private:
void _Inorder(Node* root)
{
if(root==nullptr)
{
return ;
}
_Inorder(root->left);
cout<<root->_key<<" ";
_Inorder(root->right);
} 2.5 遞歸實(shí)現(xiàn)二叉樹的操作
我們上述講解的是非遞歸形式的二叉搜索樹的各個操作。當(dāng)我們了解非遞歸形式的二叉搜索樹的各個操作后，我們下面給出遞歸形式的二叉搜索樹的各個操作的代碼，思路就不在講解：
public:
bool eraseR(const K& key)
{
return _eraseR(_root,key);
}
bool insertR(const K& key)
{
return _insertR(_root,key);
}
bool findR(const K& key)
{
return _findR(_root,key);
}
private:
bool _findR(Node* root,const K& key)
{
if(root==nullptr)
{
return false;
}
if(root->_key>key)
{
_findR(root->left,key);
}
else if(root->_key<key)
{
_findR(root->right,key);
}
else
{
return true;
}
}
bool _eraseR(Node*& root,const K& key)
{
if(root==nullptr)
{
return false;
}
if(root->_key>key)
{
_eraseR(root->left,key);
}
else if(root->_key<key)
{
_eraseR(root->right,key);
}
else
{
Node* del=root;
if(root->left==nullptr)
{
root=root->right;
}
else if(root->right==nullptr)
{
root=root->left;
}
else
{
Node* min=root->right;
while(min->left)
{
min=min->left;
}
swap(root->_key,min->_key);
return _eraseR(root->right,key);
}
delete del;
return true;
}
}
bool _insertR(Node*& root,const K& key)
{
if(root==nullptr)
{
root=new Node(key);
return true;
}
if(root->_key>key)
{
_insertR(root->left,key);
}
else if(root->_key<key)
{
_insertR(root->right,key);
}
else
{
return false;
}
}三、二叉搜索樹的性能分析
插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個操作的性能。對有n個結(jié)點(diǎn)的二叉搜索樹，若每個元素查找的概率相等，則二叉搜索樹平均查找長度是結(jié)點(diǎn)在二叉搜索樹的深度的函數(shù)，即結(jié)點(diǎn)越深，則比較次數(shù)越多。 但對于同一個關(guān)鍵碼集合，如果各關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹：
通過上述我們也發(fā)現(xiàn)，二叉搜索樹的性能主要取決于樹的平衡度。最理想的情況下，樹是完全平衡的，即左子樹節(jié)點(diǎn)數(shù)目和右子樹節(jié)點(diǎn)數(shù)目相差不超過1。在這種情況下，查找、插入和刪除操作的平均時間復(fù)雜度為 O(log n)。但是，最壞情況下，樹可能變得非平衡，導(dǎo)致這些操作的時間復(fù)雜度退化為O(n)，其中n是樹中節(jié)點(diǎn)的總數(shù)。
為了避免二叉搜索樹在使用過程中出現(xiàn)不平衡的情況，可以使用自平衡的二叉搜索樹，如紅黑樹或AVL樹。這些樹通過旋轉(zhuǎn)、調(diào)整節(jié)點(diǎn)顏色等策略來保持樹的平衡度，從而提高了整體性能。
總結(jié)起來，二叉搜索樹在C++編程語言中的實(shí)現(xiàn)非常靈活且易于理解。但需要注意的是，對于大型數(shù)據(jù)集合，建議使用自平衡的二叉搜索樹，以確保操作的效率和性能。
以上就是詳解C++二叉搜索樹的原理及實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++二叉搜索樹的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C語言代碼實(shí)現(xiàn)三子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-11-11
這篇文章主要介紹了六大排序算法-插入排序、希爾排序、選擇排序、冒泡排序、堆排序、快速排序，需要學(xué)習(xí)的小伙伴可以參考這篇文章2021-08-08
深入理解:Java是類型安全的語言,而C++是非類型安全的語言
本篇文章是對Java是類型安全的語言,而C++是非類型安全的語言進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-06-06
本篇文章是C語言系列基礎(chǔ)篇，C語言中,static是用來修飾變量和函數(shù):1.修飾局部變量–>靜態(tài)局部變量2.修飾全局變量–>靜態(tài)全局變量3.修飾函數(shù)–>靜態(tài)函數(shù)2021-08-08
消息隊列在多線程的場景有時會用到，尤其是線程通信跨線程調(diào)用的時候，就可以使用消息隊列進(jìn)行通信。本文將利用C++實(shí)現(xiàn)一個簡單的消息隊列，感興趣的可以了解一下2022-12-12
這篇文章主要為大家詳細(xì)介紹了C語言中文件相關(guān)函數(shù)的使用，可以實(shí)現(xiàn)文件的讀寫、打開和關(guān)閉。文中通過示例進(jìn)行了詳細(xì)介紹，需要的可以參考一下2022-07-07
這篇文章主要介紹了C語言時間處理實(shí)例分享的相關(guān)資料,需要的朋友可以參考下2015-07-07
這篇文章主要介紹了C++ 中的繼承，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-04-04
C++讀取訪問權(quán)限沖突引發(fā)異常問題的原因分析
C語言是一門通用計算機(jī)編程語言,廣泛應(yīng)用于底層開發(fā),最近在用C++寫代碼時經(jīng)常會遇到“引發(fā)了異常: 讀取訪問權(quán)限沖突,所以這篇文章主要給大家介紹了關(guān)于C++讀取訪問權(quán)限沖突引發(fā)異常問題的相關(guān)資料,需要的朋友可以參考下2021-07-07
windows?使用ffmpeg?.a靜態(tài)庫讀取Wav音頻并保存PCM的方法
這篇文章主要介紹了windows?使用ffmpeg?.a靜態(tài)庫讀取Wav音頻并保存PCM,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2024-02-02