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