練習(xí)46：三叉搜索樹(shù)

原文：Exercise 46: Ternary Search Tree

譯者：飛龍

我打算向你介紹的最后一種數(shù)據(jù)結(jié)構(gòu)就是三叉搜索樹(shù)（TSTree），它和BSTree很像况凉，除了它有三個(gè)分支，low籽慢、equal和high。它的用法和BStree以及Hashmap基本相同，用于儲(chǔ)存鍵值對(duì)的數(shù)據(jù)舌劳，但是它通過(guò)鍵中的獨(dú)立字符來(lái)控制竣贪。這使得TSTree具有一些BStree和Hashmap不具備的功能军洼。

TSTree的工作方式是，每個(gè)鍵都是字符串演怎，根據(jù)字符串中字符的等性匕争，通過(guò)構(gòu)建或者遍歷一棵樹(shù)來(lái)進(jìn)行插入。首先由根節(jié)點(diǎn)開(kāi)始爷耀，觀察每個(gè)節(jié)點(diǎn)的字符甘桑，如果小于、等于或大于則去往相應(yīng)的方向歹叮。你可以參考這個(gè)頭文件：

#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

樹(shù)中該節(jié)點(diǎn)的字符跑杭。

low

小于splitchar的分支。

equal

等于splitchar的分支咆耿。

high

大于splitchar的分支德谅。

value

這個(gè)節(jié)點(diǎn)上符合當(dāng)前splitchar的值的集合。

你可以看到這個(gè)實(shí)現(xiàn)中含有下列操作：

search

為特定key尋找值的典型操作萨螺。

search_prefix

尋找第一個(gè)以key為前綴的值窄做，這是你不能輕易使用BSTree 或 Hashmap 完成的操作愧驱。

insert

將key根據(jù)每個(gè)字符拆分，并把它插入到樹(shù)中椭盏。

traverse

遍歷整顆樹(shù)组砚，使你能夠收集或分析所包含的所有鍵和值。

唯一缺少的操作就是TSTree_delete掏颊，這是因?yàn)樗且粋€(gè)開(kāi)銷很大的操作惫确，比BSTree_delete大得多。當(dāng)我使用TSTree結(jié)構(gòu)時(shí)蚯舱，我將它們視為常量數(shù)據(jù)改化，我打算遍歷許多次，但是永遠(yuǎn)不會(huì)移除任何東西枉昏。它們對(duì)于這樣的操作會(huì)很快陈肛，但是不適于需要快速插入或刪除的情況。為此我會(huì)使用Hashmap因?yàn)樗捎?code>BSTree和TSTree兄裂。

TSTree的實(shí)現(xiàn)非常簡(jiǎn)單句旱，但是第一次可能難以理解。我會(huì)在你讀完之后拆分它晰奖。

#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);
}

對(duì)于TSTree_insert谈撒，我使用了相同模式的遞歸結(jié)構(gòu)，其中我創(chuàng)建了一個(gè)小型函數(shù)匾南，它調(diào)用真正的遞歸函數(shù)啃匿。我對(duì)此并不做任何檢查，但是你應(yīng)該為之添加通常的防御性編程策略蛆楞。要記住的一件事溯乒，就是它使用了一些不同的設(shè)計(jì)，這里并沒(méi)有單獨(dú)的TSTree_create函數(shù)豹爹，如果你將node傳入為NULL裆悄，它會(huì)新建一個(gè)，然后返回最終的值臂聋。

這意味著我需要為你分解TSTree_insert_base光稼，使你理解插入操作。

tstree.c:10-18

像我提到的那樣孩等，如果函數(shù)接收到NULL艾君，我需要?jiǎng)?chuàng)建節(jié)點(diǎn)，并且將*key（當(dāng)前字符）賦值給它瞎访。這用于當(dāng)我插入鍵時(shí)來(lái)構(gòu)建樹(shù)腻贰。

tstree.c:20-21

當(dāng)*key小于splitchar時(shí)，選擇low分支扒秸。

tstree.c:22

如果splitchar相等播演，我就要進(jìn)一步確定等性冀瓦。這會(huì)在我剛剛創(chuàng)建這個(gè)節(jié)點(diǎn)時(shí)發(fā)生，所以這里我會(huì)構(gòu)建這棵樹(shù)写烤。

tstree.c:23-24

仍然有字符串需要處理翼闽，所以向下遞歸equal分支，并且移動(dòng)到下一個(gè)*key字符洲炊。

tstree.c:26-27

