二叉搜索樹BST

概念

二叉搜索樹又稱二叉排序樹，它可以是一棵空樹，或者是具有以下性質(zhì)的二叉樹：若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值；若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值；它的左右子樹也分別為二叉搜索樹。

即當(dāng)我們按中序來遍歷輸出這棵樹的節(jié)點(diǎn)時(shí)，是有序的，按從小到大的順序。

實(shí)現(xiàn)的細(xì)節(jié)

搜索key的過程Find/FindR

a.從根開始查找，val比根節(jié)點(diǎn)值大則往右邊走查找，比根節(jié)點(diǎn)值小則往左邊走查找;
b.最多查找高度次，走到到空，還沒找到，說明這個(gè)值不存在。

//普通版本--用循環(huá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;
}//用遞歸來解決
public:
bool FindR(const K& key)
{return _FindR(_root, key);
}
private:
bool _FindR(Node* root, const K& key)
{if (root == nullptr)return false;if (key > root->_key)return _FindR(root->_right, key);else if (key < root->_key)return _FindR(root->_left, key);elsereturn true;
}

插入key的過程Insert/InsertR

需要考慮以下場景：

a.樹為空，則直接新增節(jié)點(diǎn)new，賦值給root指針;
b.樹不為空，按二叉搜索樹性質(zhì)查找插入位置，即與根節(jié)點(diǎn)比較，比根節(jié)點(diǎn)的值小，往左查找；比根節(jié)點(diǎn)的值大，往右查找，找到該位置后插入新節(jié)點(diǎn)。這個(gè)過程需要用到2個(gè)指針，一個(gè)為判斷當(dāng)前值與key孰大孰小的cur指針，一個(gè)是保存cur的父節(jié)點(diǎn)的parent指針，最終要把key值節(jié)點(diǎn)插入在parent的左/右節(jié)點(diǎn)。【注意：此處的二叉搜索樹無相同值】

bool Insert(const K& key)
{//如果根節(jié)點(diǎn)為空，直接插入這個(gè)值if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == key){//如果二叉搜索樹中已經(jīng)有一樣的值了，插入失敗return false;}else if (key > cur->_key){parent = cur;//與根節(jié)點(diǎn)比較，比根節(jié)點(diǎn)的值小，往左走；比根節(jié)點(diǎn)的值大，往右走cur = cur->_right;}else{parent = cur;cur = cur->_left;}}cur = new Node(key);//與根節(jié)點(diǎn)比較，比根節(jié)點(diǎn)的值大，就鏈接在右邊if (key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;
}public:bool InsertR(const K& key){return _InsertR(_root, key);}
private:
bool _InsertR(Node*& root, const K& key){//方式1 bool _InsertR(Node* root, const K& key)//if (key > root->_key)//{//	if (root->_right == nullptr)//	{//		root->_right = new Node(key);//		return true;//	}//	else//		return _InsertR(root->_right, key);//}//else if (key < root->_key)//{//	if (root->_left == nullptr)//	{//		root->_left = new Node(key);//		return true;//	}//	else//		return _InsertR(root->_left, key);//}//else//	return false;//方式2 bool _InsertR(Node*& root, const K& key)if (root == nullptr){root = new Node(key);return true;}if (key > root->_key)return _InsertR(root->_right, key);else if (key < root->_key)return _InsertR(root->_left, key);elsereturn false;}

這里的二叉搜索樹無法保證左右平衡。

刪除的過程Erase/EraseR

首先查找元素是否在二叉搜索樹中，如果不存在，則返回, 否則要?jiǎng)h除的結(jié)點(diǎn)可能分下面四種情況：

