柚子快報(bào)邀請(qǐng)碼778899分享：【c++】二叉搜索樹（BST）

http://yzkb.51969.com/

?個(gè)人主頁(yè)：Quitecoder

?專欄：c++筆記倉(cāng)

朋友們大家好，本篇文章來(lái)到二叉搜索樹的內(nèi)容

目錄

`1.二叉搜索樹的介紹``2.二叉搜索樹的操作與實(shí)現(xiàn)``insert插入``Find查找``InOrder中序遍歷``Erase刪除`

`3.二叉搜索樹的應(yīng)用（K與KV模型）``改造二叉樹為KV結(jié)構(gòu)`

`4.二叉搜索樹性能分析`

1.二叉搜索樹的介紹

二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹:

若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值它的左右子樹也分別為二叉搜索樹

它在動(dòng)態(tài)數(shù)據(jù)集合中維護(hù)了一定的排序順序，以便實(shí)現(xiàn)快速的數(shù)據(jù)查找、插入和刪除操作

左子樹比根小，右子樹比根大

比如我想查找13，就不需要暴力比較，按照大小往左邊或者右邊走

對(duì)于二叉搜索樹，進(jìn)行中序遍歷為升序

2.二叉搜索樹的操作與實(shí)現(xiàn)

首先我們構(gòu)建節(jié)點(diǎn)：

template

struct BSTreeNode

{

K _key;

BSTreeNode* _left;

BSTreeNode* _right;

BSTreeNode()

:_key(K())

,_left(nullptr)

,_right(nullptr)

{}

BSTreeNode(const K& key)

: _key(key)

, _left(nullptr)

, _right(nullptr)

{}

};

每個(gè)節(jié)點(diǎn)有兩個(gè)指針，分別指向它的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。如果子節(jié)點(diǎn)不存在，則這些指針為nullptr

默認(rèn)構(gòu)造函數(shù)：

BSTreeNode()

:_key(K())

,_left(nullptr)

,_right(nullptr)

{}

默認(rèn)構(gòu)造函數(shù)，它初始化鍵值為K類型的默認(rèn)值（通過(guò)調(diào)用K的默認(rèn)構(gòu)造函數(shù)），并將左右子節(jié)點(diǎn)指針都設(shè)置為nullptr，表示節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)

參數(shù)化構(gòu)造函數(shù)：

BSTreeNode(const K& key)

: _key(key)

, _left(nullptr)

, _right(nullptr)

{}

采用鍵值作為參數(shù)的構(gòu)造函數(shù)，它會(huì)創(chuàng)建一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)的鍵值為傳入的key值，同時(shí)初始化左右子節(jié)點(diǎn)指針為nullptr

接著我們來(lái)完成主體部分：

template

class BSTree

{

public:

typedef BSTreeNode Node;

private:

Node* _root = nullptr;

};

insert插入

比如插入5，我們從根節(jié)點(diǎn)開始，比8小，往左走，比3大，往右走…：

bool Insert(const T& key)

{

Node* cur = _root;

while (cur)

{

if (cur->_key < key)

{

cur = cur->_right;

}

else if (cur->_key > key)

{

cur = cur->_left;

}

else

{

return false;

}

}

return true;

}

比當(dāng)前節(jié)點(diǎn)小，往左走，反之往右走，搜索樹默認(rèn)是不允許插入重復(fù)鍵值

所以遇到相同的直接返回false，但是最后一步插入，我們還需要父親位置的節(jié)點(diǎn)來(lái)完成左邊插入或者右邊插入，所以我們需要一個(gè)父親節(jié)點(diǎn)來(lái)記錄位置：

bool Insert(const T& 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

{

return false;

}

}

cur = new Node(key);

if (parent->_key < key)

{

parent->_right = cur;

}

else

{

parent->_left = cur;

}

return true;

}