這是最后一個(gè)字符的情況感局，所以我將值設(shè)置好。我編寫(xiě)了一個(gè)assert來(lái)避免重復(fù)暂衡。

tstree.c:29-30

最后的情況是*key大于splitchar询微，所以我需要向下遞歸high分支。

這個(gè)數(shù)據(jù)結(jié)構(gòu)的key實(shí)際上帶有一些特性狂巢，我只會(huì)在splitchar相等時(shí)遞增所要分析的字符撑毛。其它兩種情況我只會(huì)繼續(xù)遍歷整個(gè)樹(shù)，直到碰到了相等的字符唧领，我才會(huì)遞歸處理下一個(gè)字符藻雌。這一操作使它對(duì)于找不到鍵的情況是非常快的斩个。我可以傳入一個(gè)不存在的鍵胯杭，簡(jiǎn)單地遍歷一些high和low節(jié)點(diǎn)，直到我碰到了末尾并且知道這個(gè)鍵不存在受啥。我并不需要處理鍵的每個(gè)字符做个，或者樹(shù)的每個(gè)節(jié)點(diǎn)。

一旦你理解了這些腔呜，之后來(lái)分析TSTree_search如何工作：

tstree.c:46

我并不需要遞歸處理整棵樹(shù)叁温，只需要使用使用while循環(huán)和當(dāng)前的node節(jié)點(diǎn)。

tstree.c:47-48

如果當(dāng)前字符小于節(jié)點(diǎn)中的splitchar核畴，則選擇low分支。

tstree.c:49-51

如果相等冲九，自增i并且選擇equal分支谤草，只要不是最后一個(gè)字符。這就是if(i < len)所做的莺奸，使我不會(huì)越過(guò)最后的value丑孩。

tstree.c:52-53

否則我會(huì)選擇high分支，由于當(dāng)前字符更大灭贷。

tstree.c:57-61

循環(huán)結(jié)束后如果node不為空温学，那么返回它的value，否則返回NULL甚疟。

這并不難以理解仗岖，并且你可以看到TSTree_search_prefix函數(shù)用了幾乎相同的算法逃延。唯一的不同就是我并不試著尋找精確的匹配，而是可找到的最長(zhǎng)前綴轧拄。我在相等時(shí)跟蹤last節(jié)點(diǎn)來(lái)實(shí)現(xiàn)它揽祥，并且在搜索循環(huán)結(jié)束之后，遍歷這個(gè)節(jié)點(diǎn)直到發(fā)現(xiàn)value檩电。

觀察TSTree_search_prefix拄丰，你就會(huì)開(kāi)始明白TSTree相對(duì)BSTree 和 Hashmap在查找操作上的另一個(gè)優(yōu)點(diǎn)。給定一個(gè)長(zhǎng)度為X的鍵俐末，你可以在X步內(nèi)找到任何鍵料按，但是也可以在X步加上額外的N步內(nèi)找到第一個(gè)前綴，取決于匹配的鍵有多長(zhǎng)卓箫。如果樹(shù)中最長(zhǎng)的鍵是十個(gè)字符站绪，那么你就可以在10步之內(nèi)找到任意的前綴。更重要的是丽柿，你可以通過(guò)對(duì)鍵的每個(gè)字符只比較一次來(lái)實(shí)現(xiàn)恢准。

相比之下，使用BSTree執(zhí)行相同操作甫题，你需要在BSTree的每一個(gè)可能匹配的節(jié)點(diǎn)中檢查兩個(gè)字符串是否有共同的前綴馁筐。這對(duì)于尋找鍵，或者檢查鍵是否存在（TSTree_search）是相同的坠非。你需要將每個(gè)字符與BSTree中的大多數(shù)字符對(duì)比敏沉，來(lái)確認(rèn)是否匹配。

Hashamp對(duì)于尋找前綴更加糟糕炎码，因?yàn)槟悴荒軌騼H僅計(jì)算前綴的哈希值盟迟。你基本上不能高效在Hashmap中實(shí)現(xiàn)它，除非數(shù)據(jù)類似URL可以被解析潦闲。即使這樣你還是需要遍歷Hashmap的所有節(jié)點(diǎn)攒菠。

譯者注：二叉樹(shù)和三叉樹(shù)在搜索時(shí)都是走其中的一支，但由于二叉樹(shù)中每個(gè)節(jié)點(diǎn)儲(chǔ)存字符串歉闰，而三叉樹(shù)儲(chǔ)存的是字符辖众。所以三叉樹(shù)的整個(gè)搜索過(guò)程相當(dāng)于一次字符串比較，而二叉樹(shù)的每個(gè)節(jié)點(diǎn)都需要一次字符串比較和敬。三叉樹(shù)堆疊儲(chǔ)存字符串使搜索起來(lái)更方便凹炸。