1. 要?jiǎng)h除的結(jié)點(diǎn)無孩子結(jié)點(diǎn)–直接刪除，其父節(jié)點(diǎn)原來指向它的變成指向空
2. 要?jiǎng)h除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)–托孤，讓該節(jié)點(diǎn)的父節(jié)點(diǎn)直接指向該節(jié)點(diǎn)的孩子節(jié)點(diǎn)
3. 要?jiǎng)h除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)–托孤，讓該節(jié)點(diǎn)的父節(jié)點(diǎn)直接指向該節(jié)點(diǎn)的孩子節(jié)點(diǎn)
4. 要?jiǎng)h除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)–替換，找左子樹的最大和右子樹的最小

看起來待刪除節(jié)點(diǎn)的處理方式有4種情況，實(shí)際上情況1可以與情況2或者3合并起來，因此真正的刪除過程如下：

1. 刪除該結(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的父結(jié)點(diǎn)指向被刪除節(jié)點(diǎn)的左孩子結(jié)點(diǎn)–直接刪除
2. 刪除該結(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的父結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的右孩子結(jié)點(diǎn)–直接刪除
3. 在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小)，用它的值填補(bǔ)到被刪除節(jié)點(diǎn)中，再來處理該結(jié)點(diǎn)的刪除問題–替換法刪除

//普通版本
bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){//與根節(jié)點(diǎn)比較，比根節(jié)點(diǎn)的值大，往右走；比根節(jié)點(diǎn)的值小，往左走if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{//能走到這，就說明找到了要?jiǎng)h除的這個(gè)節(jié)點(diǎn)，要?jiǎng)h除的節(jié)點(diǎn)為cur//情況1：左子節(jié)點(diǎn)為空，右子節(jié)點(diǎn)不為空if (cur->_left == nullptr){//需要特殊處理根節(jié)點(diǎn)，因?yàn)楦?jié)點(diǎn)無父節(jié)點(diǎn)if (cur == _root){_root = cur->_right;}else{//cur為parent的左子節(jié)點(diǎn)，cur的子節(jié)點(diǎn)就得繼承parent的左子節(jié)點(diǎn)if (parent->_left == cur){parent->_left = cur->_right;}//cur為parent的右子節(jié)點(diǎn)，cur的子節(jié)點(diǎn)就得繼承parent的右子節(jié)點(diǎn)else{parent->_right = cur->_right;}}delete cur;}//情況2：左子節(jié)點(diǎn)不為空，右子節(jié)點(diǎn)為空else if (cur->_right == nullptr){//需要特殊處理根節(jié)點(diǎn)，因?yàn)楦?jié)點(diǎn)無父節(jié)點(diǎn)if (cur == _root){_root = cur->_left;}else{//cur為parent的左子節(jié)點(diǎn)，cur的子節(jié)點(diǎn)就得繼承parent的左子節(jié)點(diǎn)if (parent->_left == cur){parent->_left = cur->_left;}//cur為parent的右子節(jié)點(diǎn)，cur的子節(jié)點(diǎn)就得繼承parent的右子節(jié)點(diǎn)else{parent->_right = cur->_left;}}delete cur;}//情況3：左右子節(jié)點(diǎn)均不為空else{//在cur的右子樹中尋找中序的第一個(gè)結(jié)點(diǎn)Node* parent = cur;Node* minRight = cur->_right;//此處前置條件是cur的左右子樹均不為空while (minRight->_left){parent = minRight;minRight = minRight->_left;}//交換cur和minRight的值cur->_key = minRight->_key;//刪除minRightif (minRight == parent->_left)parent->_left = minRight->_right;elseparent->_right = minRight->_right;delete minRight;}return true;}}//走到這，說明沒找到return false;
}//遞歸版本
public:bool EraseR(const K& key){return _EraseR(_root, key);}
private:bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (key > root->_key){return _EraseR(root->_right, key);}else if (key < root->_key){return _EraseR(root->_left, key);}else{Node* del = root;//相等就開始刪除if (root->_left == nullptr){root = root->_right;}//情況2：左子節(jié)點(diǎn)不為空，右子節(jié)點(diǎn)為空else if (root->_right == nullptr){				root = root->_left;}//情況3：左右子節(jié)點(diǎn)均不為空else{Node* minRight = root->_right;while (minRight->left){minRight = minRight->left;}swap(root->_key, minRight->_key);// 轉(zhuǎn)換成在子樹中去刪除節(jié)點(diǎn)return _EraseR(root->_right, key);}delete del;return true; }}

中序遍歷InOrder

在不暴露根節(jié)點(diǎn)_root的情況下（比如寫一個(gè)函數(shù)getroot()等讓用戶獲取），套一層函數(shù)接口就直接在類內(nèi)使用這個(gè)_root，實(shí)現(xiàn)中序遍歷

void InOrder()
{_InOrder(_root);std::cout << std::endl;
}
private:
void _InOrder(Node* root)
{//中序：左根右if (root == nullptr) return;_InOrder(root->_left);std::cout << root->_key << " ";_InOrder(root->_right);
}

注意：二叉搜素樹不支持改，對于二叉搜索樹而言，僅僅修改對應(yīng)節(jié)點(diǎn)的值，極有可能破壞原結(jié)構(gòu)，所以改=刪除+插入

構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、賦值構(gòu)造函數(shù)、析構(gòu)函數(shù)

public:BSTree():_root(nullptr){}BSTree(const BSTree<K>& t){_root = Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}~BSTree(){Destory(_root);_root = nullptr;}
private:void Destory(Node* root){if (root == nullptr)return;//按后序來刪除Destory(root->_left);Destory(root->_right);delete root;}Node* Copy(Node* root){if (root == nullptr)return nullptr;//前序遍歷，再遞歸拷貝Node* newnode = new Node(root->_key);newnode->_left = Copy(root->_left);newnode->_right = Copy(root->_right);return newnode;}

應(yīng)用場景

K模型–判斷某個(gè)key在不在的場景；KV模型–通過key查找或修改value

1. K模型：K模型即只有key作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲Key即可，關(guān)鍵碼即為需要搜索到的值。

比如：給一個(gè)單詞word，判斷該單詞是否拼寫正確，具體方式如下：以詞庫中所有單詞集合中的每個(gè)單詞作為key，構(gòu)建一棵二叉搜索樹在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯(cuò)誤。其他場景：檢查單詞拼寫是否正確/車庫出入系統(tǒng)/宿舍樓門禁系統(tǒng)

2. KV模型：每一個(gè)關(guān)鍵碼key，都有與之對應(yīng)的值Value，即<Key, Value>的鍵值對。該種方式在現(xiàn)實(shí)生活中非常常見：

比如英漢詞典就是英文與中文的對應(yīng)關(guān)系，通過英文可以快速找到與其對應(yīng)的中文，英文單詞與其對應(yīng)的中文<word, chinese>就構(gòu)成一種鍵值對；再比如統(tǒng)計(jì)單詞次數(shù)，統(tǒng)計(jì)成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出現(xiàn)次數(shù)就是<word, count>就構(gòu)成一種鍵值對。其他場景：英漢互譯/學(xué)號學(xué)生對應(yīng)

性能分析

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

對有n個(gè)結(jié)點(diǎn)的二叉搜索樹，若每個(gè)元素查找的概率相等，則二叉搜索樹平均查找長度是結(jié)點(diǎn)在二叉搜索樹的深度的函數(shù)，即結(jié)點(diǎn)越深，則比較次數(shù)越多。
但對于同一個(gè)關(guān)鍵碼集合，如果各關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹：

• 最優(yōu)情況下，二叉搜索樹為完全二叉樹(或者接近完全二叉樹)，其平均比較次數(shù)為：$lo{g}_{2}N$
• 最差情況下，二叉搜索樹退化為單支樹(或者類似單支)，其平均比較次數(shù)為：$\frac{N}{2}$

但是如果退化成單支樹，二叉搜索樹的性能就很差，后續(xù)引入紅黑樹和AVL樹來解決。