2

それで、私は比較的新しいデータ構造である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;
}

削除をどのように実装できるかについて、私は困惑しています。可能であれば、削除アルゴリズムを教えてください。

4

1 に答える 1

0

これを行う方法を示す小さなプログラムを次に示します。ただし、エラー処理に真剣に取り組む必要はありません。

http://pastebin.com/84TiPrtL

trie_insert 関数を少し編集して、ここに trie_delete 関数を示します。C++ を使用している場合は、 pastebinstruct 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;
}
于 2013-07-20T08:09:06.883 に答える