美思 [資料結構] 使用 C 語言:二元搜尋樹 (Binary Search Tree)

Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

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

二元搜尋樹 (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_t node_t;

struct node_t {
    int data;
    node_t *left;
    node_t *right;
};

typedef struct tree_t tree_t;

struct tree_t {
    node_t *root;
    cmpFn cmp;
};

二元搜尋樹的建構函式

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

typedef short (*cmp_fn)(int a, int b);

tree_t * tree_new(cmp_fn cmp)
{
    tree_t *self = (tree_t *) malloc(sizeof(tree_t));
    if (!self)
        return self;

    self->root = NULL;
    self->cmp = cmp;

    return self;
}

二元搜尋樹的解構函式

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

static void _tree_delete(node_t *node);

void tree_delete(void *self)
{
    if (!self)
        return;

    node_t *root = ((tree_t *) self)->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),後文會介紹二元搜尋樹的走訪。

檢查二元搜尋樹是否為空

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

bool tree_is_empty(const tree_t *self)
{
    assert(self);

    return !(self->root) ? true : false;
}

檢查二元搜尋樹的高度

當節點為空時,高度是 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; 
}

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

若節點為空,表示沒有符合 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;
}

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

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

最小 (極左) 值一定是在整顆樹最左側的節點,故只要從根節點逐一向左走訪至盡頭即可。以下是 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;
}

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

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

最大 (極右) 值一定是在整顆樹最右側的節點,故只要從根節點逐一向右走訪至盡頭即可。以下是 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;
}

將值加入二元搜尋樹中

當節點本身為空 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;
}

這裡補上 node_new 相關的實作:

static node_t * node_new(int value)
{
    node_t *node = (node_t *) malloc(sizeof(node_t));
    if (!node)
        return node;

    node->data = value;
    node->left = NULL;
    node->right = NULL;

    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;
}

這裡補上 _tree_min 部分的實作:

static int _tree_min(const node_t *node)
{
    assert(node);

    if (node->left)
        return _tree_min(node->left);

    return node->data;
}

將二元搜尋樹用於排序 (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)

關於作者

身為資訊領域碩士,美思認為開發應用程式的目的是為社會帶來價值。如果在這個過程中該軟體能成為永續經營的項目,那就是開發者和使用者雙贏的局面。

美思喜歡用開源技術來解決各式各樣的問題,但必要時對專有技術也不排斥。閒暇之餘,美思將所學寫成文章,放在這個網站上和大家分享。