練習40：二叉搜索樹 · 笨辦法學C

# 練習40：二叉搜索樹 > 原文：[Exercise 40: Binary Search Trees](http://c.learncodethehardway.org/book/ex40.html) > 譯者：[飛龍](https://github.com/wizardforcel) 二叉樹是最簡單的樹形數據結構，雖然它在許多語言中被哈希表取代，但仍舊對于一些應用很實用。二叉樹的各種變體可用于一些非常實用東西，比如數據庫的索引、搜索算法結構、以及圖像處理。我把我的二叉樹叫做`BSTree`，描述它的最佳方法就是它是另一種`Hashmap`形式的鍵值對儲存容器。它們的差異在于，哈希表為鍵計算哈希值來尋找位置，而二叉樹將鍵與樹中的節點進行對比，之后深入樹中找到儲存它的最佳位置，基于它與其它節點的關系。在我真正解釋它的工作原理之前，讓我向你展示`bstree.h`頭文件，便于你看到數據結構，之后我會用它來解釋如何構建。 ```c #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 ``` 這遵循了我之前用過的相同模式，我創建了一個基容器叫做`BSTree`，它含有叫做`BSTreeNode`的節點，組成實際內容。厭倦了嗎？是的，這種結構也沒有什么高明之處。最重要的部分是，`BSTreeNode`如何配置，以及它如何用于進行每個操作：設置、獲取和刪除。我會首先講解`get`，因為它是最簡單的操作，并且我會在數據結構上手動操作： + 我獲得你要找的鍵，并且用根節點開始遍歷，首先我將你的鍵與這個節點的鍵進行對比。 + 如果你的鍵小于`node.key`，我使用`left`指針來詳細遍歷。 + 如果你的鍵大于`node.key`，我使用`right`指針來詳細遍歷。 + 重復第二步和第三部，知道我找到了匹配`node.key`的節點，或者我遍歷到了沒有左子樹或右子樹的節點。這種情況我會返回`node.data`，其它情況會返回`NULL`。這就是`get`的全部操作，現在是`set`，它幾乎執行相同的操作，除了你在尋找防止新節點的位置。 + 如果`BSTree.root`為空，就算是執行完成了。它就是第一個節點。 + 之后我會將你的鍵與`node.key`進行比對，從根節點開始。 + 如果你的鍵小于或等于`node.key`，我會遍歷左子樹，否則是右子樹。 + 重復第三步，直到我到達了沒有左子樹或右子樹的節點，但是這是我需要選擇的方向。 + 我選擇了這個方向（左或者右）來放置新的節點，并且將這個新節點的父節點設為我來時的上一個節點。當我刪除它時，我會使用它的父節點。這也解釋了它如何工作。如果尋找一個節點涉及到按照鍵的對比來遍歷左子樹或右子樹，那么設置一個節點涉及到相同的事情，直到我找到了一個位置，可以在其左子樹或右子樹上放置新的節點。花一些時間在紙上畫出一些樹并且遍歷一些節點來進行查找或設置，你就可以理解它如何工作。之后你要準備好來看一看實現，我在其中解釋了刪除操作。刪除一個節點非常麻煩，因此它最適合逐行的代碼分解。 ```c #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`如何工作之前，我打算解釋一下我用于執行遞歸函數的模式。你會發現許多樹形數據結構都易于使用遞歸來編寫，而寫成單個函數的形式相當困難。一部分原因在于你需要為第一次操作建立一些初始的數據，之后在數據結構中遞歸，這難以寫成一個函數。解決辦法就是使用兩個函數。一個函數“建立”數據結構和首次遞歸的條件使第二層函數能夠執行真正的邏輯。首先看一看`BSTree_get`來理解我所說的。 + 我設置了初始條件來處理遞歸，如果`map->NULL`是`NULL`，那么就返回`NULL`并且不需要遞歸。 + 之后我執行了真正的遞歸調用，它就是`BSTree_getnode`。我設置了根節點的初始條件、`key`和`map`。 + 之后在`BSTree_getnode`中，我執行了真正的遞歸邏輯，我將是用`map->compare(node->key, key)`來進行鍵的比對，并且根據結果遍歷左子樹或右子樹，或者相等。 + 由于這個函數時“自相似”的，并且不用處理任何初始條件（因為`BSTree_get`處理了），我就可以使它非常簡單。當它完成時會返回給調用者，最后把結構返回給`BSTree_get`。 + 最后，在結果不為`NULL`的情況下，`BSTree_get`處理獲得的`node.data`元素。這種構造遞歸算法的方法，與我構造遞歸數據結構的方法一致。我創建了一個起始的“基函數”，它處理初始條件和一些邊界情況，之后它調用了一個簡潔的遞歸函數來執行任務。與之相比，我在`BStree`中創建了“基結構”，它持有遞歸的`BSTreeNode`結構，每個節點都引用樹中的其它節點。使用這種模式讓我更容易處理遞歸并保持簡潔。接下來，瀏覽`BSTree_set` 和 `BSTree_setnode`，來觀察相同的模式。我使用`BSTree_set`來確保初始條件和便捷情況。常見的邊界情況就是樹中沒有根節點，于是我需要創建一個函數來初始化它們。這個模式適用于幾乎任何遞歸的算法。我按照這種模式來編寫它們： + 理解初始變量，它們如何改變，以及遞歸每一步的終止條件。 + 編寫調用自身的遞歸函數，帶有參數作為終止條件和初始變量。 + 編程一個啟動函數來設置算法的初始條件，并且處理邊界情況，之后調用遞歸函數。 + 最后，啟動函數返回最后的結果，并且如果遞歸函數不能處理最終的邊界情況可能還要做調整。這引導了我完成`BSTree_delete`和`BSTree_node_delete`。首先你可以看一下`BSTree_delete`和它的啟動函數，它獲取結果節點的數據，并且釋放找到的節點。在`BSTree_node_delete`中事情就變得復雜了，因為要在樹中任意位置刪除一個節點，我需要將子節點翻轉上來。我會逐行拆分這個函數： bstree.c:190 我執行比較函數來找出應該選擇的方向。 bstree.c:192-198 這是“小于”的分支，我應該移到左子樹。這里左子樹并不存在并且返回了`NULL`來表示“未找到”。這處理了一些不在`BSTree`中元素的刪除操作。 bstree.c:199-205 和上面相同，但是是對于樹的右側分支。這就像其它函數一樣只是在樹中向下遍歷，并且在不存在時返回`NULL`。 bstree.c:206 這里是發現目標節點的地方，因為鍵是相等的（`compare`返回了0）。 bstree.c:207 這個節點同時具有`left`和`right`分支，所以它深深嵌入在樹中。 bstree.c:209 要移除這個節點，我首先要找到大于這個節點的最小節點，這里我在右子樹上調用了`BSTree_find_min`。 bstree.c:210 一旦我獲得了這個幾點，我將它的`key`和`data`與當前節點互換。這樣就高效地將當前節點移動到樹的最底端，并且不同通過它的指針來調整節點。 bstree.c:214 現在`successor`是一個無效的分支，儲存了當前節點的值。然而它可能還帶有右子樹，也就是說我必須做一個旋轉使它的右節點上來代替它。 bstree.c:217 到此為止，`successor`已經從樹中移出了，它的值被當前節點的值代替，它的任何子樹都合并進了它的父節點。我可以像`node`一樣返回它。 bstree.c:218 這個分支中，我了解到這個節點沒有右子樹只有左子樹，所以我可以簡單地用左節點來替代它。 bstree.c:219 我再次使用`BSTree_replace_node_in_parent`來執行替換，把左節點旋轉上去。 bstree.c:220 這是只有右子樹而沒有左子樹的情況，所以需要將右節點旋轉上去。 bstree.c:221 再次使用相同的函數，這次是針對右節點。 bstree.c:222 最后，對于我發現的節點只剩下一種情況，就是它沒有任何子樹（沒有做子樹也沒有右子樹）。這種情況，我只需要使用相同函數以`NULL`來執行替換。 bstree.c:210 在此之后，我已經將當前節點從書中移除，并且以某個合適的子節點的元素來替換。我只需要把它返回給調用者，使它能夠被釋放或管理。這個操作非常復雜，實話說，在一些樹形數據結構中，我并不需要執行刪除，而是把它當做軟件中的常亮數據。如果我需要做繁雜的插入和刪除工作，我會使用`Hashmap`。最后，你可以查看它的單元測試以及測試方法： ```c #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`函數，它是針對復雜數據結構的一種有趣的測試技巧。創建一些鍵來覆蓋`BSTree_node_delete`的所有分支相當困難，而且有可能我會錯過一些邊界情況。更好的方法就是創建一個“模糊測試”的函數來執行所有操作，并盡可能以一種可怕且隨機的方式執行它們。這里我插入了一系列隨機字符串的鍵，之后我刪除了它們并試著在刪除之后獲取它們的值。這種測試可以避免只測試到你知道能正常工作的部分，這意味著你不會遺漏不知道的事情。通過想你的數據結構插入一些隨機的垃圾數據，你可以碰到意料之外的事情，并檢測出任何bug。 ## 如何改進不要完成下列任何習題，因為在下個練習中我會使用這里的單元測試，來教你使用一些性能調優的技巧。在你完成練習41之后，你需要返回來完成這些習題。 + 像之前一樣，你應該執行所有防御性編程檢查，并且為不應發生的情況添加`assert`。例如，你不應該在遞歸函數中獲取到`NULL`，為此添加斷言。 + 遍歷函數按照左子樹、右子樹和當前節點的順組進行遍歷。你可以創建相反順序的遍歷函數。 + 每個節點上都會執行完整的字符串比較，但是我可以使用`Hashmap`的哈希函數來提升速度。我可以計算鍵的哈希值，在`BSTreeNode`中儲存它。之后在每個創建的函數中，我可以實現計算出鍵的哈希值，然后在遞歸中向下傳遞。我可以使用哈希來很快地比較每個節點，就像`Hashmap`那樣。 ## 附加題同樣，現在先不要完成它們，直到完成練習41，那時你就可以使用`Valgrind`的性能調優技巧來完成它們了。 + 有一種不使用遞歸的替代的方法，也可以操作這個數據結構。維基百科上介紹了不使用遞歸來完成相同事情的替代方法。這樣做會更好還是更糟？ + 查詢你能找到的所有不同的樹的相關資料。比如AVL樹、紅黑樹、以及一些非樹形結構例如跳轉表。