二叉搜索樹 – C++ 實現
二叉搜索樹 – C++ 實現
📌 概述 Overview
二叉查找樹（英語：Binary Search Tree, 後文中簡稱 BST）, 也稱為二叉搜索樹、有序二叉樹（ordered binary tree）或排序二叉樹（sorted binary tree）, 是在 20 世紀 60 年代為解決標記數據的高效存儲問題而設計的, 由 Conway Berners-Lee 和 David Wheeler 發明.
具體指的是一棵空樹或者具有下列性質的二叉樹:
- 若任意節點的左子樹不空, 則左子樹上所有節點的值均小於它的根節點的值；
- 若任意節點的右子樹不空, 則右子樹上所有節點的值均大於它的根節點的值；
- 任意節點的左、右子樹也分別為二叉查找樹；
簡單來說, 二叉搜索樹中的每一個節點都滿足: 左子樹中的所有元素均小於該節點元素; 右子樹中的所有元素均大於該節點元素. \(左子樹元素 \le 本節點元素 \le 右子樹元素\). 左小右大.
這種結構上的設計使得 BST 可以以二分查找思路實現 \(\Omega(\log n)\) （不是大o, 而是下限在logn）級別的快速增, 刪, 查等操作, 因為在樹中的每一步操作都能排除一半的元素. 完成一顆二叉搜索樹的建立之後, 我們還可以以中序遍歷的方式得到排序後的序列, 這也是二叉搜索樹被稱為排序二叉樹的原因.
需要注意的是, 二叉搜索樹的效率與在建立時輸入的元素順序有很大的關係. 在最壞情況下, 二叉搜索樹會退化成鏈表. 樹層數大大增加使得查找等操作需要消耗更多的時間）此時, 需要對樹進行額外的優化 – 平衡, 來保證高效的運行效率. 在本文中我們不作討論, 本文僅介紹樸素的二叉搜索樹.
如果看完之後還是不太理解的話, 可以看看這個美國舊金山大學CS做的一個演算法可視化. Binary Search Tree Visualization (usfca.edu) 在這個網站上詳細地看到 BST 每一步的操作. 做的很好, 不妨去玩玩!
🧩 基本操作 Operations
和其他的數據結構類似, 二叉搜索樹也有著這樣的幾個基本操作.
🔍 搜索 Search
⤵️ 根據元素值直接搜索節點
假設要搜素的節點的元素值為 item.
那麼搜索就是要從數的根節點 root 開始, 逐節點遍歷該樹.
若當前掃描到的節點的元素值小於 item, 則往右走; 若元素值大於 item 則左走. 直到掃描到目標節點或遇到 nil 節點時（未找到該元素）停止搜索, 返回結果.
具體的程式碼實現如下.
void insert(const int item)
{
TreeNode *scan = root;
TreeNode *prev = root;
while (scan != nullptr)
{
prev = scan;
scan = item < scan->data ? scan->left : scan->right;
}
TreeNode *newNode = new TreeNode(item);
if (root)
{
(item < prev->data ? prev->left : prev->right) = newNode;
newNode->parent = prev;
}
else
{
root = newNode;
}
return;
}
↔️ 找節點的前驅/後繼
前驅節點指的是樹在中序遍歷的序列中, 目標結點的前一個結點(類似鏈表中前驅的定義).（當目標結點為第一個結點是返回nil）
e.g. 如一顆樹的中序遍歷序列為: {1, 2, 3, 4, 5}, 那麼元素值為 2 的節點的前驅就是元素值為 1 的節點; 元素值為 1 的節點的前驅就是 nil.
在BST中, 因為BST 的定義, 其中序遍歷序列就是樹中所有元素按元素值大小排序而輸出的序列.
因此, 前驅節點也可以被定義成所有小於目標元素的所有元素中的最大值 \(\max( \{item\ |\ item \in tree \and item < target\})\).
根據此定義我們來完成搜索前驅節點的演算法.
由 BST 的定義我們可以得到一個結論,
設有一個節點 node, 在中序遍歷的序列中:
如果 node 是父節點的左節點
左子樹中的所有節點 < node < 父節點
如果 node 是父節點的右節點
父節點 < node < 左子樹中的所有節點
(光這樣子講可能有點抽象, 想像一下把一顆 BST 拍扁, 得到的序列就是中序遍歷的序列, 容易得到以上結論)
基於上面的結論, 請考慮以下這兩種 case.
-
case 01/ 有左子樹. 所有有可能的 node 的均在左子樹
那就意味著, 我們只需要找到 node 左子樹中最大的那個節點即可.
-
case 02/ 無左子樹. 需要一直向祖先追溯. 直到找到第一個比 node 小的節點.
第一個找到的節點就是在中序遍歷中最接近 node 節點的節點. 也就是 node 的前驅結點.
若找不到, 就說明 node 就是中序遍歷中最小的元素, 返回 nil 節點.
具體程式碼實現如下.
TreeNode *p_pred(int item)
{
TreeNode *itemNode = p_find(item);
if (!itemNode)
return nullptr;
if (itemNode->left)
{
return p_max(itemNode->left);
}
else
{
TreeNode *scan = itemNode->parent;
while (scan && scan->left == itemNode)
{
scan = scan->parent;
itemNode = itemNode->parent;
}
return scan;
}
}
while 退出時, 變數滿足: scan == nullptr.(無前驅) 或 node != prev.left ( 等價於 node->data < item) (有前驅)
對應上文提到的兩種 case.
查找後繼同理, 程式碼也大差不差. 這裡不再贅述. 直接給出程式碼.
TreeNode *p_succ(int item)
{
TreeNode *itemNode = p_find(item);
if (!itemNode)
return nullptr;
if (itemNode->right)
{
return p_min(itemNode->right);
}
else
{
TreeNode *scan = itemNode->parent;
while (scan && scan->right == itemNode)
{
scan = scan->parent;
itemNode = itemNode->parent;
}
return scan;
}
}
↪️ 插入 Insertion
本文給出的是迭代的實現方法, 遞歸的方法應該很好想, 依據 BST 的定義來寫就好了, 這裡就省略不寫了(偷懶 :p)
依據二叉搜索樹的定義查找.
待插入的元素比當前掃描到的元素小就繼續掃描左子樹, 反之則繼續掃描右子樹, 直到掃描到nil節點就插入待插入的元素.
給出程式碼如下.
注意樹為空的時候需要特殊處理哈.
void insert(const int item)
{
TreeNode *scan = root;
TreeNode *prev = root;
while (scan != nullptr)
{
prev = scan;
scan = item < scan->data ? scan->left : scan->right;
}
TreeNode *newNode = new TreeNode(item);
if (root)
{
(item < prev->data ? prev->left : prev->right) = newNode;
newNode->parent = prev;
}
else
{
root = newNode;
}
return;
}
⛔ 刪除 Deletion / Removal
刪除的情況就相對比較多比較複雜了. BST 的刪除需要考慮以下三種情況:
-
左右子樹皆空.
刪除節點是葉節點, 將對應的節點置為 nil.
-
左右子樹中只有其中一個非空.
將節點的非空子樹重新鏈接到節點的父節點即可.
-
左右子樹均非空.
這種情況是最棘手的情況. 我們做詳細討論.
情況三很麻煩.
如果也像前兩種情況直接刪除掉節點, 會出現兩個無父節點的子樹, 和原節點對應的父節點. 如果這個父節點原本還有兩個子樹的話, 那就意味著我們要面對三個子樹, 和兩個待鏈接的指針, 就必須要合併其中兩個子樹, 這會使問題會變得相當困難.
我們能不能把第三種情況也轉換成前兩種情況呢?
我們再仔細揣摩一下前驅和後繼的定義.
也許你已經發現了這個性質, BST 中某個節點的前驅和後繼一定是滿足 case1 或 case2 的. (可以用反證法和前驅後繼定義證明. 如果是case3 那麼他就不是前驅或後繼, 因為還有比該節點更大/小的節點, 不符合定義中的”最”)
要是不可以直接刪除, 可以做到用替換節點做到等效的刪除嗎? 怎樣替換才可以保持 BST 的性質呢?
保持 BST 結構上的性質 也可以說是 使樹的中序遍歷序列結果不變.
我們想到可以用這個節點的前驅或後繼來替換掉這個待刪除節點. (在後文程式碼中使用後繼, 兩個方案都可以實現, 留給讀者自行思考~)
因為待刪除節點是不重要的, 替換之後中序遍歷序列是不變的! 此後, 只需要替換之後將多出來的一個前驅/後繼刪除掉即可.
也就是說, 如此操作之後, 我們就將刪除 case3 (待刪除節點)的情況轉換為刪除 case1/2 (刪除多餘前驅/後繼)的情況了!
具體地說, 用上之前找後繼的程式碼. 用後繼節點元素值替換待刪除節點的元素值. 然後刪掉多餘的節點.
程式碼見下.
這個是直接使用指針的版本, 會啰嗦一點, 因為還需要根據 delNode 節點反推這個節點的指針(二級指針). 如果用上引用的話會程式碼簡潔不少.
public:
void remove(const int item)
{
TreeNode *delNode = p_find(item);
if (delNode)
p_remove(delNode);
}
private:
void p_remove(TreeNode *delNode)
{
if (delNode->isLeaf()) // case1
{
if (delNode->parent)
{
// judge which pointer of node to modify
if (delNode == delNode->parent->left)
{
delNode->parent->left = nullptr;
}
else
{
delNode->parent->right = nullptr;
}
}
else // when root == delNode;
{
root = nullptr;
}
delete delNode;
}
else if (delNode->left == nullptr) // case 2
{
// basically same as above
if (delNode->parent)
{
if (delNode == delNode->parent->left)
{
delNode->parent->left = delNode->right;
}
else
{
delNode->parent->right = delNode->right;
}
}
else // root == delNode;
{
root = delNode->right;
root->parent = nullptr;
}
delete delNode;
}
else if (delNode->right == nullptr)
{
// same as above
if (delNode->parent)
{
if (delNode == delNode->parent->left)
{
delNode->parent->left = delNode->left;
}
else
{
delNode->parent->right = delNode->left;
}
}
else // root == delNode;
{
root = delNode->left;
root->parent = nullptr;
}
delete delNode;
}
else
{
// case3
TreeNode *succNode = p_succ(delNode);
delNode->data = succNode->data;
p_remove(succNode);
}
}
這個是引用的版本.
public:
void remove_ref(const int item)
{
TreeNode *&delNode = p_find_ref(item);
if (delNode)
p_remove_ref(delNode);
}
private:
void p_remove_ref(TreeNode *&delNodeRef)
{
TreeNode *delPtr = delNodeRef;
if (delNodeRef->isLeaf())
{
delNodeRef = nullptr;
}
else if (!delNodeRef->left || !delNodeRef->right)
{
TreeNode *subTree = max(delNodeRef->right, delNodeRef->left);
if (root == delNodeRef)
subTree->parent = nullptr;
delNodeRef = subTree;
}
else
{
TreeNode *succNode = p_succ(delNodeRef);
delNodeRef->data = succNode->data;
p_remove(succNode);
}
delete delPtr;
}
如果還是不太理解的話, 可以看看這個美國舊金山大學 CS 做的一個演算法可視化. Binary Search Tree Visualization (usfca.edu) 在這個網站上詳細地看到 BST 中每一步的操作. 做的很好, 不妨去玩玩!
📝 程式碼實現 Implement
下面的是 BST 類的完整實現.
class TreeNode
{
public:
TreeNode(int m_data) : data(m_data) {}
int data;
TreeNode *left = nullptr;
TreeNode *right = nullptr;
TreeNode *parent = nullptr;
bool isLeaf()
{
return left == nullptr && right == nullptr;
}
};
class BinarySearchTree
{
public:
void insert(const int item)
{
TreeNode *scan = root;
TreeNode *prev = root;
while (scan != nullptr)
{
prev = scan;
scan = item < scan->data ? scan->left : scan->right;
}
TreeNode *newNode = new TreeNode(item);
if (root)
{
(item < prev->data ? prev->left : prev->right) = newNode;
newNode->parent = prev;
}
else
{
root = newNode;
}
return;
}
void remove(const int item)
{
TreeNode *delNode = p_find(item);
if (delNode)
p_remove(delNode);
}
void remove_ref(const int item)
{
TreeNode *&delNode = p_find_ref(item);
if (delNode)
p_remove_ref(delNode);
}
int find(const int item)
{
TreeNode *node = p_find(item);
return node ? node->data : -1;
}
int pred(const int item)
{
TreeNode *node = p_pred(item);
return node ? node->data : -1;
}
int succ(const int item)
{
TreeNode *node = p_succ(item);
return node ? node->data : -1;
}
void print()
{
p_printAll(root);
putchar('\n');
}
private:
TreeNode *root = nullptr;
const TreeNode *empty = nullptr;
void p_printAll(TreeNode *node)
{
if (!node)
return;
p_printAll(node->left);
printf("%d ", node->data);
p_printAll(node->right);
}
void p_remove(TreeNode *delNode)
{
if (delNode->isLeaf()) // case1
{
if (delNode->parent)
{
// judge which pointer of node to modify
if (delNode == delNode->parent->left)
{
delNode->parent->left = nullptr;
}
else
{
delNode->parent->right = nullptr;
}
}
else // when root == delNode;
{
root = nullptr;
}
delete delNode;
}
else if (delNode->left == nullptr) // case 2
{
// basically same as above
if (delNode->parent)
{
if (delNode == delNode->parent->left)
{
delNode->parent->left = delNode->right;
}
else
{
delNode->parent->right = delNode->right;
}
}
else // root == delNode;
{
root = delNode->right;
root->parent = nullptr;
}
delete delNode;
}
else if (delNode->right == nullptr)
{
// same as above
if (delNode->parent)
{
if (delNode == delNode->parent->left)
{
delNode->parent->left = delNode->left;
}
else
{
delNode->parent->right = delNode->left;
}
}
else // root == delNode;
{
root = delNode->left;
root->parent = nullptr;
}
delete delNode;
}
else
{
// case3
TreeNode *succNode = p_succ(delNode);
delNode->data = succNode->data;
p_remove(succNode);
}
}
void p_remove_ref(TreeNode *&delNodeRef)
{
TreeNode *delPtr = delNodeRef;
if (delNodeRef->isLeaf())
{
delNodeRef = nullptr;
}
else if (!delNodeRef->left || !delNodeRef->right)
{
TreeNode *subTree = max(delNodeRef->right, delNodeRef->left);
if (root == delNodeRef)
subTree->parent = nullptr;
delNodeRef = subTree;
}
else
{
TreeNode *succNode = p_succ(delNodeRef);
delNodeRef->data = succNode->data;
p_remove(succNode);
}
delete delPtr;
}
TreeNode *p_find(const int item)
{
TreeNode *scan = root;
while (scan != nullptr && scan->data != item)
{
scan = item < scan->data ? scan->left : scan->right;
}
return scan;
}
TreeNode *&p_find_ref(const int item)
{
TreeNode *scan = root;
TreeNode *prev = nullptr;
while (scan != nullptr && scan->data != item)
{
prev = scan;
scan = item < scan->data ? scan->left : scan->right;
}
if (root->data == item) return root;
if (!scan) return (TreeNode *&) empty;
return prev->left == scan ? (*prev).left : (*prev).right;
}
TreeNode *p_pred(int item)
{
TreeNode *itemNode = p_find(item);
if (!itemNode)
return nullptr;
if (itemNode->left)
{
return p_max(itemNode->left);
}
else
{
TreeNode *scan = itemNode->parent;
while (scan && scan->left == itemNode)
{
scan = scan->parent;
itemNode = itemNode->parent;
}
return scan;
}
}
TreeNode *p_succ(int item)
{
TreeNode *itemNode = p_find(item);
if (!itemNode)
return nullptr;
if (itemNode->right)
{
return p_min(itemNode->right);
}
else
{
TreeNode *scan = itemNode->parent;
while (scan && scan->right == itemNode)
{
scan = scan->parent;
itemNode = itemNode->parent;
}
return scan;
}
}
TreeNode *p_succ(TreeNode *itemNode)
{
if (itemNode->right)
{
return p_min(itemNode->right);
}
else
{
TreeNode *scan = itemNode->parent;
while (scan && scan->right == itemNode)
{
scan = scan->parent;
itemNode = itemNode->parent;
}
return scan;
}
}
TreeNode *p_max(TreeNode *node)
{
if (!node)
return nullptr;
while (node->right)
{
node = node->right;
}
return node;
}
TreeNode *p_min(TreeNode *node)
{
if (!node)
return nullptr;
while (node->left)
{
node = node->left;
}
return node;
}
};
📊 結構分析 Analysis
總結上文提到的所有操作, 對 BST 的每一步操作都是向樹的深處再進一層, 而每一次進入一顆子樹都意味著篩選掉了當前樹中的一半節點, 對剩下來的一半節點繼續操作.(二分思想)
由此, 我們可以容易的的得到一個結論: BST 中的最大查找次數取決於 BST 的最大深度, 即樹高. 在最好情況下, 一個有著 n 個節點的樹, 他的深度最小為 \(\log_2 n\). 此時, BST 可以達到最高效率.
但如果不是最好的情況呢? 很多時候 BST 生成的樹不會是理想的, 常常會有一些不滿的子樹, 產生額外的深度. 此時, BST 就會退化成更低級的數據結構. 也就是說, 這個數據結構的時間複雜度下限為 \(\Omega(\log n)\), 而其上限仍然為 O(n), 與數組和鏈表差不多. (甚至插入刪除還不如鏈表的 O(1).)
具體來說, 實際上, BST 的結構與插入元素的順序有著很大的關係. 舉個例子, 同一組數列的不同排列可以形成不同的樹. 雖然他們序列中元素都是相同的, 但是生成的樹的結構卻不盡相同. 當插入元素的順序已然有序的時候. 根據在基本操作中插入操作的實現. 此時, 在形成的樹中, 元素只會在樹的一側堆積. 也就是說, 這個時候 BST 會退化成一個單鏈表. 使得操作效率大大降低.
那麼怎麼才能讓 BST 的深度盡量的小呢? 具體地說, 是否有解決方案可以讓 BST 保證每次的插入都可以調整成最優的結構, 不再退化成鏈表?
是有的! 平衡樹的提出解決了 BST 的退化問題. 通過保證樹中每一個節點的左右子樹高度儘可能相同. 可以使整顆樹的深度近似等於前文提到的最小深度 \(\log_2 n\).
本文中不再作詳細討論, 感興趣可以自行搜索相關資訊.
🗃️ 參考資料 Reference
Wikipedia – 二叉搜索樹 – 維基百科, 自由的百科全書 (wikipedia.org)
Wikipedia – Binary search tree – Wikipedia
OI-Wiki – AVL 樹 – OI Wiki (oi-wiki.org)
