笨办法学C 练习40:二叉搜索树
练习40:二叉搜索树
原文:Exercise 40: Binary Search Trees
译者:飞龙
二叉树是最简单的树形数据结构,虽然它在许多语言中被哈希表取代,但仍旧对于一些应用很实用。二叉树的各种变体可用于一些非常实用东西,比如数据库的索引、搜索算法结构、以及图像处理。
我把我的二叉树叫做BSTree,描述它的最佳方法就是它是另一种Hashmap形式的键值对储存容器。它们的差异在于,哈希表为键计算哈希值来寻找位置,而二叉树将键与树中的节点进行对比,之后深入树中找到储存它的最佳位置,基于它与其它节点的关系。
在我真正解释它的工作原理之前,让我向你展示bstree.h头文件,便于你看到数据结构,之后我会用它来解释如何构建。
# ifndef _lcthw_BSTree_h# define _lcthw_BSTree_htypedef 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,我会遍历左子树,否则是右子树。
重复第三步,直到我到达了没有左子树或右子树的节点,但是这是我需要选择的方向。
我选择了这个方向(左或者右)来放置新的节点,并且将这个新节点的父节点设为我来时的上一个节点。当我删除它时,我会使用它的父节点。
这也解释了它如何工作。如果寻找一个节点涉及到按照键的对比来遍历左子树或右子树,那么设置一个节点涉及到相同的事情,直到我找到了一个位置,可以在其左子树或右子树上放置新的节点。
花一些时间在纸上画出一些树并且遍历一些节点来进行查找或设置,你就可以理解它如何工作。之后你要准备好来看一看实现,我在其中解释了删除操作。删除一个节点非常麻烦,因此它最适合逐行的代码分解。
# include # include # include # include 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 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 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 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。
最后,你可以查看它的单元测试以及测试方法:
# include "minunit.h"# include # include # include # include # include 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 test_fuzzing函数,它是针对复杂数据结构的一种有趣的测试技巧。创建一些键来覆盖BSTree_node_delete的所有分支相当困难,而且有可能我会错过一些边界情况。更好的方法就是创建一个“模糊测试”的函数来执行所有操作,并尽可能以一种可怕且随机的方式执行它们。这里我插入了一系列随机字符串的键,之后我删除了它们并试着在删除之后获取它们的值。这种测试可以避免只测试到你知道能正常工作的部分,这意味着你不会遗漏不知道的事情。通过想你的数据结构插入一些随机的垃圾数据,你可以碰到意料之外的事情,并检测出任何bug。## 如何改进不要完成下列任何习题,因为在下个练习中我会使用这里的单元测试,来教你使用一些性能调优的技巧。在你完成练习41之后,你需要返回来完成这些习题。1. 像之前一样,你应该执行所有防御性编程检查,并且为不应发生的情况添加assert。例如,你不应该在递归函数中获取到NULL,为此添加断言。1. 遍历函数按照左子树、右子树和当前节点的顺组进行遍历。你可以创建相反顺序的遍历函数。1. 每个节点上都会执行完整的字符串比较,但是我可以使用Hashmap的哈希函数来提升速度。我可以计算键的哈希值,在BSTreeNode中储存它。之后在每个创建的函数中,我可以实现计算出键的哈希值,然后在递归中向下传递。我可以使用哈希来很快地比较每个节点,就像Hashmap那样。## 附加题同样,现在先不要完成它们,直到完成练习41,那时你就可以使用Valgrind的性能调优技巧来完成它们了。1. 有一种不使用递归的替代的方法,也可以操作这个数据结构。维基百科上介绍了不使用递归来完成相同事情的替代方法。这样做会更好还是更糟?1. 查询你能找到的所有不同的树的相关资料。比如AVL树、红黑树、以及一些非树形结构例如跳转表。#c、lxthw#
版权声明
本文来自互联网用户投稿,文章观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符,请点击 举报 进行投诉反馈!