C++數據結構二叉搜索樹的實現應用與分析
⭐️博客代碼已上傳至gitee：https://gitee.com/byte-binxin/cpp-class-code
🌏概念
二叉搜索樹又稱為二叉排序書，因為這棵樹的中序遍歷是有序的。二叉搜索樹總結起來有以下幾個性質：
- 若它的左子樹不為空，則左子樹上所有節點的值都小於根節點的值
- 若它的右子樹不為空，則右子樹上所有節點的值都大於於根節點的值
- 它的左右子樹都是二叉搜索樹
- 這棵樹中沒有重復的元素
🌏二叉搜索樹的實現
🌲基本框架
由一個節點的成員構成，先構建節點的類型，和我們之前數據結構中的二叉樹的節點定義是一樣的。二叉搜索樹的根節點先默認給空。
template <class K, class V>
struct BSTNode
{
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;
K _key;
V _value;
BSTNode(const K& key, const V& value)
:_left(nullptr)
, _right(nullptr)
, _key(key)
,_value(value)
{}
};
template <class K, class V>
class BSTree //Binary Search Tree
{
typedef BSTNode<K, V> Node;
private:
Node* _root = nullptr;
};
🌲二叉搜索樹的插入
插入分為下面幾個步驟：
- 先判斷樹是否為空，為空就讓要插入的這個節點作為根節點，然後結束
- 部署就確定要插入節點的位置
- 用一個cur記錄當前節點，parent記錄父節點
- 要插入節點的值如果比當前節點的值小，cur就往左走，如果比當前節點的值大，就往右子樹走，如果等於就返回false，表面這棵樹中有這個數據，不需要插入。
下面是一個簡單的動圖演示
註意： 這裡不用擔心新插入節點會在樹中間插入，它一定是在最下面插入的，它會走到最下面，然後在樹的底部插入。
代碼實現如下：
bool Insert(const K& key, const V& value)
{
// 沒有節點時第一個節點就是根節點
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
// 用一個父親節點記錄cur的上一個節點
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
// 小於往左邊走
if (key < cur->_key)
cur = cur->_left;
else if (key > cur->_key)
cur = cur->_right;
else
return false;// 已有的節點不插入，此次插入失敗
}
cur = new Node(key, value);
// 判斷應該插在父節點的左邊還是右邊
if (cur->_key < parent->_key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
為瞭更好地觀察這棵樹插入後是否有效，我們可以實現一個中序遍歷，將其打印出來。 中序遍歷代碼如下：
void InOrder()
{
// 利用子函數遍歷
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}
測試代碼如下：
void TestBSTree()
{
BSTree<int> bt;
int arr[] = { 5,3,4,1,7,8,2,6,0,9 };
//int arr[] = { 1,2,3,4 };
//int arr[] = { 4,3,2,1};
for (auto e : arr)
{
bt.Insert(e);
}
bt.InOrder();
}
代碼運行結果如下：
🌲二叉搜索樹的查找
查找的步驟如下：（和插入的步驟有些類似）
- 如果查找值key比當前節點的值小，就往左子樹走
- 如果查找值key比當前節點的值大，就往右子樹走
- 如果查找值key和當前節點的值相等，就返回當前節點的指針
代碼實現如下：
Node* Find(const K& key)
{
if (_root == nullptr)
return nullptr;
Node* cur = _root;
while (cur)
{
// 小於往左邊走
if (key < cur->_key)
cur = cur->_left;
else if (key > cur->_key)
cur = cur->_right;
else
return cur;
}
return nullptr;
}
🌲二叉搜索樹的刪除（重點）
二叉搜索樹的刪除相對來說會復雜一些，下面我要給大傢分析一下。 有四種情況 先看下面這棵樹，分別對以下四個節點進行刪除會發生什麼（如何處理）？
- 刪除節點1時，它的左右都為空，可以直接刪除
- 刪除節點2時，它的左不為空右為空，刪除方法如下：
還要分析一種特殊的情況，就是此時2沒有父親節點，也就是自己為根時，看下面如何操作
- 刪除節點7時，它的左為為右不為空，刪除方法如下：
和情況2一樣，該節點如果為根節點，就讓自己的右孩子變成根節點。
- 左右都不為空（替代法）
這種情況我們采用替代法來解決，替代法就是找一個節點和現在這個節點交換，然後轉移為上面的情況，具體如下： 我們可以選擇用左子樹的最右節點（左子樹最大的節點）或右子樹的最左節點（右子樹的最小節點）和當前節點互換，然後刪除互換後的節點，這裡我們統一采用用右子樹的最右節點來進行替換。
然後這裡可以轉化為情況3來對節點進行刪除，因為所有的最左孩子一定是左為空，右是不確定的。
總結： 一共有四種情況，但是情況1可以歸為情況3，因為它也是左為空，所以整體處理下來是三種情況。
代碼實現如下：
bool Erase(const K& key)
{
// 如果樹為空，刪除失敗
if (_root == nullptr)
return false;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 小於往左邊走
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
// 找到瞭，開始刪除
// 1.左右子樹都為空 直接刪除 可以歸類為左為空
// 2.左右子樹隻有一邊為空 左為空，父親指向我的右，右為空，父親指向我的左
// 3.左右子樹都不為空 取左子樹最大的節點或右子樹最小的節點和要刪除的節點交換，然後再刪除
if (cur->_left == nullptr)
{
// 要刪除節點為根節點時，直接把右子樹的根節點賦值給——root
// 根節點的話會導致parent為nullptr
if (_root == cur)
{
_root = _root->_right;
}
else
{
// 左為空，父親指向我的右
// 判斷cur在父親的左還是右
if (parent->_left == cur) // cur->_key < parent->_key
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
cur = nullptr;
}
else if (cur->_right == nullptr)
{
if (_root == cur)
{
_root = _root->_left;
}
else
{
// 右為空，父親指向我的左
// 判斷cur在父親的左還是右
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
cur = nullptr;
}
else
{
// 找右子樹中最小的節點
Node* rightMinParent = cur;
Node* rightMin = cur->_right;// 去右子樹找
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
//swap(cur->_key, rightMin->_key);
// 替代刪除
cur->_key = rightMin->_key;
// 轉換成瞭第一種情況 左為空
if (rightMinParent->_left == rightMin)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
rightMin = nullptr;
}
return true;
}
}
return false;
}
測試代碼如下：（要測試每種情況，還有測試刪空的情況）
void TestBSTree()
{
BSTree<int> bt;
int arr[] = { 5,3,4,1,7,8,2,6,0,9 };
for (auto e : arr)
{
cout << "插入 " << e << " 後：";
bt.Insert(e);
bt.InOrder();
}
cout << "------------------------------" << endl;
for (auto e : arr)
{
cout << "刪除 " << e << " 後：";
bt.Erase(e);
bt.InOrder();
}
}
代碼運行結果如下：
🌏二叉搜索樹的應用
二叉搜索樹有兩種模型：
- K模型： K模型隻有key值，節點隻存儲key值。這裡主要應用就是查找判斷某個元素在不在。
- KV模型： KV模型每個key值都對應著一個value，主要應用就是通過key找value。（我們平時查找單詞就是通過中文找英文，或者通過英文找中文）
下面我把上面的K模型的代碼簡單改造一下，實現KV模型：（這裡沒有使用傳鍵值對的方法，之後的博客我會給大傢介紹，這裡使用傳兩個值的方式）
template <class K, class V>
struct BSTNode
{
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;
K _key;
V _value;
BSTNode(const K& key, const V& value)
:_left(nullptr)
, _right(nullptr)
, _key(key)
,_value(value)
{}
};
template <class K, class V>
class BSTree //Binary Search Tree
{
typedef BSTNode<K, V> Node;
public:
~BSTree()
{
Node* cur = _root;
while (cur)
{
Erase(cur->_key);
cur = _root;
}
}
Node* Find(const K& key)
{
if (_root == nullptr)
return nullptr;
Node* cur = _root;
while (cur)
{
// 小於往左邊走
if (key < cur->_key)
cur = cur->_left;
else if (key > cur->_key)
cur = cur->_right;
else
return cur;
}
return nullptr;
}
bool Insert(const K& key, const V& value)
{
// 沒有節點時第一個節點就是根節點
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
// 用一個父親節點記錄cur的上一個節點
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
// 小於往左邊走
if (key < cur->_key)
cur = cur->_left;
else if (key > cur->_key)
cur = cur->_right;
else
return false;// 已有的節點不插入，此次插入失敗
}
cur = new Node(key, value);
// 判斷應該插在父節點的左邊還是右邊
if (cur->_key < parent->_key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
bool Erase(const K& key)
{
// 如果樹為空，刪除失敗
if (_root == nullptr)
return false;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 小於往左邊走
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
// 找到瞭，開始刪除
// 1.左右子樹都為空 直接刪除 可以歸類為左為空
// 2.左右子樹隻有一邊為空 左為空，父親指向我的右，右為空，父親指向我的左
// 3.左右子樹都不為空 取左子樹最大的節點或右子樹最小的節點和要刪除的節點交換，然後再刪除
if (cur->_left == nullptr)
{
// 要刪除節點為根節點時，直接把右子樹的根節點賦值給——root
// 根節點的話會導致parent為nullptr
if (_root == cur)
{
_root = _root->_right;
}
else
{
// 左為空，父親指向我的右
// 判斷cur在父親的左還是右
if (parent->_left == cur) // cur->_key < parent->_key
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
cur = nullptr;
}
else if (cur->_right == nullptr)
{
if (_root == cur)
{
_root = _root->_left;
}
else
{
// 右為空，父親指向我的左
// 判斷cur在父親的左還是右
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
cur = nullptr;
}
else
{
// 找右子樹中最小的節點
Node* rightMinParent = cur;
Node* rightMin = cur->_right;// 去右子樹找
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
//swap(cur->_key, rightMin->_key);
// 替代刪除
cur->_key = rightMin->_key;
// 轉換成瞭第一種情況 左為空
if (rightMinParent->_left == rightMin)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
rightMin = nullptr;
}
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 TestBSTree_KV1()
{
// 創建一個簡易的字典
BSTree<string, string> dict;
dict.Insert("蘋果", "apple");
dict.Insert("排序", "sort");
dict.Insert("培養", "cultivate");
dict.Insert("通過", "pass");
dict.Insert("apple", "蘋果");
dict.Insert("sort", "排序");
dict.Insert("cultivate", "培養");
dict.Insert("pass", "通過");
string str;
while (cin >> str)
{
BSTNode<string, string>* ret = dict.Find(str);
if (ret)
{
cout << ret->_value << endl;
}
else
{
cout << "本字典無此詞" << endl;
}
}
下面測試幾個應用： 實例1 英漢字典
void TestBSTree_KV1()
{
// 創建一個簡易的字典
BSTree<string, string> dict;
dict.Insert("蘋果", "apple");
dict.Insert("排序", "sort");
dict.Insert("培養", "cultivate");
dict.Insert("通過", "pass");
dict.Insert("apple", "蘋果");
dict.Insert("sort", "排序");
dict.Insert("cultivate", "培養");
dict.Insert("pass", "通過");
string str;
while (cin >> str)
{
BSTNode<string, string>* ret = dict.Find(str);
if (ret)
{
cout << ret->_value << endl;
}
else
{
cout << "本字典無此詞" << endl;
}
}
}
代碼運行結果演示：
實例2： 統計樹
void TestBSTree_KV2()
{
// 統計水果個數
BSTree<string, int> countTree;
string strArr[] = { "香蕉","水蜜桃","西瓜","蘋果","香蕉" ,"西瓜","香蕉" ,"蘋果","西瓜","蘋果","蘋果","香蕉" ,"水蜜桃" };
for (auto e : strArr)
{
BSTNode<string, int>* ret = countTree.Find(e);
if (ret == nullptr)
{
// 第一次插入
countTree.Insert(e, 1);
}
else
{
ret->_value++;
}
}
countTree.InOrder();
}
代碼運行結果如下：
🌏二叉樹性能分析
一般情況下，二叉搜索樹的插入和刪除的效率都是O(logN)，極端情況會導致效率變成O(N)。
理想狀態： 完全二叉樹：O(logN)
極端情況： 一條鏈：O(1)
後面我要和大傢分析的AVL樹會利用旋轉，就可解決掉這種極端情況。
🌐總結
上面這些是二叉搜索樹的大致內容，其中刪除大傢可以好好理解一下，它後面還有兩棵樹我還沒有介紹，就是AVL樹和紅黑樹，在後面兩篇博客我都會介紹。今天就先到這瞭，喜歡的話，歡迎點贊支持~
到此這篇關於C++數據結構二叉搜索樹的實現應用與分析的文章就介紹到這瞭,更多相關C++ 二叉搜索樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！