# 練習46：三叉搜索樹 > 原文：[Exercise 46: Ternary Search Tree](http://c.learncodethehardway.org/book/ex46.html) > 譯者：[飛龍](https://github.com/wizardforcel) 我打算向你介紹的最后一種數據結構就是三叉搜索樹（`TSTree`），它和`BSTree`很像，除了它有三個分支，`low`、`equal`和`high`。它的用法和`BStree`以及`Hashmap`基本相同，用于儲存鍵值對的數據，但是它通過鍵中的獨立字符來控制。這使得`TSTree`具有一些`BStree`和`Hashmap`不具備的功能。 `TSTree`的工作方式是，每個鍵都是字符串，根據字符串中字符的等性，通過構建或者遍歷一棵樹來進行插入。首先由根節點開始，觀察每個節點的字符，如果小于、等于或大于則去往相應的方向。你可以參考這個頭文件： ```c #ifndef _lcthw_TSTree_h #define _lctwh_TSTree_h #include <stdlib.h> #include <lcthw/darray.h> typedef struct TSTree { char splitchar; struct TSTree *low; struct TSTree *equal; struct TSTree *high; void *value; } TSTree; void *TSTree_search(TSTree *root, const char *key, size_t len); void *TSTree_search_prefix(TSTree *root, const char *key, size_t len); typedef void (*TSTree_traverse_cb)(void *value, void *data); TSTree *TSTree_insert(TSTree *node, const char *key, size_t len, void *value); void TSTree_traverse(TSTree *node, TSTree_traverse_cb cb, void *data); void TSTree_destroy(TSTree *root); #endif ``` `TSTree`擁有下列成員： splitchar 樹中該節點的字符。 low 小于`splitchar`的分支。 equal 等于`splitchar`的分支。 high 大于`splitchar`的分支。 value 這個節點上符合當前`splitchar`的值的集合。 你可以看到這個實現中含有下列操作： search 為特定`key`尋找值的典型操作。 search_prefix 尋找第一個以`key`為前綴的值，這是你不能輕易使用`BSTree` 或 `Hashmap` 完成的操作。 insert 將`key`根據每個字符拆分，并把它插入到樹中。 traverse 遍歷整顆樹，使你能夠收集或分析所包含的所有鍵和值。 唯一缺少的操作就是`TSTree_delete`，這是因為它是一個開銷很大的操作，比`BSTree_delete`大得多。當我使用`TSTree`結構時，我將它們視為常量數據，我打算遍歷許多次，但是永遠不會移除任何東西。它們對于這樣的操作會很快，但是不適于需要快速插入或刪除的情況。為此我會使用`Hashmap`因為它優于`BSTree`和`TSTree`。 `TSTree`的實現非常簡單，但是第一次可能難以理解。我會在你讀完之后拆分它。 ```c #include <stdlib.h> #include <stdio.h> #include <assert.h> #include <lcthw/dbg.h> #include <lcthw/tstree.h> static inline TSTree *TSTree_insert_base(TSTree *root, TSTree *node, const char *key, size_t len, void *value) { if(node == NULL) { node = (TSTree *) calloc(1, sizeof(TSTree)); if(root == NULL) { root = node; } node->splitchar = *key; } if(*key < node->splitchar) { node->low = TSTree_insert_base(root, node->low, key, len, value); } else if(*key == node->splitchar) { if(len > 1) { node->equal = TSTree_insert_base(root, node->equal, key+1, len - 1, value); } else { assert(node->value == NULL && "Duplicate insert into tst."); node->value = value; } } else { node->high = TSTree_insert_base(root, node->high, key, len, value); } return node; } TSTree *TSTree_insert(TSTree *node, const char *key, size_t len, void *value) { return TSTree_insert_base(node, node, key, len, value); } void *TSTree_search(TSTree *root, const char *key, size_t len) { TSTree *node = root; size_t i = 0; while(i < len && node) { if(key[i] < node->splitchar) { node = node->low; } else if(key[i] == node->splitchar) { i++; if(i < len) node = node->equal; } else { node = node->high; } } if(node) { return node->value; } else { return NULL; } } void *TSTree_search_prefix(TSTree *root, const char *key, size_t len) { if(len == 0) return NULL; TSTree *node = root; TSTree *last = NULL; size_t i = 0; while(i < len && node) { if(key[i] < node->splitchar) { node = node->low; } else if(key[i] == node->splitchar) { i++; if(i < len) { if(node->value) last = node; node = node->equal; } } else { node = node->high; } } node = node ? node : last; // traverse until we find the first value in the equal chain // this is then the first node with this prefix while(node && !node->value) { node = node->equal; } return node ? node->value : NULL; } void TSTree_traverse(TSTree *node, TSTree_traverse_cb cb, void *data) { if(!node) return; if(node->low) TSTree_traverse(node->low, cb, data); if(node->equal) { TSTree_traverse(node->equal, cb, data); } if(node->high) TSTree_traverse(node->high, cb, data); if(node->value) cb(node->value, data); } void TSTree_destroy(TSTree *node) { if(node == NULL) return; if(node->low) TSTree_destroy(node->low); if(node->equal) { TSTree_destroy(node->equal); } if(node->high) TSTree_destroy(node->high); free(node); } ``` 對于`TSTree_insert`，我使用了相同模式的遞歸結構，其中我創建了一個小型函數，它調用真正的遞歸函數。我對此并不做任何檢查，但是你應該為之添加通常的防御性編程策略。要記住的一件事，就是它使用了一些不同的設計，這里并沒有單獨的`TSTree_create`函數，如果你將`node`傳入為`NULL`，它會新建一個，然后返回最終的值。 這意味著我需要為你分解`TSTree_insert_base`，使你理解插入操作。 tstree.c:10-18 像我提到的那樣，如果函數接收到`NULL`，我需要創建節點，并且將`*key`（當前字符）賦值給它。這用于當我插入鍵時來構建樹。 tstree.c:20-21 當`*key`小于`splitchar`時，選擇`low`分支。 tstree.c:22 如果`splitchar`相等，我就要進一步確定等性。這會在我剛剛創建這個節點時發生，所以這里我會構建這棵樹。 tstree.c:23-24 仍然有字符串需要處理，所以向下遞歸`equal`分支，并且移動到下一個`*key`字符。 tstree.c:26-27 這是最后一個字符的情況，所以我將值設置好。我編寫了一個`assert`來避免重復。 tstree.c:29-30 最后的情況是`*key`大于`splitchar`，所以我需要向下遞歸`high`分支。 這個數據結構的`key`實際上帶有一些特性，我只會在`splitchar`相等時遞增所要分析的字符。其它兩種情況我只會繼續遍歷整個樹，直到碰到了相等的字符，我才會遞歸處理下一個字符。這一操作使它對于找不到鍵的情況是非常快的。我可以傳入一個不存在的鍵，簡單地遍歷一些`high`和`low`節點，直到我碰到了末尾并且知道這個鍵不存在。我并不需要處理鍵的每個字符，或者樹的每個節點。 一旦你理解了這些，之后來分析`TSTree_search`如何工作： tstree.c:46 我并不需要遞歸處理整棵樹，只需要使用`while`循環和當前的`node`節點。 tstree.c:47-48 如果當前字符小于節點中的`splitchar`，則選擇`low`分支。 tstree.c:49-51 如果相等，自增`i`并且選擇`equal`分支，只要不是最后一個字符。這就是`if(i < len)`所做的，使我不會越過最后的`value`。 tstree.c:52-53 否則我會選擇`high`分支，由于當前字符更大。 tstree.c:57-61 循環結束后如果`node`不為空，那么返回它的`value`，否則返回`NULL`。 這并不難以理解，并且你可以看到`TSTree_search_prefix`函數用了幾乎相同的算法。唯一的不同就是我并不試著尋找精確的匹配，而是可找到的最長前綴。我在相等時跟蹤`last`節點來實現它，并且在搜索循環結束之后，遍歷這個節點直到發現`value`。 觀察`TSTree_search_prefix`，你就會開始明白`TSTree`相對`BSTree` 和 `Hashmap`在查找操作上的另一個優點。給定一個長度為X的鍵，你可以在X步內找到任何鍵，但是也可以在X步加上額外的N步內找到第一個前綴，取決于匹配的鍵有多長。如果樹中最長的鍵是十個字符，那么你就可以在10步之內找到任意的前綴。更重要的是，你可以通過對鍵的每個字符只比較一次來實現。 相比之下，使用`BSTree`執行相同操作，你需要在`BSTree`的每一個可能匹配的節點中檢查兩個字符串是否有共同的前綴。這對于尋找鍵，或者檢查鍵是否存在（`TSTree_search`）是相同的。你需要將每個字符與`BSTree`中的大多數字符對比，來確認是否匹配。 `Hashamp`對于尋找前綴更加糟糕，因為你不能夠僅僅計算前綴的哈希值。你基本上不能高效在`Hashmap`中實現它，除非數據類似URL可以被解析。即使這樣你還是需要遍歷`Hashmap`的所有節點。 > 譯者注：二叉樹和三叉樹在搜索時都是走其中的一支，但由于二叉樹中每個節點儲存字符串，而三叉樹儲存的是字符。所以三叉樹的整個搜索過程相當于一次字符串比較，而二叉樹的每個節點都需要一次字符串比較。三叉樹堆疊儲存字符串使搜索起來更方便。 > 至于哈希表，由于字符串整體和前綴計算出來的哈希值差別很大，所以按前綴搜索時，哈希的優勢完全失效，所以只能改為暴力搜索，效果比二叉樹還要差。 最后的兩個函數應該易于分析，因為它們是典型的遍歷和銷毀操作，你已經在其它數據結構中看到過了。 最后，我編寫了簡單的單元測試，來確保我所做的全部東西正確。 ```c #include "minunit.h" #include <lcthw/tstree.h> #include <string.h> #include <assert.h> #include <lcthw/bstrlib.h> TSTree *node = NULL; char *valueA = "VALUEA"; char *valueB = "VALUEB"; char *value2 = "VALUE2"; char *value4 = "VALUE4"; char *reverse = "VALUER"; int traverse_count = 0; struct tagbstring test1 = bsStatic("TEST"); struct tagbstring test2 = bsStatic("TEST2"); struct tagbstring test3 = bsStatic("TSET"); struct tagbstring test4 = bsStatic("T"); char *test_insert() { node = TSTree_insert(node, bdata(&test1), blength(&test1), valueA); mu_assert(node != NULL, "Failed to insert into tst."); node = TSTree_insert(node, bdata(&test2), blength(&test2), value2); mu_assert(node != NULL, "Failed to insert into tst with second name."); node = TSTree_insert(node, bdata(&test3), blength(&test3), reverse); mu_assert(node != NULL, "Failed to insert into tst with reverse name."); node = TSTree_insert(node, bdata(&test4), blength(&test4), value4); mu_assert(node != NULL, "Failed to insert into tst with second name."); return NULL; } char *test_search_exact() { // tst returns the last one inserted void *res = TSTree_search(node, bdata(&test1), blength(&test1)); mu_assert(res == valueA, "Got the wrong value back, should get A not B."); // tst does not find if not exact res = TSTree_search(node, "TESTNO", strlen("TESTNO")); mu_assert(res == NULL, "Should not find anything."); return NULL; } char *test_search_prefix() { void *res = TSTree_search_prefix(node, bdata(&test1), blength(&test1)); debug("result: %p, expected: %p", res, valueA); mu_assert(res == valueA, "Got wrong valueA by prefix."); res = TSTree_search_prefix(node, bdata(&test1), 1); debug("result: %p, expected: %p", res, valueA); mu_assert(res == value4, "Got wrong value4 for prefix of 1."); res = TSTree_search_prefix(node, "TE", strlen("TE")); mu_assert(res != NULL, "Should find for short prefix."); res = TSTree_search_prefix(node, "TE--", strlen("TE--")); mu_assert(res != NULL, "Should find for partial prefix."); return NULL; } void TSTree_traverse_test_cb(void *value, void *data) { assert(value != NULL && "Should not get NULL value."); assert(data == valueA && "Expecting valueA as the data."); traverse_count++; } char *test_traverse() { traverse_count = 0; TSTree_traverse(node, TSTree_traverse_test_cb, valueA); debug("traverse count is: %d", traverse_count); mu_assert(traverse_count == 4, "Didn't find 4 keys."); return NULL; } char *test_destroy() { TSTree_destroy(node); return NULL; } char * all_tests() { mu_suite_start(); mu_run_test(test_insert); mu_run_test(test_search_exact); mu_run_test(test_search_prefix); mu_run_test(test_traverse); mu_run_test(test_destroy); return NULL; } RUN_TESTS(all_tests); ``` ## 優點和缺點 `TSTree`可以用于實現一些其它實用的事情： + 除了尋找前綴，你可以反轉插入的所有鍵，之后通過后綴來尋找。我使用它來尋找主機名稱，因為我想要找到`*.learncodethehardway.com`，所以如果我反向來尋找，會更快匹配到它們。 + 你可以執行“模糊”搜索，其中你可以收集所有與鍵的大多數字符相似的節點，或者使用其它算法用于搜索近似的匹配。 + 你可以尋找所有中間帶有特定部分的鍵。 我已經談論了`TSTree`能做的一些事情，但是它們并不總是最好的數據結構。`TSTree`的缺點在于： + 像我提到過的那樣，刪除操作非常麻煩。它們適用于需要快速檢索并且從不移除的操作。如果你需要刪除，可以簡單地將`value`置空，之后當樹過大時周期性重構它。 + 與`BSTree`和`Hashmap`相比，它在相同的鍵上使用了大量的空間。它對于鍵中的每個字符都使用了完整的節點。它對于短的鍵效果更好，但如果你在`TSTree`中放入一大堆東西，它會變得很大。 + 它們也不適合處理非常長的鍵，然而“長”是主觀的詞，所以應當像通常一樣先進行測試。如果你嘗試儲存一萬個字符的鍵，那么應當使用`Hashmap`。 ## 如何改進 像通常一樣，瀏覽代碼，使用防御性的先決條件、斷言，并且檢查每個函數來改進。下面是一些其他的改進方案，但是你并不需要全部實現它們： + 你可以使用`DArray`來允許重復的`value`值。 + 因為我提到刪除非常困難，但是你可以通過將值設為`NULL`來模擬，使值能夠高效被刪除。 + 目前還不能獲取到所有匹配指定前綴的值，我會讓你在附加題中實現它。 + 有一些其他得更復雜的算法會比它要好。查詢前綴數組、前綴樹和基數樹的資料。 ## 附加題 + 實現`TSTree_collect`返回`DArray`包含所有匹配指定前綴的鍵。 + 實現`TSTree_search_suffix`和`TSTree_insert_suffix`，實現后綴搜索和插入。 + 使用`valgrind`來查看與`BSTree` 和 `Hashmap`相比，這個結構使用了多少內存來儲存數據。