由于我們是從根部開始向下遍歷直到達(dá)到葉節(jié)點(diǎn)，parent->_key必定不等于key（因?yàn)橛兄貜?fù)檢查）。如果parent的鍵值小于插入的鍵值key，新節(jié)點(diǎn)被設(shè)置為父節(jié)點(diǎn)的右子樹；否則設(shè)置為左子樹

注意

這里如果起始為**空樹*

Node* cur = _root;

while (cur)

{

// ...

}

由于cur是從_root開始的，如果跳過(guò)判空且_root實(shí)際上為nullptr，這個(gè)循環(huán)不會(huì)執(zhí)行任何操作，因?yàn)樗臈l件立即不滿足（cur此時(shí)為nullptr），并且會(huì)跳到循環(huán)之后的代碼，如下：

cur = new Node(key);

// ...

這里將創(chuàng)建一個(gè)新的節(jié)點(diǎn)，但此時(shí)變量parent仍然是nullptr。代碼會(huì)接著嘗試訪問(wèn)parent的_key成員：

if (parent->_key < key)

{

// ...

}

因?yàn)閜arent是nullptr，這會(huì)導(dǎo)致未定義行為，最常見(jiàn)的是程序崩潰，因?yàn)槟悴荒軐?duì)nullptr解引用。另外，即使程序不崩潰，新的節(jié)點(diǎn)cur也沒(méi)有父節(jié)點(diǎn)可以掛載到，這樣二叉搜索樹的結(jié)構(gòu)就不完整了

所以完整代碼如下：

bool Insert(const T& 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;

}

Find查找

find這里思路很簡(jiǎn)單，就按照大小關(guān)系往下遍歷即可：

bool Find(const T& 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;

}

InOrder中序遍歷

void _InOrder(Node* root)

{

if (root == nullptr)

{

return;

}

_InOrder(root->_left);

cout << root->_key << " ";

_InOrder(root->_right);

}

這里我們需要傳入根節(jié)點(diǎn)，為類成員，單獨(dú)一個(gè)函數(shù)是無(wú)法實(shí)現(xiàn)的，所以我們先完成上面的子函數(shù)書寫，再一個(gè)主函數(shù)傳入_root即可

void InOrder()

{

_InOrder(_root);

cout << endl;

}

測(cè)試如下：

int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

for (int e : a)

{

b1.Insert(e);

}

b1.InOrder();

Erase刪除

二叉樹的刪除是這里的難點(diǎn)，因?yàn)樗婕暗蕉喾N情況，針對(duì)不同的情況我們對(duì)應(yīng)不同的方法：

要?jiǎng)h除的結(jié)點(diǎn)無(wú)孩子結(jié)點(diǎn)要?jiǎng)h除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)要?jiǎng)h除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)要?jiǎng)h除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)

前三種情況可以結(jié)合起來(lái)：

情況2：刪除該結(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除節(jié)點(diǎn)的左孩子結(jié)點(diǎn)–直接刪除

情況3：刪除該結(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的右孩子結(jié)點(diǎn)–直接刪除

情況4：替換法解決

對(duì)于一個(gè)節(jié)點(diǎn)，它的：

中序前驅(qū)是它左子樹中的最大節(jié)點(diǎn)，它小于該節(jié)點(diǎn)且最接近它。中序后繼是它右子樹中的最小節(jié)點(diǎn)，它大于該節(jié)點(diǎn)且最接近它。

替換法刪除的思路分為以下步驟：

找到需要被刪除的節(jié)點(diǎn)。檢查這個(gè)節(jié)點(diǎn)是否有兩個(gè)子節(jié)點(diǎn)：

如果不是，處理起來(lái)比較簡(jiǎn)單，可以直接刪除。如果該節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，則該子節(jié)點(diǎn)取代被刪除節(jié)點(diǎn)的位置。如果是葉節(jié)點(diǎn)，可以直接移除。如果是，執(zhí)行以下步驟。 選擇使用中序前驅(qū)或中序后繼來(lái)替換要?jiǎng)h除的節(jié)點(diǎn)。我們通常默認(rèn)使用中序后繼，但兩者均可。找到中序后繼節(jié)點(diǎn)：

進(jìn)入待刪除節(jié)點(diǎn)的右子樹，然后一直向左走，直到找到?jīng)]有左子節(jié)點(diǎn)的節(jié)點(diǎn)；這是中序后繼。 替換：

