Trie与Trie发生冲突

Question

因此，我正在尝试阅读Trie，这是一个相对新的数据结构。在我读过的地方，trie中的每个节点都包含一个整型变量，它将标记一个单词的结尾，并且还包含26个指针，每个指针指向较低级别的节点（假设这些单词只包含小字母字符）。

现在我面对的问题是，在我看到/阅读实现的地方，他们用一个字符标记节点。像在这种情况下：

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

但我了解特里的方式，我相信每一个边缘应标记为一个字符。虽然，我知道我们没有边缘的数据结构，只是针对节点。但是不会标记边缘更准确？

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

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