詳解C++二叉搜索樹(shù)的原理及實(shí)現(xiàn)
一、二叉搜索樹(shù)的概念
二叉搜索樹(shù)又稱(chēng)二叉排序樹(shù)，二叉搜索樹(shù)是一種二叉樹(shù)，其中每個(gè)節(jié)點(diǎn)的值大于其左子樹(shù)中的任何節(jié)點(diǎn)，并且小于其右子樹(shù)中的任何節(jié)點(diǎn)。這個(gè)特性使得二叉搜索樹(shù)具有高效的查找、插入和刪除操作。下圖即為二叉搜索樹(shù)：
二、二叉搜索樹(shù)的操作及實(shí)現(xiàn)
由于二叉搜索樹(shù)的特性，使得二叉搜索樹(shù)具有高效的查找、插入和刪除操作。在我們分析各個(gè)操作的效率和實(shí)現(xiàn)原理之前，我們先把二叉樹(shù)的大體結(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 二叉搜索樹(shù)的插入
2.1.1 插入的原理
插入一個(gè)新的值時(shí)，我們需要遵守二叉搜索樹(shù)的特性。首先，我們從根節(jié)點(diǎn)開(kāi)始找到合適的插入位置。具體操作是，將新值與當(dāng)前節(jié)點(diǎn)的值比較，若新值小于當(dāng)前節(jié)點(diǎn)的值，則往左子樹(shù)方向找到合適的葉子節(jié)點(diǎn)進(jìn)行插入；反之，若新值大于當(dāng)前節(jié)點(diǎn)的值，則往右子樹(shù)方向找到合適的葉子節(jié)點(diǎn)進(jìn)行插入。
合適的葉子節(jié)點(diǎn)指的是一直往下查找，直到該位置為空（nullptr）時(shí)，此時(shí)新值就應(yīng)該插入該位置。即使我們找到了合適的位置，如果不知道該位置的父節(jié)點(diǎn)的話，似乎并不能連接到該樹(shù)中。所以在查找合適位置的同時(shí)，還需要維護(hù)一個(gè)父節(jié)點(diǎn)。但是我們需要注意，二叉搜索樹(shù)中沒(méi)有重復(fù)的值。如果插入重復(fù)的值，那么就會(huì)插入失敗。
同時(shí)，我們?cè)俨迦肭埃袛嘣摌?shù)是否為空。否則就會(huì)出現(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 二叉搜索樹(shù)的查找
2.2.1 查找的原理
其實(shí)在上述的插入中，我們不就進(jìn)行了查找嗎？！為了查找一個(gè)特定的值，我們從根節(jié)點(diǎn)開(kāi)始向下遍歷二叉樹(shù)，根據(jù)當(dāng)前節(jié)點(diǎn)的值與目標(biāo)值的大小關(guān)系來(lái)選擇往左子樹(shù)或者右子樹(shù)進(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 二叉搜索樹(shù)的刪除
2.3.1 刪除的原理
刪除操作是相對(duì)復(fù)雜的，因?yàn)槲覀冃枰幚聿煌那闆r。具體步驟如下：
- 如果要?jiǎng)h除的節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)，直接刪除即可。
- 如果要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，將子節(jié)點(diǎn)替換為要?jiǎng)h除的節(jié)點(diǎn)即可。
- 如果要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，需要用其右子樹(shù)中最小的節(jié)點(diǎn)替換要?jiǎng)h除的節(jié)點(diǎn)，并且刪除右子樹(shù)中最小的節(jié)點(diǎn)。
對(duì)上述的情況在進(jìn)行分析和總結(jié)，一共可分為如下情況：
- 要?jiǎng)h除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn) 。刪除該結(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除節(jié)點(diǎn)的左孩子結(jié)點(diǎn)--直接刪除。
要?jiǎng)h除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn) 。刪除該結(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的右孩子結(jié)點(diǎn)--直接刪除。
- 要?jiǎng)h除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)。在它的右子樹(shù)中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小)，用它的值填補(bǔ)到被刪除節(jié)點(diǎn)中，再來(lái)處理該結(jié)點(diǎn)的刪除問(wèn)題--替換法刪除
為什么是上述的三種情況呢？我們?cè)敿?xì)分析一下是為什么。
假如我們要?jiǎng)h除的節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)，我們可以把這種情況看成要?jiǎng)h除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)或者只有右孩子結(jié)點(diǎn)。把另一個(gè)存在的孩子看成空（nullptr）。這樣刪除后，直接可讓其父節(jié)點(diǎn)指向空（nullptr），而不是野指針。
要?jiǎng)h除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)或者要?jiǎng)h除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)是兩種不同的情況。因?yàn)樗麄兊牟僮魇遣煌摹?/p>
要?jiǎng)h除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)這種情況較為復(fù)雜。首先我們應(yīng)該找到能夠填充該位置的節(jié)點(diǎn)。根據(jù)二叉搜索樹(shù)的特性每個(gè)節(jié)點(diǎn)的值大于其左子樹(shù)中的任何節(jié)點(diǎn)，并且小于其右子樹(shù)中的任何節(jié)點(diǎn)，我們找到的值應(yīng)該也滿足此特點(diǎn)。有兩個(gè)節(jié)點(diǎn)的只滿足該情況：該節(jié)點(diǎn)左子樹(shù)的最大值、該節(jié)點(diǎn)右子樹(shù)的最小值。本篇文章講述的是左子樹(shù)的最大值。找左子樹(shù)的最大值，就是該子樹(shù)最右邊的節(jié)點(diǎn)。找到后交值換再刪除。
要?jiǎng)h除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)這種情況，在找左子樹(shù)的最大值時(shí)也應(yīng)該維護(hù)一個(gè)父節(jié)點(diǎn)。為什么呢？因?yàn)槲覀冋业阶笞訕?shù)的最大值時(shí)，與要?jiǎng)h除的節(jié)點(diǎn)的值交換后，要?jiǎng)h除該節(jié)點(diǎn)（交換前的左子樹(shù)最大值的節(jié)點(diǎn)）。此時(shí)該節(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 二叉搜索樹(shù)的中序遍歷
二叉搜索樹(shù)又稱(chēng)二叉排序樹(shù)，為什么又名二叉排序樹(shù)呢？二叉搜索樹(shù)的中序遍歷的結(jié)果就是一個(gè)有序的結(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)二叉樹(shù)的操作
我們上述講解的是非遞歸形式的二叉搜索樹(shù)的各個(gè)操作。當(dāng)我們了解非遞歸形式的二叉搜索樹(shù)的各個(gè)操作后，我們下面給出遞歸形式的二叉搜索樹(shù)的各個(gè)操作的代碼，思路就不在講解：
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;
}
}三、二叉搜索樹(shù)的性能分析
插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹(shù)中各個(gè)操作的性能。對(duì)有n個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)，若每個(gè)元素查找的概率相等，則二叉搜索樹(shù)平均查找長(zhǎng)度是結(jié)點(diǎn)在二叉搜索樹(shù)的深度的函數(shù)，即結(jié)點(diǎn)越深，則比較次數(shù)越多。 但對(duì)于同一個(gè)關(guān)鍵碼集合，如果各關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹(shù)：
通過(guò)上述我們也發(fā)現(xiàn)，二叉搜索樹(shù)的性能主要取決于樹(shù)的平衡度。最理想的情況下，樹(shù)是完全平衡的，即左子樹(shù)節(jié)點(diǎn)數(shù)目和右子樹(shù)節(jié)點(diǎn)數(shù)目相差不超過(guò)1。在這種情況下，查找、插入和刪除操作的平均時(shí)間復(fù)雜度為 O(log n)。但是，最壞情況下，樹(shù)可能變得非平衡，導(dǎo)致這些操作的時(shí)間復(fù)雜度退化為O(n)，其中n是樹(shù)中節(jié)點(diǎn)的總數(shù)。
為了避免二叉搜索樹(shù)在使用過(guò)程中出現(xiàn)不平衡的情況，可以使用自平衡的二叉搜索樹(shù)，如紅黑樹(shù)或AVL樹(shù)。這些樹(shù)通過(guò)旋轉(zhuǎn)、調(diào)整節(jié)點(diǎn)顏色等策略來(lái)保持樹(shù)的平衡度，從而提高了整體性能。
總結(jié)起來(lái)，二叉搜索樹(shù)在C++編程語(yǔ)言中的實(shí)現(xiàn)非常靈活且易于理解。但需要注意的是，對(duì)于大型數(shù)據(jù)集合，建議使用自平衡的二叉搜索樹(shù)，以確保操作的效率和性能。
以上就是詳解C++二叉搜索樹(shù)的原理及實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++二叉搜索樹(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++開(kāi)發(fā)：為什么多線程讀寫(xiě)shared_ptr要加鎖的詳細(xì)介紹
本篇文章介紹了，在C++中為什么多線程讀寫(xiě)shared_ptr要加鎖的詳細(xì)說(shuō)明。需要的朋友參考下2013-04-04
C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單井字棋游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單井字棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-04-04
輸入一個(gè)字符串,取出其中的整數(shù)(實(shí)現(xiàn)代碼)
輸入一個(gè)字符串，內(nèi)含所有數(shù)字和非數(shù)字字符。將其中連續(xù)的數(shù)字作為一個(gè)整數(shù)，依次存放到一個(gè)數(shù)組中，統(tǒng)計(jì)共有多少個(gè)整數(shù)，并輸出這些數(shù)2013-09-09
C++語(yǔ)言實(shí)現(xiàn)線性表之?dāng)?shù)組實(shí)例
這篇文章主要介紹了C++語(yǔ)言實(shí)現(xiàn)線性表之?dāng)?shù)組,實(shí)例分析了C++實(shí)現(xiàn)數(shù)組形式線性表的原理與方法,需要的朋友可以參考下2015-04-04
C++生成隨機(jī)數(shù)的實(shí)現(xiàn)代碼
這篇文章主要介紹了C++生成隨機(jī)數(shù)的實(shí)現(xiàn)代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-04-04
Visual Studio Code運(yùn)行程序時(shí)輸出中文成亂碼問(wèn)題及解決方法
這篇文章主要介紹了解決Visual Studio Code運(yùn)行程序時(shí)輸出中文成亂碼問(wèn)題，本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-03-03
簡(jiǎn)單介紹C++編程中派生類(lèi)的析構(gòu)函數(shù)
這篇文章主要介紹了C++編程中派生類(lèi)的析構(gòu)函數(shù),析構(gòu)函數(shù)平時(shí)一般使用較少,需要的朋友可以參考下2015-09-09
Qt數(shù)據(jù)庫(kù)應(yīng)用之實(shí)現(xiàn)數(shù)據(jù)分組導(dǎo)出
這篇文章主要為大家詳細(xì)介紹了如何利用Qt實(shí)現(xiàn)數(shù)據(jù)庫(kù)數(shù)據(jù)分組導(dǎo)出，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)或工作有一定參考價(jià)值，需要的可以了解一下2022-06-06
這篇文章主要介紹了c語(yǔ)言二進(jìn)制數(shù)按位輸出示例,需要的朋友可以參考下2014-03-03
這篇文章主要介紹了C++設(shè)計(jì)模式之外觀模式,本文詳細(xì)講解了C++中的Facade模式,并給出了實(shí)例代碼,需要的朋友可以參考下2014-10-10