復(fù)制中序后繼節(jié)點(diǎn)的值到待刪除節(jié)點(diǎn)中，覆蓋原有值此時(shí)，待刪除節(jié)點(diǎn)的值已更新為其中序后繼節(jié)點(diǎn)的值，原來(lái)的中序后繼節(jié)點(diǎn)可以被移除（因?yàn)樗呀?jīng)被復(fù)制了）。需要注意，這個(gè)中序后繼節(jié)點(diǎn)不會(huì)有左子節(jié)點(diǎn)（因?yàn)樗呀?jīng)是某個(gè)子樹中的最左側(cè)節(jié)點(diǎn)），所以它要么是一個(gè)葉節(jié)點(diǎn)，要么只有一個(gè)右子節(jié)點(diǎn) 刪除中序后繼節(jié)點(diǎn)：

通過(guò)調(diào)整指針，將中序后繼節(jié)點(diǎn)的父節(jié)點(diǎn)指向其可能存在的右子節(jié)點(diǎn)（也可能為空），完成刪除操作

進(jìn)行這樣的替換之后，二叉搜索樹的特性依然得以保持。中序后繼節(jié)點(diǎn)保證了替換后的節(jié)點(diǎn)值仍然比其左子節(jié)點(diǎn)的所有值大，且比其右子節(jié)點(diǎn)（除了被移除的中序后繼節(jié)點(diǎn)外）的所有值小

替換法刪除操作需要注意的關(guān)鍵點(diǎn)是，通過(guò)中序前驅(qū)或中序后繼節(jié)點(diǎn)替換，實(shí)際上我們把刪除一個(gè)可能有兩個(gè)子節(jié)點(diǎn)的難題轉(zhuǎn)變成了刪除一個(gè)有零個(gè)或一個(gè)子節(jié)點(diǎn)的簡(jiǎn)單問(wèn)題，且這個(gè)中序后繼節(jié)點(diǎn)一定在待刪除節(jié)點(diǎn)的右子樹中最左側(cè)

bool Erase(const T& key)

{

if (_root == nullptr)

return false;

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;

}

}

delete cur;

}

else

{

//左右都不為空，替換法刪除

Node* rightminparent = cur;

Node* rightmin = cur->_right;

while (rightmin->_left)

{

rightminparent = rightmin;

rightmin = rightmin->_left;

}

cur->_key = rightmin->_key;

if (rightminparent->_left = rightmin)

{

rightminparent->_left = rightmin->_right;

}

else

{

rightminparent->_right = rightmin->_right;

}

delete rightmin;

}

return true;

}

}

return false;

}

我們拆分來(lái)看這串代碼：

檢查樹是否為空:

if (_root == nullptr)

return false;

查找需刪除的節(jié)點(diǎn): 代碼通過(guò)while循環(huán)遍歷樹找到匹配key的節(jié)點(diǎn)。在循環(huán)中使用變量cur作為當(dāng)前節(jié)點(diǎn)，變量parent作為cur的父節(jié)點(diǎn) 節(jié)點(diǎn)匹配: 當(dāng)找到與key匹配的節(jié)點(diǎn)后:

如果該節(jié)點(diǎn)沒(méi)有左子節(jié)點(diǎn)(cur->_left == nullptr), 那么它的右子節(jié)點(diǎn)直接替換它（也適用于它沒(méi)有子節(jié)點(diǎn)的情況）如果該節(jié)點(diǎn)沒(méi)有右子節(jié)點(diǎn)(cur->_right == nullptr), 那么它的左子節(jié)點(diǎn)直接替換它

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;

}

