练习40：二叉搜索树

原文：Exercise 40: Binary Search Trees

译者：飞龙

二叉树是最简单的树形数据结构，虽然它在许多语言中被哈希表取代，但仍旧对于一些应用很实用。二叉树的各种变体可用于一些非常实用东西，比如数据库的索引、搜索算法结构、以及图像处理。

我把我的二叉树叫做BSTree，描述它的最佳方法就是它是另一种Hashmap形式的键值对储存容器。它们的差异在于，哈希表为键计算哈希值来寻找位置，而二叉树将键与树中的节点进行对比，之后深入树中找到储存它的最佳位置，基于它与其它节点的关系。

在我真正解释它的工作原理之前，让我向你展示bstree.h头文件，便于你看到数据结构，之后我会用它来解释如何构建。

  1. #ifndef _lcthw_BSTree_h
  2. #define _lcthw_BSTree_h
  5. typedef int (*BSTree_compare)(void *a, void *b);
  7. typedef struct BSTreeNode {
  8.     void *key;
  9.     void *data;
  11.     struct BSTreeNode *left;
  12.     struct BSTreeNode *right;
  13.     struct BSTreeNode *parent;
  14. } BSTreeNode;
  16. typedef struct BSTree {
  17.     int count;
  18.     BSTree_compare compare;
  19.     BSTreeNode *root;
  20. } BSTree;
  22. typedef int (*BSTree_traverse_cb)(BSTreeNode *node);
  24. BSTree *BSTree_create(BSTree_compare compare);
  25. void BSTree_destroy(BSTree *map);
  27. int BSTree_set(BSTree *map, void *key, void *data);
  28. void *BSTree_get(BSTree *map, void *key);
  30. int BSTree_traverse(BSTree *map, BSTree_traverse_cb traverse_cb);
  32. void *BSTree_delete(BSTree *map, void *key);
  34. #endif

这遵循了我之前用过的相同模式，我创建了一个基容器叫做BSTree，它含有叫做BSTreeNode的节点，组成实际内容。厌倦了吗？是的，这种结构也没有什么高明之处。

最重要的部分是，BSTreeNode如何配置，以及它如何用于进行每个操作：设置、获取和删除。我会首先讲解get，因为它是最简单的操作，并且我会在数据结构上手动操作：

  • 我获得你要找的键，并且用根节点开始遍历，首先我将你的键与这个节点的键进行对比。
  • 如果你的键小于node.key，我使用left指针来详细遍历。
  • 如果你的键大于node.key，我使用right指针来详细遍历。
  • 重复第二步和第三部，知道我找到了匹配node.key的节点，或者我遍历到了没有左子树或右子树的节点。这种情况我会返回node.data，其它情况会返回NULL。

这就是get的全部操作，现在是set，它几乎执行相同的操作，除了你在寻找防止新节点的位置。

  • 如果BSTree.root为空，就算是执行完成了。它就是第一个节点。
  • 之后我会将你的键与node.key进行比对，从根节点开始。
  • 如果你的键小于或等于node.key，我会遍历左子树，否则是右子树。
  • 重复第三步，直到我到达了没有左子树或右子树的节点，但是这是我需要选择的方向。
  • 我选择了这个方向（左或者右）来放置新的节点，并且将这个新节点的父节点设为我来时的上一个节点。当我删除它时，我会使用它的父节点。

这也解释了它如何工作。如果寻找一个节点涉及到按照键的对比来遍历左子树或右子树，那么设置一个节点涉及到相同的事情，直到我找到了一个位置，可以在其左子树或右子树上放置新的节点。

