柚子快報(bào)邀請碼778899分享：java 【C++】二叉搜索樹
?個(gè)人主頁?：孤寂大仙V ?收錄專欄?：C++從小白到高手 ?往期回顧?：【C++】多態(tài) ? 流水不爭，爭的是滔滔不息
文章目錄
一、二叉搜索樹的概念二、搜索二叉樹的操作二叉搜索樹的插入二叉搜索樹的查找二叉搜索樹的刪除
三、二叉搜索樹的性能分析四、二叉搜索樹的實(shí)現(xiàn)代碼五、二叉搜索樹key和key/value使用場景key搜索場景key/value搜索場景：
六、key/value?叉搜索樹代碼實(shí)現(xiàn)
一、二叉搜索樹的概念
二叉搜索樹（Binary Search Tree, BST）又稱二叉排序樹是一種二叉樹，滿足以下性質(zhì)：
節(jié)點(diǎn)的左子樹上所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值。節(jié)點(diǎn)的右子樹上所有節(jié)點(diǎn)的值都大于該節(jié)點(diǎn)的值。左右子樹也必須是二叉搜索樹（遞歸定義）。
?叉搜索樹中可以?持插?相等的值，也可以不?持插?相等的值，具體看使?場景定義，后續(xù)我 們學(xué)習(xí)map/set/multimap/multiset系列容器底層就是?叉搜索樹，其中map/set不?持插?相等 值，multimap/multiset?持插?相等值。
二、搜索二叉樹的操作
二叉搜索樹的插入
樹為空，則直接新增結(jié)點(diǎn)，賦值給root指針樹不空，按?叉搜索樹性質(zhì)，插?值?當(dāng)前結(jié)點(diǎn)?往右?，插?值?當(dāng)前結(jié)點(diǎn)?往左?，找到空位置，插?新結(jié)點(diǎn)。如果?持插?相等的值，插?值跟當(dāng)前結(jié)點(diǎn)相等的值可以往右?，也可以往左?，找到空位置，插?新結(jié)點(diǎn)。（要注意的是要保持邏輯?致性，插?相等的值不要?會(huì)往右?，?會(huì)往左?）
bool Insert(const K& key)
{
if (_root == nullptr)
{
// 如果樹為空，直接創(chuàng)建根節(jié)點(diǎn)。
_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
{
// 如果發(fā)現(xiàn)相同的鍵值，則插入失敗。
return false;
}
}
// 創(chuàng)建新節(jié)點(diǎn)并插入到合適的位置。
cur = new Node(key);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
二叉搜索樹的查找
從根開始?較，查找x，x?根的值?則往右邊?查找，x?根值?則往左邊?查找。最多查找?度次，?到到空，還沒找到，這個(gè)值不存在。如果不?持插?相等的值，找到x即可返回。如果?持插?相等的值，意味著有多個(gè)x存在，?般要求查找中序的第?個(gè)x。如下圖，查找3，要找到1的右孩?的那個(gè)3返回。
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;
}
二叉搜索樹的刪除
?先查找元素是否在?叉搜索樹中，如果不存在，則返回false。 如果查找元素存在則分以下四種情況分別處理：（假設(shè)要?jiǎng)h除的結(jié)點(diǎn)為N）
1. 要?jiǎng)h除結(jié)點(diǎn)N左右孩?均為空 2. 要?jiǎng)h除的結(jié)點(diǎn)N左孩?位空，右孩?結(jié)點(diǎn)不為空 3. 要?jiǎng)h除的結(jié)點(diǎn)N右孩?位空，左孩?結(jié)點(diǎn)不為空 4. 要?jiǎng)h除的結(jié)點(diǎn)N左右孩?結(jié)點(diǎn)均不為空
對應(yīng)以上四種情況的解決?案：
把N結(jié)點(diǎn)的?親對應(yīng)孩?指針指向空，直接刪除N結(jié)點(diǎn)（情況1可以當(dāng)成2或者3處理，效果是?樣的）把N結(jié)點(diǎn)的?親對應(yīng)孩?指針指向N的右孩?，直接刪除N結(jié)點(diǎn)把N結(jié)點(diǎn)的?親對應(yīng)孩?指針指向N的左孩?，直接刪除N結(jié)點(diǎn)?法直接刪除N結(jié)點(diǎn)，因?yàn)镹的兩個(gè)孩??處安放，只能?替換法刪除。找N左?樹的值最?結(jié)點(diǎn)R(最右結(jié)點(diǎn))或者N右?樹的值最?結(jié)點(diǎn)R(最左結(jié)點(diǎn))替代N，因?yàn)檫@兩個(gè)結(jié)點(diǎn)中任意?個(gè)，放到N的位置，都滿??叉搜索樹的規(guī)則。替代N的意思就是N和R的兩個(gè)結(jié)點(diǎn)的值交換，轉(zhuǎn)?變成刪除R結(jié)點(diǎn)，R結(jié)點(diǎn)符合情況2或情況3，可以直接刪除。
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->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
Node* replaceParent = cur;
Node* replace = cur->_right;
while (replace->_left)
{
replaceParent = replace;
replace = replace->_left;
}
cur->_key = replace->_key;
if (replaceParent->_left == replace)
replaceParent->_left = replace->_right;
else
replaceParent->_right = replace->_right;
delete replace;
}
return true;
}
}
return false;
}
三、二叉搜索樹的性能分析
那么這樣的效率顯然是?法滿?我們需求的，我們后續(xù)課程需要繼續(xù)講解?叉搜索樹的變形，平衡?叉搜索樹AVL樹和紅?樹，才能適?于我們在內(nèi)存中存儲和搜索數(shù)據(jù)。
四、二叉搜索樹的實(shí)現(xiàn)代碼
#include
using namespace std;
namespace key
{
template
struct BSNode
{
K _key;
BSNode
BSNode
BSNode(const K& key)
: _key(key)
, _left(nullptr)
, _right(nullptr)
{}
};
template
class BSTree
{
using Node = BSNode
public:
//插入
bool Insert(const K& key)
{
if (_root == nullptr)
{
// 如果樹為空，直接創(chuàng)建根節(jié)點(diǎn)。
_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
{
// 如果發(fā)現(xiàn)相同的鍵值，則插入失敗。
return false;
}
}
// 創(chuàng)建新節(jié)點(diǎn)并插入到合適的位置。
cur = new Node(key);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
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;
}
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->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
Node* replaceParent = cur;
Node* replace = cur->_right;
while (replace->_left)
{
replaceParent = replace;
replace = replace->_left;
}
cur->_key = replace->_key;
if (replaceParent->_left == replace)
replaceParent->_left = replace->_right;
else
replaceParent->_right = replace->_right;
delete replace;
}
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 << " ";
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
}
五、二叉搜索樹key和key/value使用場景
key搜索場景
只有key作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲key即可，關(guān)鍵碼即為需要搜索到的值，搜索場景只需要判斷key在不在。key的搜索場景實(shí)現(xiàn)的?叉樹搜索樹?持增刪查，但是不?持修改，修改key就破壞搜索樹結(jié)構(gòu)了。
場景1：?區(qū)??值守?庫，?區(qū)?庫買了?位的業(yè)主?才能進(jìn)?區(qū)，那么物業(yè)會(huì)把買了?位的業(yè)主的?牌號錄?后臺系統(tǒng)，?輛進(jìn)?時(shí)掃描?牌在不在系統(tǒng)中，在則抬桿，不在則提??本?區(qū)?輛，?法進(jìn)?。
場景2：檢查?篇英??章單詞拼寫是否正確，將詞庫中所有單詞放??叉搜索樹，讀取?章中的單詞，查找是否在?叉搜索樹中，不在則波浪線標(biāo)紅提?。
key/value搜索場景：
每?個(gè)關(guān)鍵碼key，都有與之對應(yīng)的值value，value可以任意類型對象。樹的結(jié)構(gòu)中(結(jié)點(diǎn))除了需要存儲key還要存儲對應(yīng)的value，增/刪/查還是以key為關(guān)鍵字??叉搜索樹的規(guī)則進(jìn)??較，可以快速查找到key對應(yīng)的value。key/value的搜索場景實(shí)現(xiàn)的?叉樹搜索樹?持修改，但是不?持修改key，修改key破壞搜索樹結(jié)構(gòu)了，可以修改value。
場景1：簡單中英互譯字典，樹的結(jié)構(gòu)中(結(jié)點(diǎn))存儲key(英?)和vlaue(中?)，搜索時(shí)輸?英?，則同時(shí)查找到了英?對應(yīng)的中?。
場景2：商場??值守?庫，??進(jìn)場時(shí)掃描?牌，記錄?牌和?場時(shí)間，出?離場時(shí)，掃描?牌，查找?場時(shí)間，?當(dāng)前時(shí)間-?場時(shí)間計(jì)算出停?時(shí)?，計(jì)算出停?費(fèi)?，繳費(fèi)后抬桿，?輛離場。
場景3：統(tǒng)計(jì)?篇?章中單詞出現(xiàn)的次數(shù)，讀取?個(gè)單詞，查找單詞是否存在，不存在這個(gè)說明第?次出現(xiàn)，（單詞，1），單詞存在，則++單詞對應(yīng)的次數(shù)。
六、key/value?叉搜索樹代碼實(shí)現(xiàn)
namespace key_value
{
template
struct BSTNode
{
K _key;
V _value;
BSTNode
BSTNode
BSTNode(const K& key, const V& value)
:_key(key)
, _value(value)
, _left(nullptr)
, _right(nullptr)
{}
};
// Binary Search Tree
// Key/value
template
class BSTree
{
//typedef BSTNode
using Node = BSTNode
public:
// 強(qiáng)制生成構(gòu)造
BSTree() = default;
BSTree(const BSTree& t)
{
_root = Copy(t._root);
}
BSTree& operator=(BSTree tmp)
{
swap(_root, tmp._root);
return *this;
}
~BSTree()
{
Destroy(_root);
_root = nullptr;
}
bool Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
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, value);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
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;
}
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->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
// 右為空
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
// 左右都不為空
// 右子樹最左節(jié)點(diǎn)
Node* replaceParent = cur;
Node* replace = cur->_right;
while (replace->_left)
{
replaceParent = replace;
replace = replace->_left;
}
cur->_key = replace->_key;
if (replaceParent->_left == replace)
replaceParent->_left = replace->_right;
else
replaceParent->_right = replace->_right;
delete replace;
}
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);
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newRoot = new Node(root->_key, root->_value);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
private:
Node* _root = nullptr;
};
}
柚子快報(bào)邀請碼778899分享：java 【C++】二叉搜索樹
相關(guān)鏈接
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Kikuu全球購
