# 前言
強者朋友說: 演算法不熟情有可原, 但是資料結構不懂就是你的錯了。 如果對 Tree 資料結構不是很了解, 建議可以先參考 Tree 的簡介
# BST 概念解說
關於 BST 的解說, 可以從上面的連結去了解一下, 下面就直接用範例來解說
# 範例
# Node
下面會針對 Node class, 以及各個 method 做概念上的解說
# Node class
node 會有幾個 property
- $data 為此 node 持有的值
- $left 為 left child node
- $right 為 right child node
- $parent 為 parent node
如下 example:
<?php
class Node {
public $data;
public $left;
public $right;
public $parent;
public function __construct(int $data = NULL, Node $parent = NULL) {
$this->data = $data;
$this->parent = $parent;
$this->left = NULL;
$this->right = NULL;
}
}
# min
找到自當前 node 以下的 BST 中的最小值。 BST 的規則中, 每個 node > left child node
, 因此, 若我要取得該 tree 下最小的 node, 那該 node 必定位於該 tree 的最左最底層 如下 example:
<?php
public function min() {
$node = $this;
while($node->left) {
$node = $node->left;
}
return $node;
}
# max
找到自當前 node 以下的 BST 中的最大值。 BST 的規則中, 每個 node < right child node
, 因此, 若我要取得該 tree 下最大的 node, 那該 node 必定位於該 tree 的最右最底層 如下 example:
<?php
public function max() {
$node = $this;
while($node->right) {
$node = $node->right;
}
return $node;
}
# successor (繼承者)
Tree 當中, 依大小來看, 比當前 node 大的下一個值又稱為 successor (繼任者)。 從 BST 規則我們知道, node < right child node
, 所以, right child node
此 subtree 下的最小值, 便是 node 的 successor 如下 example:
<?php
public function successor() {
$node = $this;
if($node->right)
return $node->right->min();
else
return NULL;
}
# predecessor (前任)
Tree 當中, 依大小來看, 比當前 node 小的上一個值又稱為 predecessor (前任, 不是前男友)。 從 BST 規則我們知道, node > left child node
, 所以, left child node
此 subtree 下的最大值, 便是 node 的 predecessor 如下 example:
<?php
public function predecessor() {
$node = $this;
if($node->left)
return $node->left->max();
else
return NULL;
}
# BST
現在來講講 BST class, 一樣會從 BST class 到各個 method 做概念上的解說
# BST class
BST 只有一個 property $root, 代表此 BST 的 root node
<?php
class BST {
public $root = NULL;
public function __construct(int $data) {
$this->root = new Node($data);
}
}
# isEmpty
這個比較簡單, 判斷該 BST 是否為 empty tree 如下 example:
<?php
public function isEmpty(): bool {
return $this->root === NULL;
}
# insert
程式碼看起來有點長, 但其實邏輯與概念都不複雜。 BST 的排列規則為 node > left child node
, node < right child node
, 因此, 不停的拿 node 與 data 循著此規則比較並往下, 便可以找到適合 insert data 的位置 如下 example:
<?php
function insert(int $data)
{
if ($this->isEmpty()) {
$node = new Node($data);
$this->root = $node;
return $node;
}
$node = $this->root;
while ($node) {
if ($data > $node->data) {
if ($node->right) {
$node = $node->right;
}
else {
$node->right = new Node($data, $node);
$node = $node->right;
break;
}
}
elseif ($data < $node->data) {
if ($node->left) {
$node = $node->left;
}
else {
$node->left = new Node($data, $node);
$node = $node->left;
break;
}
}
else {
break;
}
}
return $node;
}
# traverse (遍歷)
traverse 的概念主要利用二個特性, 使用遞迴來找到並 echo 出每個 node 的 data
- BST 的排列規則
- 每個 node 與及 parent 以及 child 都有著 linked list 的特性
<?php
public function traverse(Node $node) {
if ($node) {
if ($node->left)
$this->traverse($node->left);
echo $node->data . "\n";
if ($node->right)
$this->traverse($node->right);
}
}
# remove
remove 概念上很單純, 找到該 node, 然後刪除 會用到 Node class 的 search, delete method, 可先往下看, 等到理解完 search 以及 delete method, 自然無痛領悟 remove method
<?php
public function remove(int $data) {
$node = $this->search($data);
if ($node) $node->delete();
}
# search
細細一看, 有沒有發現概念上其實跟 insert 類似? 差異處在於, insert 找到位置後執行 insert 動作, 而 search 是 return 該 node 一樣是循著 BST 的規則往下找, 找到後 return 該 node (以 break 方式結束 loop), 若沒找到則會 return null (找到底部還沒找到, 所以 $node 為 false 而結束 loop)
<?php
public function search(int $data) {
if ($this->isEmpty()) {
return FALSE;
}
$node = $this->root;
while ($node) {
if ($data > $node->data) {
$node = $node->right;
} elseif ($data < $node->data) {
$node = $node->left;
} else {
break;
}
}
return $node;
}
# delete
Delete 在所有 method 當中, 邏輯是最為複雜的。 首先, 我們先歸納出幾種可能性
- 要被刪除的 node 沒有 child node
- 要被刪除的 node 只有左或右一個 child node
- 要被刪除的 node 有左右 child node
示意圖如下:
如果情況是 1, 那最單純, 直接刪除就可
如果情況是 2, 那概念上也很簡單, 我們只需要將 parent 跟 child 連起來, 而一旦 parent 跟 child 的連結變更了, 那當前 node 也就等於不存在了 (因為沒有 node 可以連結到他) 因此, 我們需要判斷該 node 是其 parent 的 left 或 right child node, 這樣我們才可以修改 parent 上對應的 property, 不然改錯可是會 GG 的。 以及該 node 所擁有的 child node 是 left 還是 right, 概念同 parent
如果情況是 3, 那依照 BST 的規則, node > left child node
, node < right child node
, 因此我們必須將一個合乎這個規則的 node 移動到被刪除 node 原本的位置上, 這樣才會符合 BST 規則 怎麼做呢? 如果上面有認真看過上面解說的朋友就知道, 我們可以使用 successor 或 predecessor 取得合適的 node, 兩者都可, 以下 example 會使用 successor
好啦, 基本上就是這三種概念, 釐清概念之後讀 example code 就簡單很多啦! 那接下來就請參考以下的 example:
<?php
public function delete() {
$node = $this;
if (!$node->left && !$node->right) {
if ($node->parent->left === $node) {
$node->parent->left = NULL;
} else {
$node->parent->right = NULL;
}
} elseif ($node->left && $node->right) {
$successor = $node->successor();
$node->data = $successor->data;
$successor->delete();
} elseif ($node->left) {
if ($node->parent->left === $node) {
$node->parent->left = $node->left;
$node->left->parent = $node->parent;
} else {
$node->parent->right = $node->left;
$node->left->parent = $node->parent;
}
$node->left = NULL;
} elseif ($node->right) {
if ($node->parent->left === $node) {
$node->parent->left = $node->right;
$node->right->parent = $node->parent;
} else {
$node->parent->right = $node->right;
$node->right->parent = $node->parent;
}
$node->right = NULL;
}
}
# 實際跑跑看
下面我們來實際跑跑看, 首先是 insert
<?php
$tree = new BST(10);
$tree->insert(12);
$tree->insert(6);
$tree->insert(3);
$tree->insert(8);
$tree->insert(15);
$tree->insert(13);
$tree->insert(36);
$tree->traverse($tree->root);
這時的 BST 看起來應該會像這樣:
輸出:
3
6
8
10
12
13
15
36
接著來試試 search
<?php
echo $tree->search(14) ? "Found" : "Not Found";
echo "\n";
echo $tree->search(36) ? "Found" : "Not Found";
輸出:
Not Found
Found
最後來試試 remove
<?php
public function remove(int $data) {
$node = $this->search($data);
if ($node) $node->delete();
}
$tree->remove(15);
$tree->traverse($tree->root);
輸出:
3
6
8
10
12
13
36
# Traverse
不曉得有沒有朋友想過一個問題, 那就是為什麼 traverse method 會讓結果自動排序? 到底是什麼黑魔法? 其實, 依照不同的順序, traverse 又分為三種, 分別是 in-order, pre-order, 跟 post-order 讓我們一一觀來!
# in-order
In-order traverse 會在每一個 node 當中, 依循下面的邏輯順序:
- traverse left child node
- echo node data
- traverse right child node
如果是使用 in-order, 那會照 node 的大小順序 echo
# pre-order
pre-order traverse 會在每一個 node 當中, 依循下面的邏輯順序:
- echo node data
- traverse left child node
- traverse right child node
# post-order
post-order traverse 會在每一個 node 當中, 依循下面的邏輯順序:
- traverse left child node
- traverse right child node
- echo node data
只是 echo 的順序不同, 卻會讓結果完全的不同呀! 這個 Ray 思考了一下, 發現很難用文字去解釋, 程式邏輯在遞迴中的執行順序其實跟不在遞迴中也一樣, 只是多了遞迴的概念, 嗯… 我好像在說廢話, 哈哈 不過這邊有個推薦的網站可以模擬並圖示化 BST 的行為, 有興趣的朋友可以去玩玩看!
# 總結
送君千里, 終須一別。 天下無不散的宴席。
本篇文章到此就結束啦, 希望對你/妳有幫助!