Problemas com Trie - c, trie

Então, eu estava tentando ler um Trie, relativamente um novoestrutura de dados para mim. E onde quer que eu lesse, cada nó no trie, consistiria em uma variável inteira que marcaria o fim de uma palavra, e também consistiria de 26 ponteiros, cada um apontando para nós no nível inferior (supondo que as palavras contenham apenas pequenas caracteres de letra).

Agora o problema que estou enfrentando é, onde eu vejo / leio a implementação, eles marcam o nó com um caractere. Como neste caso:

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

Mas do jeito que eu estou entendendo Trie, eu acreditoque cada borda deve ser marcada como um caractere. Embora eu saiba que não temos uma estrutura de dados para as bordas, apenas para os nós. Mas não marcar as bordas seria mais correto?

Além disso, este é o meu algoritmo para implementar a inserção. Por favor, me diga se você encontrar algo errado com isso.

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


trie* insert (trie *root, char *inp)
{
if (*input == "")
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)=="")
root->val = 1;
return root;
}

Estou perplexo sobre como eu poderia implementar a exclusão. Se você puder, por favor me ajude com um algoritmo de exclusão.

Respostas:

Aqui está um pequeno programa que mostra uma maneira de fazer isso. Não há nenhum esforço sério para o tratamento de erros:

http://pastebin.com/84TiPrtL

Eu editei levemente sua função trie_insert e mostrei uma função trie_delete aqui. struct Vec dentro do código pastebin pode ser alterado para um std::vector se você estiver usando C ++.

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 == "") {
// 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;
}