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