花一些时间在纸上画出一些树并且遍历一些节点来进行查找或设置，你就可以理解它如何工作。之后你要准备好来看一看实现，我在其中解释了删除操作。删除一个节点非常麻烦，因此它最适合逐行的代码分解。

  1. #include <lcthw/dbg.h>
  2. #include <lcthw/bstree.h>
  3. #include <stdlib.h>
  4. #include <lcthw/bstrlib.h>
  6. static int default_compare(void *a, void *b)
  7. {
  8.     return bstrcmp((bstring)a, (bstring)b);
  9. }
  12. BSTree *BSTree_create(BSTree_compare compare)
  13. {
  14.     BSTree *map = calloc(1, sizeof(BSTree));
  15.     check_mem(map);
  17.     map->compare = compare == NULL ? default_compare : compare;
  19.     return map;
  21. error:
  22.     if(map) {
  23.         BSTree_destroy(map);
  24.     }
  25.     return NULL;
  26. }
  28. static int BSTree_destroy_cb(BSTreeNode *node)
  29. {
  30.     free(node);
  31.     return 0;
  32. }
  34. void BSTree_destroy(BSTree *map)
  35. {
  36.     if(map) {
  37.         BSTree_traverse(map, BSTree_destroy_cb);
  38.         free(map);
  39.     }
  40. }
  43. static inline BSTreeNode *BSTreeNode_create(BSTreeNode *parent, void *key, void *data)
  44. {
  45.     BSTreeNode *node = calloc(1, sizeof(BSTreeNode));
  46.     check_mem(node);
  48.     node->key = key;
  49.     node->data = data;
  50.     node->parent = parent;
  51.     return node;
  53. error:
  54.     return NULL;
  55. }
  58. static inline void BSTree_setnode(BSTree *map, BSTreeNode *node, void *key, void *data)
  59. {
  60.     int cmp = map->compare(node->key, key);
  62.     if(cmp <= 0) {
  63.         if(node->left) {
  64.             BSTree_setnode(map, node->left, key, data);
  65.         } else {
  66.             node->left = BSTreeNode_create(node, key, data);
  67.         }
  68.     } else {
  69.         if(node->right) {
  70.             BSTree_setnode(map, node->right, key, data);
  71.         } else {
  72.             node->right = BSTreeNode_create(node, key, data);
  73.         }
  74.     }
  75. }
  78. int BSTree_set(BSTree *map, void *key, void *data)
  79. {
  80.     if(map->root == NULL) {
  81.         // first so just make it and get out
  82.         map->root = BSTreeNode_create(NULL, key, data);
  83.         check_mem(map->root);
  84.     } else {
  85.         BSTree_setnode(map, map->root, key, data);
  86.     }
  88.     return 0;
  89. error:
  90.     return -1;
  91. }
  93. static inline BSTreeNode *BSTree_getnode(BSTree *map, BSTreeNode *node, void *key)
  94. {
  95.     int cmp = map->compare(node->key, key);
  97.     if(cmp == 0) {
  98.         return node;
  99.     } else if(cmp < 0) {
  100.         if(node->left) {
  101.             return BSTree_getnode(map, node->left, key);
  102.         } else {
  103.             return NULL;
  104.         }
  105.     } else {
  106.         if(node->right) {
  107.             return BSTree_getnode(map, node->right, key);
  108.         } else {
  109.             return NULL;
  110.         }
  111.     }
  112. }
  114. void *BSTree_get(BSTree *map, void *key)
  115. {
  116.     if(map->root == NULL) {
  117.         return NULL;
  118.     } else {
  119.         BSTreeNode *node = BSTree_getnode(map, map->root, key);
  120.         return node == NULL ? NULL : node->data;
  121.     }
  122. }
  125. static inline int BSTree_traverse_nodes(BSTreeNode *node, BSTree_traverse_cb traverse_cb)
  126. {
  127.     int rc = 0;
  129.     if(node->left) {
  130.         rc = BSTree_traverse_nodes(node->left, traverse_cb);
  131.         if(rc != 0) return rc;
  132.     }
  134.     if(node->right) {
  135.         rc = BSTree_traverse_nodes(node->right, traverse_cb);
  136.         if(rc != 0) return rc;
  137.     }
  139.     return traverse_cb(node);
  140. }
  142. int BSTree_traverse(BSTree *map, BSTree_traverse_cb traverse_cb)
  143. {
  144.     if(map->root) {
  145.         return BSTree_traverse_nodes(map->root, traverse_cb);
  146.     }
  148.     return 0;
  149. }
  151. static inline BSTreeNode *BSTree_find_min(BSTreeNode *node)
  152. {
  153.     while(node->left) {
  154.         node = node->left;
  155.     }
  157.     return node;
  158. }
  160. static inline void BSTree_replace_node_in_parent(BSTree *map, BSTreeNode *node, BSTreeNode *new_value)
  161. {
  162.     if(node->parent) {
  163.         if(node == node->parent->left) {
  164.             node->parent->left = new_value;
  165.         } else {
  166.             node->parent->right = new_value;
  167.         }
  168.     } else {
  169.         // this is the root so gotta change it
  170.         map->root = new_value;
  171.     }
  173.     if(new_value) {
  174.         new_value->parent = node->parent;
  175.     }
  176. }
  178. static inline void BSTree_swap(BSTreeNode *a, BSTreeNode *b)
  179. {
  180.     void *temp = NULL;
  181.     temp = b->key; b->key = a->key; a->key = temp;
  182.     temp = b->data; b->data = a->data; a->data = temp;
  183. }
  185. static inline BSTreeNode *BSTree_node_delete(BSTree *map, BSTreeNode *node, void *key)
  186. {
  187.     int cmp = map->compare(node->key, key);
  189.     if(cmp < 0) {
  190.         if(node->left) {
  191.             return BSTree_node_delete(map, node->left, key);
  192.         } else {
  193.             // not found
  194.             return NULL;
  195.         }
  196.     } else if(cmp > 0) {
  197.         if(node->right) {
  198.             return BSTree_node_delete(map, node->right, key);
  199.         } else {
  200.             // not found
  201.             return NULL;
  202.         }
  203.     } else {
  204.         if(node->left && node->right) {
  205.             // swap this node for the smallest node that is bigger than us
  206.             BSTreeNode *successor = BSTree_find_min(node->right);
  207.             BSTree_swap(successor, node);
  209.             // this leaves the old successor with possibly a right child
  210.             // so replace it with that right child
  211.             BSTree_replace_node_in_parent(map, successor, successor->right);
  213.             // finally it's swapped, so return successor instead of node
  214.             return successor;
  215.         } else if(node->left) {
  216.             BSTree_replace_node_in_parent(map, node, node->left);
  217.         } else if(node->right) {
  218.             BSTree_replace_node_in_parent(map, node, node->right);
  219.         } else {
  220.             BSTree_replace_node_in_parent(map, node, NULL);
  221.         }
  223.         return node;
  224.     }
  225. }
  227. void *BSTree_delete(BSTree *map, void *key)
  228. {
  229.     void *data = NULL;
  231.     if(map->root) {
  232.         BSTreeNode *node = BSTree_node_delete(map, map->root, key);
  234.         if(node) {
  235.             data = node->data;
  236.             free(node);
  237.         }
  238.     }
  240.     return data;
  241. }

