練習40：二叉搜索樹

原文：Exercise 40: Binary Search Treess

譯者：飛龍

二叉樹是最簡單的樹形數據結構湃鹊，雖然它在許多語言中被哈希表取代，但仍舊對于一些應用很實用瞎访。二叉樹的各種變體可用于一些非常實用東西婴梧，比如數據庫的索引蔓倍、搜索算法結構、以及圖像處理敞咧。

我把我的二叉樹叫做BSTree棘捣，描述它的最佳方法就是它是另一種Hashmap形式的鍵值對儲存容器敛纲。它們的差異在于丰辣，哈希表為鍵計算哈希值來尋找位置岗屏，而二叉樹將鍵與樹中的節(jié)點進行對比母剥，之后深入樹中找到儲存它的最佳位置，基于它與其它節(jié)點的關系茵烈。

在我真正解釋它的工作原理之前百匆，讓我向你展示bstree.h頭文件，便于你看到數據結構呜投，之后我會用它來解釋如何構建加匈。

#ifndef _lcthw_BSTree_h
#define _lcthw_BSTree_h


typedef int (*BSTree_compare)(void *a, void *b);

typedef struct BSTreeNode {
    void *key;
    void *data;

    struct BSTreeNode *left;
    struct BSTreeNode *right;
    struct BSTreeNode *parent;
} BSTreeNode;

typedef struct BSTree {
    int count;
    BSTree_compare compare;
    BSTreeNode *root;
} BSTree;

typedef int (*BSTree_traverse_cb)(BSTreeNode *node);

BSTree *BSTree_create(BSTree_compare compare);
void BSTree_destroy(BSTree *map);

int BSTree_set(BSTree *map, void *key, void *data);
void *BSTree_get(BSTree *map, void *key);

int BSTree_traverse(BSTree *map, BSTree_traverse_cb traverse_cb);

void *BSTree_delete(BSTree *map, void *key);

#endif

這遵循了我之前用過的相同模式，我創(chuàng)建了一個基容器叫做BSTree宙彪，它含有叫做BSTreeNode的節(jié)點矩动，組成實際內容。厭倦了嗎释漆？是的悲没，這種結構也沒有什么高明之處。

最重要的部分是男图，BSTreeNode如何配置示姿，以及它如何用于進行每個操作：設置、獲取和刪除逊笆。我會首先講解get栈戳，因為它是最簡單的操作，并且我會在數據結構上手動操作：

• 我獲得你要找的鍵难裆，并且用根節(jié)點開始遍歷子檀，首先我將你的鍵與這個節(jié)點的鍵進行對比。
• 如果你的鍵小于node.key乃戈，我使用left指針來詳細遍歷褂痰。
• 如果你的鍵大于node.key，我使用right指針來詳細遍歷症虑。
• 重復第二步和第三部缩歪，知道我找到了匹配node.key的節(jié)點，或者我遍歷到了沒有左子樹或右子樹的節(jié)點谍憔。這種情況我會返回node.data匪蝙，其它情況會返回NULL。

這就是get的全部操作习贫，現在是set逛球，它幾乎執(zhí)行相同的操作，除了你在尋找防止新節(jié)點的位置沈条。

• 如果BSTree.root為空需忿，就算是執(zhí)行完成了。它就是第一個節(jié)點。
• 之后我會將你的鍵與node.key進行比對屋厘，從根節(jié)點開始涕烧。
• 如果你的鍵小于或等于node.key，我會遍歷左子樹汗洒，否則是右子樹议纯。
• 重復第三步，直到我到達了沒有左子樹或右子樹的節(jié)點溢谤，但是這是我需要選擇的方向瞻凤。
• 我選擇了這個方向（左或者右）來放置新的節(jié)點，并且將這個新節(jié)點的父節(jié)點設為我來時的上一個節(jié)點世杀。當我刪除它時阀参，我會使用它的父節(jié)點。

