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 기능을 표시했습니다하지만 오류 처리에 넣어 더 진지한 노력이 없다. 페이 스북 코드 내의 struct Vec은 std::vector으로 변경할 수 있습니다 (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 == '\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; 
}