Trie的麻烦

Question

因此，我正在尝试阅读Trie，对我来说，这是一种相对较新的数据结构。在我读到的任何地方，trie中的每个节点都由一个整数变量组成，该变量将标记一个单词的结尾，并且还将由26个指针组成，每个指针指向较低级别的节点(假设单词只包含小写字母字符)。

现在我面临的问题是，无论我在哪里看到/读到实现，它们都会用字符标记节点。如下例所示：

http://community.topcoder.com/i/education/alg_tries.png

但在我对Trie的理解中，我认为每一条边都应该被标记为一个字符。不过，我知道我们没有边的数据结构，只有节点的数据结构。但是标记边缘不是更正确吗？

另外，这是我实现插入的算法。如果你发现它有什么问题，请告诉我。

struct trie
{
    int val;
    trie* aplha[26];
}


trie* insert (trie *root, char *inp)
{
    if (*input == '\0')
        return root;

    if (root == NULL)
    {
        root = (trie *) malloc(sizeof(trie));
        int i = 0;
        for (i=0;i<26;i++)
            root->alpha[i] = NULL;
    }

    temp = *input - 'a';
    root->alpha[temp] = insert (root->alpha[temp],input+1);
    if (*(input+1)=='\0')
        root->val = 1;
    return root;
}

我对如何实现delete感到困惑。如果您可以，请帮助我与删除算法。

Answer 1

这里有一个小程序，它展示了一种你可以做到的方法。然而，在错误处理方面并没有投入很大的努力：

http://pastebin.com/84TiPrtL

我稍微编辑了您的trie_insert函数，并在这里显示了一个trie_delete函数。如果您使用的是C++，则可以将粘贴代码中的struct Vec更改为std::vector。

struct trie *trie_insert(struct trie *root, char *input)
{
    int idx;
    if (!input) {
        return root;
    }
    if (root == NULL) {
        root = (struct trie *)calloc(1, sizeof(struct trie));
    }
    if (*input == '\0') {
        // leaves have root->val set to 1
        root->val = 1;
    } else {
        // carry on insertion
        idx = *input - 'a';
        root->alpha[idx] = trie_insert(root->alpha[idx], input+1);
    }
    return root;
}

struct trie *trie_delete(struct trie *root, char *s)
{
    int i, idx, reap = 0;
    if (!root || !s) {
        return root;
    }
    if (!*s && root->val) {
        // delete this string, and mark node as deletable
        root->val = 0;
        reap = 1;
    } else {
        // more characters to insert, carry on
        idx = *s - 'a';
        if (root->alpha[idx]) {
            root->alpha[idx] = trie_delete(root->alpha[idx], s+1);
            if (!root->alpha[idx]) {
                // child node deleted, set reap = 1
                reap = 1;
            }
        }
    }
    // We can delete this if both:
    // 1. reap is set to 1, which is only possible if either:
    //    a. we are now at the end of the string and root->val used
    //       to be 1, but is now set to 0
    //    b. the child node has been deleted
    // 2. The string ending at the current node is not inside the trie,
    //    so root->val = 0
    if (reap && !root->val) {
        for (i = 0; i < NRALPHA; i++) {
            if (root->alpha[i]) {
                reap = 0;
                break;
            }
        }
        // no more children, delete this node
        if (reap) {
            trie_free(root);
            root = NULL;
        }
    }
    return root;
}