這也解釋了它如何工作瞻坝。如果尋找一個節(jié)點涉及到按照鍵的對比來遍歷左子樹或右子樹蛛壳，那么設置一個節(jié)點涉及到相同的事情，直到我找到了一個位置所刀，可以在其左子樹或右子樹上放置新的節(jié)點衙荐。

花一些時間在紙上畫出一些樹并且遍歷一些節(jié)點來進行查找或設置，你就可以理解它如何工作浮创。之后你要準備好來看一看實現忧吟，我在其中解釋了刪除操作。刪除一個節(jié)點非常麻煩斩披，因此它最適合逐行的代碼分解溜族。

#include <lcthw/dbg.h>
#include <lcthw/bstree.h>
#include <stdlib.h>
#include <lcthw/bstrlib.h>

static int default_compare(void *a, void *b)
{
    return bstrcmp((bstring)a, (bstring)b);
}


BSTree *BSTree_create(BSTree_compare compare)
{
    BSTree *map = calloc(1, sizeof(BSTree));
    check_mem(map);

    map->compare = compare == NULL ? default_compare : compare;

    return map;

error:
    if(map) {
        BSTree_destroy(map);
    }
    return NULL;
}

static int BSTree_destroy_cb(BSTreeNode *node)
{
    free(node);
    return 0;
}

void BSTree_destroy(BSTree *map)
{
    if(map) {
        BSTree_traverse(map, BSTree_destroy_cb);
        free(map);
    }
}


static inline BSTreeNode *BSTreeNode_create(BSTreeNode *parent, void *key, void *data)
{
    BSTreeNode *node = calloc(1, sizeof(BSTreeNode));
    check_mem(node);

    node->key = key;
    node->data = data;
    node->parent = parent;
    return node;

error:
    return NULL;
}


static inline void BSTree_setnode(BSTree *map, BSTreeNode *node, void *key, void *data)
{
    int cmp = map->compare(node->key, key);

    if(cmp <= 0) {
        if(node->left) {
            BSTree_setnode(map, node->left, key, data);
        } else {
            node->left = BSTreeNode_create(node, key, data);
        }
    } else {
        if(node->right) {
            BSTree_setnode(map, node->right, key, data);
        } else {
            node->right = BSTreeNode_create(node, key, data);
        }
    }
}


int BSTree_set(BSTree *map, void *key, void *data)
{
    if(map->root == NULL) {
        // first so just make it and get out
        map->root = BSTreeNode_create(NULL, key, data);
        check_mem(map->root);
    } else {
        BSTree_setnode(map, map->root, key, data);
    }

    return 0;
error:
    return -1;
}

static inline BSTreeNode *BSTree_getnode(BSTree *map, BSTreeNode *node, void *key)
{
    int cmp = map->compare(node->key, key);

    if(cmp == 0) {
        return node;
    } else if(cmp < 0) {
        if(node->left) {
            return BSTree_getnode(map, node->left, key);
        } else {
            return NULL;
        }
    } else {
        if(node->right) {
            return BSTree_getnode(map, node->right, key);
        } else {
            return NULL;
        }
    }
}

void *BSTree_get(BSTree *map, void *key)
{
    if(map->root == NULL) {
        return NULL;
    } else {
        BSTreeNode *node = BSTree_getnode(map, map->root, key);
        return node == NULL ? NULL : node->data;
    }
}


static inline int BSTree_traverse_nodes(BSTreeNode *node, BSTree_traverse_cb traverse_cb)
{
    int rc = 0;

    if(node->left) {
        rc = BSTree_traverse_nodes(node->left, traverse_cb);
        if(rc != 0) return rc;
    }

    if(node->right) {
        rc = BSTree_traverse_nodes(node->right, traverse_cb);
        if(rc != 0) return rc;
    }

    return traverse_cb(node);
}

int BSTree_traverse(BSTree *map, BSTree_traverse_cb traverse_cb)
{
    if(map->root) {
        return BSTree_traverse_nodes(map->root, traverse_cb);
    }

    return 0;
}

static inline BSTreeNode *BSTree_find_min(BSTreeNode *node)
{
    while(node->left) {
        node = node->left;
    }

    return node;
}