如果cur恰好是根節(jié)點(diǎn)，我們直接將樹的根 _root 指向cur的右子節(jié)點(diǎn)。這個(gè)更新意味著我們?cè)跇渲幸瞥烁?jié)點(diǎn)，并將右子節(jié)點(diǎn)（如果存在）提升為新的根節(jié)點(diǎn)。

如果cur不是根節(jié)點(diǎn)，我們需要更新它父節(jié)點(diǎn)的相應(yīng)指針。我們檢查cur是其父節(jié)點(diǎn)的左子還是右子，并相應(yīng)地更新父節(jié)點(diǎn)的左指針或右指針，使其指向cur的右子節(jié)點(diǎn)。這樣，在二叉搜索樹中刪除了cur節(jié)點(diǎn)，并保持了其右子樹

如果該節(jié)點(diǎn)既有左子節(jié)點(diǎn)也有右子節(jié)點(diǎn), 那么需要找到該節(jié)點(diǎn)的中序后繼節(jié)點(diǎn)來(lái)替代它。中序后繼節(jié)點(diǎn)是在其右子樹中值最小的節(jié)點(diǎn)。我們替換cur的鍵為中序后繼節(jié)點(diǎn)的鍵，并將rightmin放在原來(lái)的位置上。

else

{

//左右都不為空，替換法刪除

Node* rightminparent = cur;

Node* rightmin = cur->_right;

while (rightmin->_left)

{

rightminparent = rightmin;

rightmin = rightmin->_left;

}

cur->_key = rightmin->_key;

if (rightminparent->_left == rightmin)

{

rightminparent->_left = rightmin->_right;

}

else

{

rightminparent->_right = rightmin->_right;

}

delete rightmin;

}

注意，在替換完成后需要?jiǎng)h除原始的中序后繼節(jié)點(diǎn)。這時(shí)rightmin的右子節(jié)點(diǎn)（如果存在）會(huì)替換rightmin。

每次刪除一個(gè)節(jié)點(diǎn)后，代碼會(huì)釋放該節(jié)點(diǎn)的內(nèi)存。

維護(hù)父節(jié)點(diǎn)指針: 刪除過(guò)程中對(duì)父節(jié)點(diǎn)指針的適當(dāng)維護(hù)是必須的，以確保刪除節(jié)點(diǎn)后樹的結(jié)構(gòu)保持正確。比如，如果待刪除節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)，那么父節(jié)點(diǎn)的左指針應(yīng)該指向待刪除節(jié)點(diǎn)的相應(yīng)子節(jié)點(diǎn)

最后，如果在樹中找到并成功刪除了key對(duì)應(yīng)的節(jié)點(diǎn)，則函數(shù)返回true。如果沒(méi)有找到，則函數(shù)返回false。

3.二叉搜索樹的應(yīng)用（K與KV模型）

K模型：

K模型指的是二叉樹的節(jié)點(diǎn)僅存儲(chǔ)鍵Key）信息，而沒(méi)有與鍵相關(guān)聯(lián)的特定“值”（Value）。換句話說(shuō)，節(jié)點(diǎn)中的數(shù)據(jù)只有一個(gè)維度，節(jié)點(diǎn)的排序和組織就是基于這些鍵在K模型的二叉樹中，例如二叉搜索樹（BST），節(jié)點(diǎn)的位置由其鍵的順序決定。所有的節(jié)點(diǎn)操作，包括插入、查找和刪除都是根據(jù)這個(gè)鍵來(lái)執(zhí)行的。

比如：給一個(gè)單詞word，判斷該單詞是否拼寫正確，具體方式如下：

以詞庫(kù)中所有單詞集合中的每個(gè)單詞作為key，構(gòu)建一棵二叉搜索樹在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯(cuò)誤

KV模型：

