資料結構 - Binary Search Tree (二元搜尋樹) - PHP 實作

Data Structure and Algorithm 14 分钟 讀完 (大概 2026 字)

# 前言

強者朋友說: 演算法不熟情有可原, 但是資料結構不懂就是你的錯了。
如果對 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

  1. BST 的排列規則
  2. 每個 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();
}

細細一看, 有沒有發現概念上其實跟 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 當中, 邏輯是最為複雜的。
首先, 我們先歸納出幾種可能性

  1. 要被刪除的 node 沒有 child node
  2. 要被刪除的 node 只有左或右一個 child node
  3. 要被刪除的 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 當中, 依循下面的邏輯順序：

  1. traverse left child node
  2. echo node data
  3. traverse right child node

如果是使用 in-order, 那會照 node 的大小順序 echo


# pre-order

pre-order traverse 會在每一個 node 當中, 依循下面的邏輯順序：

  1. echo node data
  2. traverse left child node
  3. traverse right child node

# post-order

post-order traverse 會在每一個 node 當中, 依循下面的邏輯順序：

  1. traverse left child node
  2. traverse right child node
  3. echo node data

只是 echo 的順序不同, 卻會讓結果完全的不同呀！ 這個 Ray 思考了一下, 發現很難用文字去解釋, 程式邏輯在遞迴中的執行順序其實跟不在遞迴中也一樣, 只是多了遞迴的概念, 嗯… 我好像在說廢話, 哈哈
不過這邊有個推薦的網站可以模擬並圖示化 BST 的行為, 有興趣的朋友可以去玩玩看！
Binary Tree Visualiser



# 總結

送君千里, 終須一別。
天下無不散的宴席。

本篇文章到此就結束啦, 希望對你/妳有幫助！



# 參考來源

#PHP #Tree #Binary Search Tree
Character Sets, Collations, Unicode (MySQL 官方文件原子化翻譯) 資料結構 - Binary Tree (二元樹) - PHP 實作

留言

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×