static inline void BSTree_replace_node_in_parent(BSTree *map, BSTreeNode *node, BSTreeNode *new_value)
{
    if(node->parent) {
        if(node == node->parent->left) {
            node->parent->left = new_value;
        } else {
            node->parent->right = new_value;
        }
    } else {
        // this is the root so gotta change it
        map->root = new_value;
    }

    if(new_value) {
        new_value->parent = node->parent;
    }
}

static inline void BSTree_swap(BSTreeNode *a, BSTreeNode *b)
{
    void *temp = NULL;
    temp = b->key; b->key = a->key; a->key = temp;
    temp = b->data; b->data = a->data; a->data = temp;
}

static inline BSTreeNode *BSTree_node_delete(BSTree *map, BSTreeNode *node, void *key)
{
    int cmp = map->compare(node->key, key);

    if(cmp < 0) {
        if(node->left) {
            return BSTree_node_delete(map, node->left, key);
        } else {
            // not found
            return NULL;
        }
    } else if(cmp > 0) {
        if(node->right) {
            return BSTree_node_delete(map, node->right, key);
        } else {
            // not found
            return NULL;
        }
    } else {
        if(node->left && node->right) {
            // swap this node for the smallest node that is bigger than us
            BSTreeNode *successor = BSTree_find_min(node->right);
            BSTree_swap(successor, node);

            // this leaves the old successor with possibly a right child
            // so replace it with that right child
            BSTree_replace_node_in_parent(map, successor, successor->right);

            // finally it's swapped, so return successor instead of node
            return successor;
        } else if(node->left) {
            BSTree_replace_node_in_parent(map, node, node->left);
        } else if(node->right) {
            BSTree_replace_node_in_parent(map, node, node->right);
        } else {
            BSTree_replace_node_in_parent(map, node, NULL);
        }

        return node;
    }
}

void *BSTree_delete(BSTree *map, void *key)
{
    void *data = NULL;

    if(map->root) {
        BSTreeNode *node = BSTree_node_delete(map, map->root, key);

        if(node) {
            data = node->data;
            free(node);
        }
    }

    return data;
}

在講解BSTree_delete如何工作之前，我打算解釋一下我用于執(zhí)行遞歸函數的模式垦沉。你會發(fā)現許多樹形數據結構都易于使用遞歸來編寫斩祭，而寫成單個函數的形式相當困難。一部分原因在于你需要為第一次操作建立一些初始的數據乡话，之后在數據結構中遞歸，這難以寫成一個函數耳奕。

解決辦法就是使用兩個函數绑青。一個函數“建立”數據結構和首次遞歸的條件使第二層函數能夠執(zhí)行真正的邏輯。首先看一看BSTree_get來理解我所說的屋群。

• 我設置了初始條件來處理遞歸闸婴，如果map->NULL是NULL，那么就返回NULL并且不需要遞歸芍躏。
• 之后我執(zhí)行了真正的遞歸調用邪乍，它就是BSTree_getnode。我設置了根節(jié)點的初始條件、key和map庇楞。
• 之后在BSTree_getnode中榜配，我執(zhí)行了真正的遞歸邏輯，我將是用map->compare(node->key, key)來進行鍵的比對吕晌，并且根據結果遍歷左子樹或右子樹蛋褥，或者相等。
• 由于這個函數時“自相似”的睛驳，并且不用處理任何初始條件（因為BSTree_get處理了）烙心，我就可以使它非常簡單。當它完成時會返回給調用者乏沸，最后把結構返回給BSTree_get淫茵。
• 最后，在結果不為NULL的情況下蹬跃，BSTree_get處理獲得的node.data元素匙瘪。

這種構造遞歸算法的方法，與我構造遞歸數據結構的方法一致炬转。我創(chuàng)建了一個起始的“基函數”辆苔，它處理初始條件和一些邊界情況，之后它調用了一個簡潔的遞歸函數來執(zhí)行任務扼劈。與之相比驻啤，我在BStree中創(chuàng)建了“基結構”，它持有遞歸的BSTreeNode結構荐吵，每個節(jié)點都引用樹中的其它節(jié)點骑冗。使用這種模式讓我更容易處理遞歸并保持簡潔。