KV模型指的是二叉樹的節(jié)點(diǎn)存儲(chǔ)“鍵值對(duì)”（Key-Value Pair）。這里“鍵”（Key）用于確定節(jié)點(diǎn)的位置跟順序，“值”（Value）則是與鍵關(guān)聯(lián)的數(shù)據(jù)。在KV模型的二叉樹中，節(jié)點(diǎn)依然是根據(jù)鍵的順序進(jìn)行排列和組織的，但是與每個(gè)鍵都有一個(gè)相對(duì)應(yīng)的值。這種模式適用于情況更為復(fù)雜的場(chǎng)景，如實(shí)現(xiàn)映射或字典結(jié)構(gòu)。KV模型的一個(gè)典型例子是映射（Map）或詞典（Dictionary）

比如英漢詞典就是英文與中文的對(duì)應(yīng)關(guān)系，通過(guò)英文可以快速找到與其對(duì)應(yīng)的中文，英文單詞與其對(duì)應(yīng)的中文就構(gòu)成一種鍵值對(duì)；

再比如統(tǒng)計(jì)單詞次數(shù)，統(tǒng)計(jì)成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出現(xiàn)次數(shù)就是就構(gòu)成一種鍵值對(duì)

改造二叉樹為KV結(jié)構(gòu)

節(jié)點(diǎn)構(gòu)建，加一個(gè)模版參數(shù)V

template

struct BSTreeNode

{

V _value;

K _key;

BSTreeNode* _left;

BSTreeNode* _right;

BSTreeNode()

:_key(K())

, _value(V());

, _left(nullptr)

, _right(nullptr)

{}

BSTreeNode(const K& key,const V& value)

: _key(key)

,_value(value)

, _left(nullptr)

, _right(nullptr)

{}

};

代碼主題部分只需要進(jìn)行簡(jiǎn)單的修改即可：

template

class BSTree

{

public:

typedef BSTreeNode Node;

bool Insert(const K& key,const V& value)

{........

cur = new Node(key,value);

........

}

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;

}

........

};

其余部分不需要改變

簡(jiǎn)單示例如下：

void TestBSTree2()

{

BSTree dict;

dict.Insert("string", "字符串");

dict.Insert("left", "左邊");

dict.Insert("insert", "插入");

//...

string str;

while (cin >> str)

{

BSTreeNode* ret = dict.Find(str);

if (ret)

{

cout << ret->_value << endl;

}

else

{

cout << "無(wú)此單詞，請(qǐng)重新輸入" << endl;

}

}

}

本節(jié)內(nèi)容到此結(jié)束！ 感謝閱讀?。?/p>

4.二叉搜索樹性能分析

插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個(gè)操作的性能

對(duì)有n個(gè)結(jié)點(diǎn)的二叉搜索樹，若每個(gè)元素查找的概率相等，則二叉搜索樹平均查找長(zhǎng)度是結(jié)點(diǎn)在二叉搜索樹的深度的函數(shù)，即結(jié)點(diǎn)越深，則比較次數(shù)越多

但對(duì)于同一個(gè)關(guān)鍵碼集合，如果各關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹：

最優(yōu)情況下，二叉搜索樹為完全二叉樹(或者接近完全二叉樹)，其平均比較次數(shù)為O(log n)

最差情況下，二叉搜索樹退化為單支樹(或者類似單支)，查找的時(shí)間復(fù)雜度為O(n)

如果退化成單支樹，二叉搜索樹的性能就失去了。那能否進(jìn)行改進(jìn)，不論按照什么次序插入關(guān)鍵碼，二叉搜索樹的性能都能達(dá)到最優(yōu)？

期待后續(xù)AVL樹和紅黑樹的講解

本節(jié)內(nèi)容到此結(jié)束??！感謝閱讀??！

柚子快報(bào)邀請(qǐng)碼778899分享：【c++】二叉搜索樹（BST）

http://yzkb.51969.com/

參考閱讀