二元搜尋樹 (Binary Search Tree)

    二元搜尋樹的抽象資料結構

    二元搜尋樹 (binary search tree) 是樹 (tree) 的一種,二元樹會分為左子樹和右子樹兩部分。在初階的資料結構教材中,不會對二元搜尋樹進行平衡的動作,這樣的樹實用性偏低,但易於實作,會拿來做為樹的第一個實例。本文會實做一個未平衡的二元搜尋樹。

    二元搜尋樹的抽象資料結構如下:

    T is a BST (binary search tree)
    
    sub IsEmpty(T): bool
    sub Height(T): size
    sub Contains(T, value): bool
    sub Max(T): result
    sub Min(T): result
    sub Add(T, value): void
    sub Remove(T, value): void
    

    由其抽象資料結構可知二元搜尋樹有以下的行為:

    • IsEmpty(T):檢查樹是否為空
    • Height(T):取得樹的高度
    • Contains(T, value):檢查特定值是否存在於樹中
    • Max(T):取得樹的最大值
    • Min(T):取得樹的最小值
    • Add(T, value):將單一值加入樹
    • Remove(T, value):將單一值移出樹

    宣告二元搜尋樹類別

    以下是二元搜尋樹的類別的虛擬碼:

    class Node:
        data <- empty
        left <- null as pointer to Node
        right <- null as pointer to Node
    
    class Tree:
        root <- null as pointer to Node
        cmp <- a predicate function
    

    這時候內部節點會有 leftright 兩個指向其他節點的指標,和先前的線性資料結構的內部結點相異。

    市面上常見的教材會把二元搜尋樹的比較條件寫死在程式碼中,這樣寫比較易理解,但程式碼的重用性較低。在此處,我們將大小比較的程式抽出來,寫在函式 cmp 中。cmp 會根據兩個值的大小關係回傳 10-1,藉此判斷兩個值的關係。只要該程式語言支援函數式程式的特性都可以用這種手法寫,以 C 語言來說,C 語言支援指向函式的指標 (pointer to function),故可用這個寫法。

    以下是等效的 C 語言實作:

    typedef struct node node_t;
    
    struct node {
        int data;
        node_t *left;
        node_t *right;
    };
    
    typedef struct tree tree_t;
    
    struct tree {
        node_t *root;
        cmp_fn cmp;
    };
    

    二元搜尋樹的建構函式

    以下是以 C 語言實作的二元搜尋樹的建構函式:

    typedef short (*cmp_fn)(int a, int b);
    
    tree_t * tree_new(cmp_fn cmp)
    {
        tree_t *tr = (tree_t *) malloc(sizeof(tree_t));
        if (!tr) {
            return tr;
        }
    
        tr->root = NULL;
        tr->cmp = cmp;
    
        return tr;
    }
    

    二元搜尋樹的解構函式

    以下是 C 語言的二元搜尋樹的解構函式:

    static void _tree_delete(node_t *node);
    
    void tree_delete(void *self)
    {
        if (!self) {
            return;
        }
    
        node_t *root = ((tree_t *) self)->root;
        if (root) {
            _tree_delete(root);
        }
    
        free(self);
    }
    
    static void _tree_delete(node_t *node)
    {
        if (!node) {
            return;
        }
    
        _tree_delete(node->left);
        _tree_delete(node->right);
        free(node);
    }
    

    要先以遞迴逐一走訪並釋放內部節點後再釋放二元樹物件本身;走訪的方式是採後序走訪 (postorder traversal),後文會介紹二元搜尋樹的走訪。

    檢查二元搜尋樹是否為空

    檢查二元搜尋樹是否為空的虛擬碼如下:

    sub IsEmpty(T): bool
        return T.root == null
    

    藉由檢查根節點是否為空 null 即可知樹是否為空。以下是等效的 C 語言實作:

    bool tree_is_empty(const tree_t *self)
    {
        assert(self);
    
        return !(self->root) ? true : false;
    }
    

    檢查二元搜尋樹的高度

    檢查二元搜尋樹高度的虛擬碼如下:

    sub Height(T): size    
        return _Height(T.root)
    
    sub _Height(node): size
        if node == null then
            return 0
        end
        
        left <- node.left == null ? 0 : _Height(node.left)
        right <- node.rigth == null ? 0 : _Height(node.right)
    
        height <- left > right ? left : right
        
        return height + 1
    

    當節點為空時,高度是 0

    反之,分別檢查左子樹和右子樹的高度後,取較大值,再加 1 (本身高度),最後回傳答案。

    從根節點開始遞迴走訪即可知道整顆樹的高度。樹會大量使用遞迴,如果對遞迴程式不熟,最好先回頭看一下基礎的遞迴程式怎麼寫。以下是等效的 C 語言實作:

    static size_t _tree_height(const node_t *node);
    
    size_t tree_height(const tree_t *self)
    {
        assert(self);
    
        return _tree_height(self->root);
    }
    
    static size_t _tree_height(const node_t *node)
    {
        if (!node) {
            return 0;
        }
    
        size_t l = (!(node->left)) ? 0 : _tree_height(node->left);
        size_t r = (!(node->right)) ? 0 : _tree_height(node->right);
    
        size_t h = l > r ? l : r;
    
        return h + 1; 
    }
    

    檢查特定值是否存在於二元搜尋樹中

    檢查值是否存在於二元搜尋樹的虛擬碼如下:

    cmp is a predicate function
    
    sub Contains(T, value): bool
        return _Contains(T.root, value)
        
    sub _Contains(node, value): bool
        if node == null then
            return false
        end if
        
        if cmp(node.data, value) == 0 then
            return true
        else if cmp(value, node->data) < 0 then
            return _Contains(node.left, value)
        else
            return _Contains(node.right, value)
        end if
    

    若節點為空,表示沒有符合 value 的值,故回傳 false

    若節點不為空,則以 cmp 比較兩者間的關係。若兩數相符,則回傳 true;若節點值大於 value,則繼續搜尋左子樹以找出是否有符合 value 的值;若節點小於 value,則繼續搜尋右子樹以找出是否有符合 value 的值。

    從根節點開始遞迴走訪,即可找出整顆樹中是否有符合 value 的值。

    以下是等效的 C 語言程式碼:

    static bool _tree_contains(node_t *node, int value, cmp_fn cmp);
    
    bool tree_contains(const tree_t *self, int value)
    {
        assert(self);
    
        return _tree_contains(self->root, value, self->cmp);
    }
    
    static bool _tree_contains(node_t *node, int value, cmp_fn cmp) {
        if (!node) {
            return false;
        }
        
        if (cmp(value, node->data) == 0) {
            return true;
        }
        else if (cmp(value, node->data) < 0) {
            return _tree_contains(node->left, value, cmp);
        }
        else if (cmp(value, node->data) > 0) {
            return _tree_contains(node->right, value, cmp);
        }
    
        return false;
    }
    

    取得二元搜尋樹的最小 (極左) 值

    註:在本範例程式中,極左極不一定是最小值,需注意。

    以下是取得二元搜尋樹的最小 (極左) 值的虛擬碼:

    sub Min(T): result
        assert not IsEmpty(T)
        
        p <- T
        while (p.left != null) do
            p <- p.left
        end while
        
        return p.data
    

    最小 (極左) 值一定是在整顆樹最左側的節點,故只要從根節點逐一向左走訪至盡頭即可。以下是等效的 C 程式實作:

    int tree_min(const tree_t *self)
    {
        assert(!tree_is_empty(self));
    
        node_t *p = self->root;
        while (p->left) {
            p = p->left;
        }
    
        return p->data;
    }
    

    取得二元搜尋樹的最大 (極右) 值

    註:在本範例程式中,極右極不一定是最大值,需注意。

    以下是取得二元搜尋樹的最大 (極右) 值的虛擬碼:

    cmp is a predicate function
    
    sub Max(T): result
        assert not IsEmpty(T)
        
        p <- T
        while (p.right != null) do
            p <- p.right
        end while
        
        return p.data
    

    最大 (極右) 值一定是在整顆樹最右側的節點,故只要從根節點逐一向右走訪至盡頭即可。以下是等效的 C 程式實作:

    int tree_max(const tree_t *self)
    {
        assert(!tree_is_empty(self));
    
        node_t *p = self->root;
        while (p->right) {
            p = p->right;
        }
    
        return p->data;
    }
    

    將值加入二元搜尋樹中

    以下是將值加入二元搜尋樹的虛擬碼:

    cmp is a predicate function
    
    sub Add(T, value): void
        _Add(T.root, value)
    
    sub _Add(node, value): void
        if node == null then
            tree = node_t(value)
            node <- tree
            return
        end
        
        if cmp(node.data, value) >= 0 then
            _Add(node.left, value)
        else
            _Add(node.right, value)
        end if
    

    當節點本身為空 null 時,直接在節點處新增子樹 tree 即可。

    當節點不為空時,會根據 value 和節點值的關係來決定下一個步驟。當節點值大於 value 時,繼續搜尋左子樹,找出適合加入節點的位置;當節點值小於 value 時,繼續搜尋右子樹,找出適合加入節點的位置。

    當節點值等於 value 時,有兩種處理方式,一種是拋棄該值,一種是將該值指定至左右子樹之一;指定子樹時,需固定方向。基本上要看值的數量重不重要來決定實做的方式。

    以下是等效的 C 語言實作:

    static bool _tree_insert(node_t **node, int value, cmp_fn cmp);
    
    bool tree_insert(tree_t *self, int value)
    {
        assert(self);
    
        return _tree_insert(&(self->root), value, self->cmp);
    }
    
    static bool _tree_insert(node_t **node, int value, cmp_fn cmp)
    {
        if (!(*node)) {
            *node = node_new(value);
            if (!(*node)) {
                return false;
            }
    
            return true;
        }
    
        if (cmp(value, (*node)->data) < 0) {
            return _tree_insert(&((*node)->left), value, cmp);
        }
        else if (cmp(value, (*node)->data) >= 0) {
            return _tree_insert(&((*node)->right), value, cmp);
        }
    
        return false;
    }
    

    將值移出二元搜尋樹

    以下是將值移出二元搜尋樹的虛擬碼:

    cmp is a predicate function
    
    sub Remove(T, value): void
        T.root <- _Remove(T.root, value)
    
    sub _Remove(node, value): tree
        if node == null then
            return null
        end if
        
        if cmp(node.data, value) > 0 then
            node.left <- _Remove(node.left, value)
        else if cmp(node.data, value) < 0 then
            node.right <- _Remove(node.right, value)
        else
            if node.left == null then
                p <- node
                node <- node.right
                delete p
            else if node.right == null then
                p <- node
                node <- node.left
                delete p
            else
                min <- _Max(node.right)
                node.data <- min
                node.right <- _Remove(node.right, min)
            end if
        end fi
        
        return node
    

    若節點為空,不需執行移出值的動作,直接跳出函式即可。

    若節點不為空,則需依照節點值和 value 間的關係來決定下步。當節點值大於 value 時,繼續搜尋左子樹,以找出符合條件的可刪除值;反之,當節點值小於 value 時,繼續搜尋右子樹,以找出符合條件的可刪除值。

    當節點值符合 value 時,會依照該節點和子樹間的關決決定下一步。當左子樹為空時,直接以右子樹取代節點所在的位置;反之,當右子樹為空時,直接以左子樹取代節點所在的位置。當左右子樹皆不為空時,找出右子樹的最小值,取代原節點的值;之後要繼續搜尋右子樹,刪除該最小值。會以右子樹的最小值是為了保持樹的值之間的相對關係,也可以左子樹的最大值來補值,讀者可試著練習看看。

    以下是等效的 C 語言實作:

    static bool _tree_remove(node_t **node, int value, cmp_fn cmp);
    
    bool tree_remove(tree_t *self, int value)
    {
        if (tree_is_empty(self)) {
            return false;
        }
    
        return _tree_remove(&(self->root), value, self->cmp);
    }
    
    static bool _tree_remove(node_t **node, int value, cmp_fn cmp)
    {
        if (!(*node)) {
            return false;
        }
    
        if (cmp(value, (*node)->data) < 0) {
            return _tree_remove(&((*node)->left), value, cmp);
        }
        else if (cmp(value, (*node)->data) > 0) {
            return _tree_remove(&((*node)->right), value, cmp);
        }
    
        if (!((*node)->left)) {
            node_t *temp = (*node)->right;
            free(*node);
            *node = temp;
        }
        else if (!((*node)->right)) {
            node_t *temp = (*node)->left;
            free(*node);
            *node = temp;
        }
        else {
            int min = _tree_min((*node)->right);
            (*node)->data = min;
            if (!_tree_remove(&((*node)->right), min, cmp)) {
                return false;
            }
        }
    
        return true;
    }
    

    將二元搜尋樹用於排序 (sorting) 和搜尋 (searching) 問題

    二元搜尋樹也可用於排序 (sorting) 和搜尋 (searching) 問題。當我們放入元素時,這些元素已經按照特定的順序排列好,只要以中序走訪 (in-order traversal) 走訪整個二元樹,就可以得到排序後的串列。在前文中提及的 Contains(T, value) 函式,其實就是搜尋問題的實例。

    演算法上的效率

    假定 T 是一個二元搜尋樹,本範例的二元搜尋樹在演算法上的效率如下:

    • IsEmpty(T)O(1)
    • Height(T):最差為 O(n),最佳為 O(log(n))
    • Contains(T, value)O(Height(T))
    • Max(T)O(Height(T))
    • Min(T): O(Height(T))
    • Add(T, value)O(Height(T))
    • Remove(T, value)O(Height(T))

    二元樹的效率會和樹的高度相關,樹越高,運行時間越久。理想上,二元樹的高度的成長率為 O(log(n)),但本文的二元樹採初階的實作方式,沒有對樹進行平衡,在最差的情形下該二元樹可能會退化成鏈結串列,這時候樹高度的成長率變成 O(n)

    【分享本文】
    Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Yahoo
    【追蹤本站】
    Facebook Facebook Twitter