接下來先煎，瀏覽BSTree_set 和 BSTree_setnode贼涩，來觀察相同的模式。我使用BSTree_set來確保初始條件和便捷情況薯蝎。常見的邊界情況就是樹中沒有根節(jié)點遥倦，于是我需要創(chuàng)建一個函數來初始化它們。

這個模式適用于幾乎任何遞歸的算法占锯。我按照這種模式來編寫它們：

• 理解初始變量袒哥，它們如何改變，以及遞歸每一步的終止條件消略。
• 編寫調用自身的遞歸函數堡称，帶有參數作為終止條件和初始變量。
• 編程一個啟動函數來設置算法的初始條件艺演，并且處理邊界情況却紧，之后調用遞歸函數桐臊。
• 最后，啟動函數返回最后的結果晓殊，并且如果遞歸函數不能處理最終的邊界情況可能還要做調整断凶。

這引導了我完成BSTree_delete和BSTree_node_delete。首先你可以看一下BSTree_delete和它的啟動函數挺物，它獲取結果節(jié)點的數據懒浮，并且釋放找到的節(jié)點。在BSTree_node_delete中事情就變得復雜了识藤，因為要在樹中任意位置刪除一個節(jié)點砚著，我需要將子節(jié)點翻轉上來。我會逐行拆分這個函數：

bstree.c:190

我執(zhí)行比較函數來找出應該選擇的方向痴昧。

bstree.c:192-198

這是“小于”的分支稽穆，我應該移到左子樹。這里左子樹并不存在并且返回了NULL來表示“未找到”赶撰。這處理了一些不在BSTree中元素的刪除操作舌镶。

bstree.c:199-205

和上面相同，但是是對于樹的右側分支豪娜。這就像其它函數一樣只是在樹中向下遍歷餐胀，并且在不存在時返回NULL。

bstree.c:206

這里是發(fā)現目標節(jié)點的地方瘤载，因為鍵是相等的（compare返回了0）否灾。

bstree.c:207

這個節(jié)點同時具有left和right分支，所以它深深嵌入在樹中鸣奔。

bstree.c:209

要移除這個節(jié)點墨技，我首先要找到大于這個節(jié)點的最小節(jié)點，這里我在右子樹上調用了BSTree_find_min挎狸。

bstree.c:210

一旦我獲得了這個幾點扣汪，我將它的key和data與當前節(jié)點互換。這樣就高效地將當前節(jié)點移動到樹的最底端锨匆，并且不同通過它的指針來調整節(jié)點崭别。

bstree.c:214

現在successor是一個無效的分支，儲存了當前節(jié)點的值恐锣。然而它可能還帶有右子樹紊遵，也就是說我必須做一個旋轉使它的右節(jié)點上來代替它。

bstree.c:217

到此為止侥蒙，successor已經從樹中移出了，它的值被當前節(jié)點的值代替匀奏，它的任何子樹都合并進了它的父節(jié)點鞭衩。我可以像node一樣返回它。

bstree.c:218

這個分支中，我了解到這個節(jié)點沒有右子樹只有左子樹论衍，所以我可以簡單地用左節(jié)點來替代它瑞佩。

bstree.c:219

我再次使用BSTree_replace_node_in_parent來執(zhí)行替換，把左節(jié)點旋轉上去坯台。

bstree.c:220

這是只有右子樹而沒有左子樹的情況炬丸，所以需要將右節(jié)點旋轉上去。

bstree.c:221

再次使用相同的函數蜒蕾，這次是針對右節(jié)點稠炬。

bstree.c:222

最后，對于我發(fā)現的節(jié)點只剩下一種情況咪啡，就是它沒有任何子樹（沒有做子樹也沒有右子樹）首启。這種情況，我只需要使用相同函數以NULL來執(zhí)行替換撤摸。

bstree.c:210

