21 December 2016

字典树,英文名字是 trie,也叫前缀树。主要是用于查找某个单词是否存在。

事实上,我认为大部分的数据结构很难学,都是写代码的人写得好难看(垃圾)。如果在你知道这个数据结构大概是干嘛的情况下,再看一些优秀的 代码/伪代码,自己也可以很方便地写出代码。

来看看具体字典树是怎么工作的:(图片来自维基百科)

假设我们要查找, tea 这个单词,我们首先看看 t 在不在这棵树上,发现 t 确实在,顺着树继续向下,我们找到了 e,再接着找到了 a。结果我们确定 tea 确实存在。

再根据这幅图,假设我们要查找 hello 这个单词呢,我们还是顺着树往下找,h 一开始就不在,可以确定不在 hello 不存在。

另外需要注意的是,顺着这棵树找,存在就一定存在吗?答案是不是的。虽然有点绕,但是想想我们现在要查找 te 这个单词在不在这棵树上,从 t 再到 e,我们确实找到了他们都在树上,但是呢,因为 e 这个点上,没有一个终止符号, te 只是 tea 这个单词的一部分,不算一个单词。

假如,我们现在需要再往树上插入单词 testte ,那么这棵树就变成下面这副模样了(标红表示这里是一个单词终止符号)。

现在应该大概知道 trie 树是来干嘛的了。接下来看看代码是如何实现的,首先,看看这个结构体

struct node {
    int count;
    char data;
    struct node *child[26];
};

树上的每个节点都用如下的结构体表示:

  • count 表示当前这个节点是否是一个终止符号,默认是 0,表示不是
  • data 表示当前的节点存储的是那个字符
  • 这个节点下面连接了 26 个子节点 (child[26])
void insert(struct node *root, const char *str, int len) {
    for (int i = 0; i < len; i++) {
        int index      = str[i] - 'a';
        struct node *p = root->child[index];

        if (p == NULL) {
            p = (struct node *) malloc (sizeof(struct node));
            p->count = 0;
            p->data  = str[i];

            root->child[index] = p;
        }

        if (i+1 == len) {  // 到达了字符串的最后一个字符
            p->count++;    // count + 1,表示这是一个终止符号
        }

        root = root->child[index];
    }
}

int find(struct node *root, const char *str, int len) {
    int i;

    struct node *p = root;
    for (i = 0; i < len; i++) {
        int index = str[i] - 'a';
        p = p->child[index];
        if (p == NULL) {
            return -1;          /* not found */
        }
    }

    if (i == len && p->count != 0) {
        return p->count;
    }
    return -1;                  /* not found */
}

int main() {
    struct node root;

    memset(&root, 0, sizeof(root));
    root.data = ' ';

    insert(&root, "hello", strlen("hello"));

    printf("%d\n", find(&root, "abc", 3));

    return 0;
}