作者按：因為教程所示圖片使用的是 github 倉庫圖片胚嘲，網(wǎng)速過慢的朋友請移步《二叉搜索樹的實現(xiàn)與常見用法》原文地址滚澜。更歡迎來我的小站看更多原創(chuàng)內(nèi)容：godbmw.com界赔，進(jìn)行“姿勢”交流 ?(?*)
1. 為什么需要二叉搜索樹佑颇？
選擇數(shù)據(jù)結(jié)構(gòu)的核心在于解決問題牺氨，而不是為了使用而使用狡耻。
由于二叉搜索樹的定義和特性墩剖，它可以高效解決以下問題：
- 查找問題：二分查找
- 高級結(jié)構(gòu)：字典結(jié)構(gòu)實現(xiàn)
- 數(shù)據(jù)變動：節(jié)點的插入、刪除
- 遍歷問題：前序夷狰、中序涛碑、后序和層次遍歷
- 數(shù)值運(yùn)算：
ceil、floor孵淘、找到第 n 大的元素蒲障、找到指定元素在排序好的數(shù)組的位置 等等
值得一提的是，除了遍歷算法瘫证，上述各種問題的算法時間復(fù)雜度都是 :
2. 二叉搜索樹的定義和性質(zhì)
二叉搜索樹是一顆空樹揉阎，或者具有以下性質(zhì)的二叉樹：
- 若任意節(jié)點的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值
- 若任意節(jié)點的右子樹不空背捌，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值
- 任意節(jié)點的左毙籽、右子樹也分別為二叉查找樹
- 沒有鍵值相等的節(jié)點
需要注意的是，二叉搜索樹不一定是一顆完全二叉樹毡庆，因此坑赡，二叉搜索樹不能用數(shù)組來存儲。
3. 二叉搜索樹的實現(xiàn)
第 3 部分實現(xiàn)的測試代碼地址：https://gist.github.com/dongyuanxin/d0803a8821c6797e9ce8522a676cf44b么抗。
這是 Github 的 GIST毅否，請自備梯子。
3.1 樹結(jié)構(gòu)實現(xiàn)
借助struct和指針模擬樹的結(jié)構(gòu)蝇刀，并且將其封裝到BST這個類之中：
// BST.h
// Created by godbmw.com on 2018/9/27.
//
#ifndef BINARYSEARCH_BST_H
#define BINARYSEARCH_BST_H
#include <iostream>
#include <queue>
using namespace std;
template <typename Key, typename Value>
class BST {
private:
struct Node {
Key key;
Value value;
Node *left;
Node *right;
Node(Key key, Value value) {
this->key = key;
this->value = value;
this->left = NULL;
this->right = NULL;
}
Node(Node* node) {
this->key = node->key;
this->value = node->value;
this->left = node->left;
this->right = node->right;
}
};
Node *root;
int count;
public:
BST() {
this->root = NULL;
this->count = 0;
}
~BST() {
this->destroy(this->root);
}
int size() {
return this->count;
}
bool isEmpty() {
return this->root == NULL;
}
};
#endif //BINARYSEARCH_BST_H
3.2 實現(xiàn)節(jié)點插入
插入采取遞歸的寫法螟加，思路如下：
- 遞歸到底層情況：新建節(jié)點，并且返回
- 非底層情況：如果當(dāng)前鍵等于插入鍵吞琐，則更新當(dāng)前節(jié)點的值捆探；小于，進(jìn)入當(dāng)前節(jié)點的左子樹站粟；大于黍图，進(jìn)入當(dāng)前節(jié)點的右子樹。
private:
Node* insert(Node* node, Key key, Value value) {
if(node == NULL) {
count++;
return new Node(key, value);
}
if(key == node->key) {
node->value = value;
} else if( key < node->key) {
node->left = insert(node->left, key, value);
} else {
node->right = insert(node->right, key, value);
}
return node;
}
public:
void insert(Key key, Value value) {
this->root = this->insert(this->root, key, value);
}
3.3 實現(xiàn)節(jié)點的查找
查找包含 2 個函數(shù)：contain和search奴烙。前者返回布爾型助被，表示樹中是否有這個節(jié)點；后者返回指針類型缸沃，表示樹中節(jié)點對應(yīng)的值恰起。
search為什么返回值的指針類型呢：
- 如果要查找的節(jié)點不存在修械，指針可以直接返回
NULL趾牧。 - 如果返回
Node*，就破壞了類的封裝性肯污。原則上翘单，內(nèi)部數(shù)據(jù)結(jié)構(gòu)不對外展示吨枉。 - 如果查找的節(jié)點存在，返回去鍵對應(yīng)的值哄芜，用戶可以修改貌亭，并不影響樹結(jié)構(gòu)。
private:
bool contain(Node* node, Key key) {
if(node == NULL) {
return false;
}
if(key == node->key) {
return true;
} else if(key < node->key) {
return contain(node->left, key);
} else {
return contain(node->right, key);
}
}
Value* search(Node* node, Key key) {
if(node == NULL) {
return NULL;
}
if(key == node->key) {
return &(node->value);
} else if (key < node->key) {
return search(node->left, key);
} else {
return search(node->right, key);
}
}
public:
bool contain(Key key) {
return this->contain(this->root, key);
}
// 注意返回值類型
Value* search(Key key) {
return this->search(this->root, key);
}
3.4 遍歷實現(xiàn)
前序认臊、中序和后序遍歷的思路很簡單圃庭，根據(jù)定義，直接遞歸調(diào)用即可失晴。
對于層次遍歷剧腻，需要借助隊列queue這種數(shù)據(jù)結(jié)構(gòu)。思路如下：
- 首先涂屁，將根節(jié)點放入隊列
- 如果隊列不空书在，進(jìn)入循環(huán)
- 取出隊列頭部元素，輸出信息拆又。并將這個元素出隊
- 將這個元素非空的左右節(jié)點依次放入隊列
- 檢測隊列是否為空儒旬，不空的進(jìn)入第 3 步；空的話帖族，跳出循環(huán)栈源。
private:
void pre_order(Node* node) {
if(node != NULL) {
cout<<node->key<<endl;
pre_order(node->left);
pre_order(node->right);
}
}
void in_order(Node* node) {
if(node != NULL) {
in_order(node->left);
cout<<node->key<<endl;
in_order(node->right);
}
}
void post_order(Node *node) {
if(node != NULL) {
post_order(node->left);
post_order(node->right);
cout<<node->key<<endl;
}
}
void level_order(Node* node) {
if(node == NULL) {
return;
}
queue<Node*> q;
q.push(node);
while(!q.empty()) {
Node* node = q.front();
q.pop();
cout<< node->key <<endl;
if(node->left) {
q.push(node->left);
}
if(node->right) {
q.push(node->right);
}
}
}
public:
void pre_order() {
this->pre_order(this->root);
}
void in_order() {
this->in_order(this->root);
}
void post_order() {
this->post_order(this->root);
}
void level_order() {
this->level_order(this->root);
}
3.5 實現(xiàn)節(jié)點刪除
為了方便實現(xiàn)，首先封裝了獲取最小鍵值和最大鍵值的兩個方法：minimum和maximum竖般。
刪除節(jié)點的原理很簡單（忘了什么名字凉翻，是一個計算機(jī)科學(xué)家提出的），思路如下：
- 如果左節(jié)點為空捻激，刪除本節(jié)點制轰，返回右節(jié)點。
- 如果右節(jié)點為空胞谭，刪除本節(jié)點垃杖，返回左節(jié)點。
- 如果左右節(jié)點都為空丈屹，是 1 或者 2 的子情況调俘。
- 如果左右節(jié)點都不為空，找到當(dāng)前節(jié)點的右子樹的最小節(jié)點旺垒，并用這個最小節(jié)點替換本節(jié)點彩库。
為什么第 4 步這樣可以繼續(xù)保持二叉搜索樹的性質(zhì)呢卵酪？
顯然梗逮，右子樹的最小節(jié)點，能滿足小于右子樹的所有節(jié)點界斜，并且大于左子樹的全部節(jié)點竞漾。
如下圖所示眯搭，要刪除58這個節(jié)點窥翩，就應(yīng)該用59這個節(jié)點替換：
image
private:
// 尋找最小鍵值
Node* minimum(Node* node) {
if(node->left == NULL) {
return node;
}
return minimum(node->left);
}
// 尋找最大鍵值
Node* maximum(Node* node) {
if(node->right == NULL) {
return node;
}
return maximum(node->right);
}
Node* remove_min(Node* node) {
if(node->left == NULL) {
Node* right = node->right;
delete node;
count--;
return right;
}
node->left = remove_min(node->left);
return node;
}
Node* remove_max(Node* node) {
if(node->right == NULL) {
Node* left = node->left;
delete node;
count--;
return left;
}
node->right = remove_max(node->right);
return node;
}
// 刪除掉以node為根的二分搜索樹中鍵值為key的節(jié)點
// 返回刪除節(jié)點后新的二分搜索樹的根
Node* remove(Node* node, Key key) {
if(node == NULL) {
return NULL;
}
if(key < node->key) {
node->left = remove(node->left, key);
} else if(key > node->key){
node->right = remove(node->right, key);
} else {
// key == node->key
if(node->left == NULL) {
Node* right = node->right;
delete node;
count--;
return right;
}
if(node->right == NULL) {
Node *left = node->left;
delete node;
count--;
return left;
}
// node->right != NULL && node->left != NULL
Node* successor = new Node(minimum(node->right));
count++;
// "count --" in "function remove_min(node->right)"
successor->right = remove_min(node->right);
successor->left = node->left;
delete node;
count--;
return successor;
}
return node;
}
public:
// 尋找最小鍵值
Key* minimum() {
if(this->count == 0) return NULL;
Node* min_node = this->minimum(this->root);
return &(min_node->key);
}
// 尋找最大鍵值
Key* maximum() {
if(this->count == 0) return NULL;
Node* max_node = this->maximum(this->root);
return &(max_node->key);
}
void remove_min() {
if(this->root == NULL) {
return;
}
this->root = this->remove_min(this->root);
}
void remove_max() {
if(this->root == NULL) {
return;
}
this->root = this->remove_max(this->root);
}
void remove(Key key) {
this->root = remove(this->root, key);
}
3.6 數(shù)值運(yùn)算：floor和ceil
floor和ceil分別是地板和天花板的意思。在一個數(shù)組中鳞仙，對于指定元素n寇蚊，如果數(shù)組中存在n，那么n的兩個值就是它本身棍好；如果不存在仗岸，那么分別是距離最近的小于指定元素的值 和 距離最近的大于指定元素的值。
private:
Node* floor(Node* node, Key key) {
if(node == NULL) {
return NULL;
}
// key等于node->key：floor的結(jié)果就是node本身
if(node->key == key) {
return node;
}
// key小于node—>key：floor的結(jié)果肯定在node節(jié)點的左子樹
if(node->key > key) {
return floor(node->left, key);
}
// key大于node->key：右子樹可能存在比node->key大借笙，但是比key小的節(jié)點
// 如果存在上述情況爹梁，返回這個被選出來的節(jié)點
// 否則，函數(shù)最后返回node本身
Node* tmp = floor(node->right, key);
if(tmp != NULL) {
return tmp;
}
return node;
}
Node* ceil(Node* node, Key key) {
if(node == NULL) {
return NULL;
}
if(node->key == key) {
return node;
}
if(node->key < key) {
return ceil(node->right, key);
}
Node* tmp = ceil(node->left, key);
if(tmp != NULL) {
return tmp;
}
return node;
}
public:
Key* floor(Key key) {
Key* min_key = this->minimum();
if(this->isEmpty() || key < *min_key) {
return NULL;
}
// floor node
Node *node = floor(this->root, key);
return &(node->key);
}
Key* ceil(Key key) {
Key* max_key = this->maximum();
if(this->isEmpty() || key > *max_key) {
return NULL;
}
// ceil node
Node* node = ceil(this->root, key);
return &(node->key);
}
4. 代碼測試
第 3 部分實現(xiàn)的測試代碼地址：https://gist.github.com/dongyuanxin/759d16e1ce87913ad2f359d49d5f5016提澎。
這是 Github 的 GIST姚垃，請自備梯子。
5. 拓展延伸
考慮一種數(shù)據(jù)類型盼忌，如果是基本有序的一組數(shù)據(jù)积糯，一次insert進(jìn)入二叉搜索樹，那么谦纱，二叉搜索樹就退化為了鏈表看成。此時，上述所有操作的時間復(fù)雜度都會退化為 跨嘉。
為了避免這種情況川慌，就有了紅黑樹等數(shù)據(jù)結(jié)構(gòu)，來保證樹的平衡性：左右子樹的高度差小于等于 1祠乃。
6. 致謝
本篇博客是總結(jié)于慕課網(wǎng)的《學(xué)習(xí)算法思想 修煉編程內(nèi)功》的筆記梦重，強(qiáng)推強(qiáng)推強(qiáng)推。