在此之后毅桃，我已經將當前節(jié)點從書中移除，并且以某個合適的子節(jié)點的元素來替換准夷。我只需要把它返回給調用者钥飞，使它能夠被釋放或管理。

這個操作非常復雜衫嵌，實話說读宙，在一些樹形數據結構中，我并不需要執(zhí)行刪除渐扮，而是把它當做軟件中的常亮數據论悴。如果我需要做繁雜的插入和刪除工作，我會使用Hashmap墓律。

最后膀估，你可以查看它的單元測試以及測試方法：

#include "minunit.h"
#include <lcthw/bstree.h>
#include <assert.h>
#include <lcthw/bstrlib.h>
#include <stdlib.h>
#include <time.h>

BSTree *map = NULL;
static int traverse_called = 0;
struct tagbstring test1 = bsStatic("test data 1");
struct tagbstring test2 = bsStatic("test data 2");
struct tagbstring test3 = bsStatic("xest data 3");
struct tagbstring expect1 = bsStatic("THE VALUE 1");
struct tagbstring expect2 = bsStatic("THE VALUE 2");
struct tagbstring expect3 = bsStatic("THE VALUE 3");

static int traverse_good_cb(BSTreeNode *node)
{
    debug("KEY: %s", bdata((bstring)node->key));
    traverse_called++;
    return 0;
}


static int traverse_fail_cb(BSTreeNode *node)
{
    debug("KEY: %s", bdata((bstring)node->key));
    traverse_called++;

    if(traverse_called == 2) {
        return 1;
    } else {
        return 0;
    }
}


char *test_create()
{
    map = BSTree_create(NULL);
    mu_assert(map != NULL, "Failed to create map.");

    return NULL;
}

char *test_destroy()
{
    BSTree_destroy(map);

    return NULL;
}


char *test_get_set()
{
    int rc = BSTree_set(map, &test1, &expect1);
    mu_assert(rc == 0, "Failed to set &test1");
    bstring result = BSTree_get(map, &test1);
    mu_assert(result == &expect1, "Wrong value for test1.");

    rc = BSTree_set(map, &test2, &expect2);
    mu_assert(rc == 0, "Failed to set test2");
    result = BSTree_get(map, &test2);
    mu_assert(result == &expect2, "Wrong value for test2.");

    rc = BSTree_set(map, &test3, &expect3);
    mu_assert(rc == 0, "Failed to set test3");
    result = BSTree_get(map, &test3);
    mu_assert(result == &expect3, "Wrong value for test3.");

    return NULL;
}

char *test_traverse()
{
    int rc = BSTree_traverse(map, traverse_good_cb);
    mu_assert(rc == 0, "Failed to traverse.");
    mu_assert(traverse_called == 3, "Wrong count traverse.");

    traverse_called = 0;
    rc = BSTree_traverse(map, traverse_fail_cb);
    mu_assert(rc == 1, "Failed to traverse.");
    mu_assert(traverse_called == 2, "Wrong count traverse for fail.");

    return NULL;
}

char *test_delete()
{
    bstring deleted = (bstring)BSTree_delete(map, &test1);
    mu_assert(deleted != NULL, "Got NULL on delete.");
    mu_assert(deleted == &expect1, "Should get test1");
    bstring result = BSTree_get(map, &test1);
    mu_assert(result == NULL, "Should delete.");

    deleted = (bstring)BSTree_delete(map, &test1);
    mu_assert(deleted == NULL, "Should get NULL on delete");

    deleted = (bstring)BSTree_delete(map, &test2);
    mu_assert(deleted != NULL, "Got NULL on delete.");
    mu_assert(deleted == &expect2, "Should get test2");
    result = BSTree_get(map, &test2);
    mu_assert(result == NULL, "Should delete.");

    deleted = (bstring)BSTree_delete(map, &test3);
    mu_assert(deleted != NULL, "Got NULL on delete.");
    mu_assert(deleted == &expect3, "Should get test3");
    result = BSTree_get(map, &test3);
    mu_assert(result == NULL, "Should delete.");

    // test deleting non-existent stuff
    deleted = (bstring)BSTree_delete(map, &test3);
    mu_assert(deleted == NULL, "Should get NULL");

    return NULL;
}