在讲解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。

最后，你可以查看它的单元测试以及测试方法：

  1. #include "minunit.h"
  2. #include <lcthw/bstree.h>
  3. #include <assert.h>
  4. #include <lcthw/bstrlib.h>
  5. #include <stdlib.h>
  6. #include <time.h>
  8. BSTree *map = NULL;
  9. static int traverse_called = 0;
  10. struct tagbstring test1 = bsStatic("test data 1");
  11. struct tagbstring test2 = bsStatic("test data 2");
  12. struct tagbstring test3 = bsStatic("xest data 3");
  13. struct tagbstring expect1 = bsStatic("THE VALUE 1");
  14. struct tagbstring expect2 = bsStatic("THE VALUE 2");
  15. struct tagbstring expect3 = bsStatic("THE VALUE 3");
  17. static int traverse_good_cb(BSTreeNode *node)
  18. {
  19.     debug("KEY: %s", bdata((bstring)node->key));
  20.     traverse_called++;
  21.     return 0;
  22. }
  25. static int traverse_fail_cb(BSTreeNode *node)
  26. {
  27.     debug("KEY: %s", bdata((bstring)node->key));
  28.     traverse_called++;
  30.     if(traverse_called == 2) {
  31.         return 1;
  32.     } else {
  33.         return 0;
  34.     }
  35. }
  38. char *test_create()
  39. {
  40.     map = BSTree_create(NULL);
  41.     mu_assert(map != NULL, "Failed to create map.");
  43.     return NULL;
  44. }
  46. char *test_destroy()
  47. {
  48.     BSTree_destroy(map);
  50.     return NULL;
  51. }
  54. char *test_get_set()
  55. {
  56.     int rc = BSTree_set(map, &test1, &expect1);
  57.     mu_assert(rc == 0, "Failed to set &test1");
  58.     bstring result = BSTree_get(map, &test1);
  59.     mu_assert(result == &expect1, "Wrong value for test1.");
  61.     rc = BSTree_set(map, &test2, &expect2);
  62.     mu_assert(rc == 0, "Failed to set test2");
  63.     result = BSTree_get(map, &test2);
  64.     mu_assert(result == &expect2, "Wrong value for test2.");
  66.     rc = BSTree_set(map, &test3, &expect3);
  67.     mu_assert(rc == 0, "Failed to set test3");
  68.     result = BSTree_get(map, &test3);
  69.     mu_assert(result == &expect3, "Wrong value for test3.");
  71.     return NULL;
  72. }
  74. char *test_traverse()
  75. {
  76.     int rc = BSTree_traverse(map, traverse_good_cb);
  77.     mu_assert(rc == 0, "Failed to traverse.");
  78.     mu_assert(traverse_called == 3, "Wrong count traverse.");
  80.     traverse_called = 0;
  81.     rc = BSTree_traverse(map, traverse_fail_cb);
  82.     mu_assert(rc == 1, "Failed to traverse.");
  83.     mu_assert(traverse_called == 2, "Wrong count traverse for fail.");
  85.     return NULL;
  86. }
  88. char *test_delete()
  89. {
  90.     bstring deleted = (bstring)BSTree_delete(map, &test1);
  91.     mu_assert(deleted != NULL, "Got NULL on delete.");
  92.     mu_assert(deleted == &expect1, "Should get test1");
  93.     bstring result = BSTree_get(map, &test1);
  94.     mu_assert(result == NULL, "Should delete.");
  96.     deleted = (bstring)BSTree_delete(map, &test1);
  97.     mu_assert(deleted == NULL, "Should get NULL on delete");
  99.     deleted = (bstring)BSTree_delete(map, &test2);
  100.     mu_assert(deleted != NULL, "Got NULL on delete.");
  101.     mu_assert(deleted == &expect2, "Should get test2");
  102.     result = BSTree_get(map, &test2);
  103.     mu_assert(result == NULL, "Should delete.");
  105.     deleted = (bstring)BSTree_delete(map, &test3);
  106.     mu_assert(deleted != NULL, "Got NULL on delete.");
  107.     mu_assert(deleted == &expect3, "Should get test3");
  108.     result = BSTree_get(map, &test3);
  109.     mu_assert(result == NULL, "Should delete.");
  111.     // test deleting non-existent stuff
  112.     deleted = (bstring)BSTree_delete(map, &test3);
  113.     mu_assert(deleted == NULL, "Should get NULL");
  115.     return NULL;
  116. }
  118. char *test_fuzzing()
  119. {
  120.     BSTree *store = BSTree_create(NULL);
  121.     int i = 0;
  122.     int j = 0;
  123.     bstring numbers[100] = {NULL};
  124.     bstring data[100] = {NULL};
  125.     srand((unsigned int)time(NULL));
  127.     for(i = 0; i < 100; i++) {
  128.         int num = rand();
  129.         numbers[i] = bformat("%d", num);
  130.         data[i] = bformat("data %d", num);
  131.         BSTree_set(store, numbers[i], data[i]);
  132.     }
  134.     for(i = 0; i < 100; i++) {
  135.         bstring value = BSTree_delete(store, numbers[i]);
  136.         mu_assert(value == data[i], "Failed to delete the right number.");
  138.         mu_assert(BSTree_delete(store, numbers[i]) == NULL, "Should get nothing.");
  140.         for(j = i+1; j < 99 - i; j++) {
  141.             bstring value = BSTree_get(store, numbers[j]);
  142.             mu_assert(value == data[j], "Failed to get the right number.");
  143.         }
  145.         bdestroy(value);
  146.         bdestroy(numbers[i]);
  147.     }
  149.     BSTree_destroy(store);
  151.     return NULL;
  152. }
  154. char *all_tests()
  155. {
  156.     mu_suite_start();
  158.     mu_run_test(test_create);
  159.     mu_run_test(test_get_set);
  160.     mu_run_test(test_traverse);
  161.     mu_run_test(test_delete);
  162.     mu_run_test(test_destroy);
  163.     mu_run_test(test_fuzzing);
  165.     return NULL;
  166. }
  168. RUN_TESTS(all_tests);