至于哈希表，由于字符串整體和前綴計(jì)算出來(lái)的哈希值差別很大昼弟，所以按前綴搜索時(shí)啤它，哈希的優(yōu)勢(shì)完全失效，所以只能改為暴力搜索，效果比二叉樹(shù)還要差变骡。

最后的兩個(gè)函數(shù)應(yīng)該易于分析离赫，因?yàn)樗鼈兪堑湫偷谋闅v和銷毀操作，你已經(jīng)在其它數(shù)據(jù)結(jié)構(gòu)中看到過(guò)了锣光。

最后笆怠，我編寫(xiě)了簡(jiǎn)單的單元測(cè)試，來(lái)確保我所做的全部東西正確誊爹。

#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);

優(yōu)點(diǎn)和缺點(diǎn)

TSTree可以用于實(shí)現(xiàn)一些其它實(shí)用的事情：

• 除了尋找前綴蹬刷，你可以反轉(zhuǎn)插入的所有鍵，之后通過(guò)后綴來(lái)尋找频丘。我使用它來(lái)尋找主機(jī)名稱办成，因?yàn)槲蚁胍业?code>*.learncodethehardway.com，所以如果我反向來(lái)尋找搂漠，會(huì)更快匹配到它們迂卢。
• 你可以執(zhí)行“模糊”搜索，其中你可以收集所有與鍵的大多數(shù)字符相似的節(jié)點(diǎn)桐汤，或者使用其它算法用于搜索近似的匹配而克。
• 你可以尋找所有中間帶有特定部分的鍵。

我已經(jīng)談?wù)摿?code>TSTree能做的一些事情怔毛，但是它們并不總是最好的數(shù)據(jù)結(jié)構(gòu)员萍。TSTree的缺點(diǎn)在于：

• 像我提到過(guò)的那樣，刪除操作非常麻煩拣度。它們適用于需要快速檢索并且從不移除的操作碎绎。如果你需要?jiǎng)h除，可以簡(jiǎn)單地將value置空抗果，之后當(dāng)樹(shù)過(guò)大時(shí)周期性重構(gòu)它筋帖。
• 與BSTree和Hashmap相比，它在相同的鍵上使用了大量的空間冤馏。它對(duì)于鍵中的每個(gè)字符都使用了完整的節(jié)點(diǎn)日麸。它對(duì)于短的鍵效果更好，但如果你在TSTree中放入一大堆東西宿接，它會(huì)變得很大赘淮。
• 它們也不適合處理非常長(zhǎng)的鍵，然而“長(zhǎng)”是主觀的詞睦霎，所以應(yīng)當(dāng)像通常一樣先進(jìn)行測(cè)試。如果你嘗試儲(chǔ)存一萬(wàn)個(gè)字符的鍵走诞，那么應(yīng)當(dāng)使用Hashmap副女。

如何改進(jìn)

像通常一樣，瀏覽代碼蚣旱，使用防御性的先決條件碑幅、斷言戴陡，并且檢查每個(gè)函數(shù)來(lái)改進(jìn)。下面是一些其他的改進(jìn)方案沟涨，但是你并不需要全部實(shí)現(xiàn)它們：

• 你可以使用DArray來(lái)允許重復(fù)的value值恤批。
• 因?yàn)槲姨岬絼h除非常困難，但是你可以通過(guò)將值設(shè)為NULL來(lái)模擬裹赴，使值能夠高效被刪除喜庞。
• 目前還不能獲取到所有匹配指定前綴的值，我會(huì)讓你在附加題中實(shí)現(xiàn)它棋返。
• 有一些其他得更復(fù)雜的算法會(huì)比它要好延都。查詢前綴數(shù)組、前綴樹(shù)和基數(shù)樹(shù)的資料睛竣。

附加題

• 實(shí)現(xiàn)TSTree_collect返回DArray包含所有匹配指定前綴的鍵晰房。
• 實(shí)現(xiàn)TSTree_search_suffix和TSTree_insert_suffix，實(shí)現(xiàn)后綴搜索和插入射沟。
• 使用valgrind來(lái)查看與BSTree 和 Hashmap相比殊者，這個(gè)結(jié)構(gòu)使用了多少內(nèi)存來(lái)儲(chǔ)存數(shù)據(jù)。