char *test_fuzzing()
{
    BSTree *store = BSTree_create(NULL);
    int i = 0;
    int j = 0;
    bstring numbers[100] = {NULL};
    bstring data[100] = {NULL};
    srand((unsigned int)time(NULL));

    for(i = 0; i < 100; i++) {
        int num = rand();
        numbers[i] = bformat("%d", num);
        data[i] = bformat("data %d", num);
        BSTree_set(store, numbers[i], data[i]);
    }

    for(i = 0; i < 100; i++) {
        bstring value = BSTree_delete(store, numbers[i]);
        mu_assert(value == data[i], "Failed to delete the right number.");

        mu_assert(BSTree_delete(store, numbers[i]) == NULL, "Should get nothing.");

        for(j = i+1; j < 99 - i; j++) {
            bstring value = BSTree_get(store, numbers[j]);
            mu_assert(value == data[j], "Failed to get the right number.");
        }

        bdestroy(value);
        bdestroy(numbers[i]);
    }

    BSTree_destroy(store);

    return NULL;
}

char *all_tests()
{
    mu_suite_start();

    mu_run_test(test_create);
    mu_run_test(test_get_set);
    mu_run_test(test_traverse);
    mu_run_test(test_delete);
    mu_run_test(test_destroy);
    mu_run_test(test_fuzzing);

    return NULL;
}

RUN_TESTS(all_tests);

我要重點講解test_fuzzing函數，它是針對復雜數據結構的一種有趣的測試技巧耻讽。創(chuàng)建一些鍵來覆蓋BSTree_node_delete的所有分支相當困難察纯，而且有可能我會錯過一些邊界情況。更好的方法就是創(chuàng)建一個“模糊測試”的函數來執(zhí)行所有操作针肥，并盡可能以一種可怕且隨機的方式執(zhí)行它們饼记。這里我插入了一系列隨機字符串的鍵，之后我刪除了它們并試著在刪除之后獲取它們的值慰枕。

這種測試可以避免只測試到你知道能正常工作的部分具则，這意味著你不會遺漏不知道的事情。通過想你的數據結構插入一些隨機的垃圾數據具帮，你可以碰到意料之外的事情博肋，并檢測出任何bug低斋。

如何改進

不要完成下列任何，因為在下個練習中我會使用這里的單元測試匪凡，來教你使用一些性能調優(yōu)的技巧膊畴。在你完成練習41之后，你需要返回來完成這些練習病游。

• 像之前一樣唇跨，你應該執(zhí)行所有防御性編程檢查，并且為不應發(fā)生的情況添加assert衬衬。例如买猖，你不應該在遞歸函數中獲取到NULL，為此添加斷言佣耐。
• 遍歷函數按照左子樹政勃、右子樹和當前節(jié)點的順組進行遍歷。你可以創(chuàng)建相反順序的遍歷函數兼砖。
• 每個節(jié)點上都會執(zhí)行完整的字符串比較奸远，但是我可以使用Hashmap的哈希函數來提升速度。我可以計算鍵的哈希值讽挟，在BSTreeNode中儲存它懒叛。之后在每個創(chuàng)建的函數中，我可以實現計算出鍵的哈希值耽梅，然后在遞歸中向下傳遞薛窥。我可以使用哈希來很快地比較每個節(jié)點，就像Hashmap那樣眼姐。

附加題

同樣诅迷，現在先不要完成它們，直到完成練習41众旗，那時你就可以使用Valgrind的性能調優(yōu)技巧來完成它們了罢杉。

• 有一種不使用遞歸的替代的方法，也可以操作這個數據結構贡歧。維基百科上介紹了不使用遞歸來完成相同事情的替代方法滩租。這樣做會更好還是更糟？
• 查詢你能找到的所有不同的樹的相關資料利朵。比如AVL樹律想、紅黑樹、以及一些非樹形結構例如跳轉表绍弟。