c - 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;
}

我对如何实现删除感到困惑。如果可以，请帮我设计一个删除算法。

Answer 1

这是一个小程序，展示了一种方法。虽然没有认真对待错误处理:

http://pastebin.com/84TiPrtL

我稍微编辑了您的 trie_insert 函数并在此处显示了 trie_delete 函数。如果您使用的是 C++，则可以将 pastebin 代码中的 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;
}