我要重点讲解test_fuzzing函数，它是针对复杂数据结构的一种有趣的测试技巧。创建一些键来覆盖BSTree_node_delete的所有分支相当困难，而且有可能我会错过一些边界情况。更好的方法就是创建一个“模糊测试”的函数来执行所有操作，并尽可能以一种可怕且随机的方式执行它们。这里我插入了一系列随机字符串的键，之后我删除了它们并试着在删除之后获取它们的值。

这种测试可以避免只测试到你知道能正常工作的部分，这意味着你不会遗漏不知道的事情。通过想你的数据结构插入一些随机的垃圾数据，你可以碰到意料之外的事情，并检测出任何bug。

如何改进

不要完成下列任何习题，因为在下个练习中我会使用这里的单元测试，来教你使用一些性能调优的技巧。在你完成练习41之后，你需要返回来完成这些习题。

  • 像之前一样，你应该执行所有防御性编程检查，并且为不应发生的情况添加assert。例如，你不应该在递归函数中获取到NULL，为此添加断言。
  • 遍历函数按照左子树、右子树和当前节点的顺组进行遍历。你可以创建相反顺序的遍历函数。
  • 每个节点上都会执行完整的字符串比较，但是我可以使用Hashmap的哈希函数来提升速度。我可以计算键的哈希值，在BSTreeNode中储存它。之后在每个创建的函数中，我可以实现计算出键的哈希值，然后在递归中向下传递。我可以使用哈希来很快地比较每个节点，就像Hashmap那样。

附加题

同样，现在先不要完成它们，直到完成练习41，那时你就可以使用Valgrind的性能调优技巧来完成它们了。

  • 有一种不使用递归的替代的方法，也可以操作这个数据结构。维基百科上介绍了不使用递归来完成相同事情的替代方法。这样做会更好还是更糟？
  • 查询你能找到的所有不同的树的相关资料。比如AVL树、红黑树、以及一些非树形结构例如跳转表。