기본 접두사 트리 구현 질문

Question

기본 접두사 트리 또는 "trie"를 구현했습니다. 트라이는이 같은 노드로 구성 : "애플", "방주"와 "고양이"

// pseudo-code 
struct node { 
    char c; 
    collection<node> childnodes; 
}; 

내가 내 트라이에 다음 단어를 추가 말. 이제 "Ap"와 "Ca"와 같은 접두사를 검색 할 때 my trie의 "bool containsPrefix (string prefix)"메서드가 true를 올바르게 반환합니다.

이제 "Cat"과 "Ark"에 대해서는 true를 반환하지만 위의 예에서는 "App"에 대해 false를 반환하는 "bool containsWholeWord (string word)"메서드를 구현하고 있습니다.

트라이의 노드가 일종의 "endOfWord"플래그를 갖는 것이 일반적입니까? 이것은 조회되는 문자열이 실제로 접두어가 아닌 trie에 입력 된 전체 단어인지 여부를 결정하는 데 도움이됩니다.

건배!

Answer 1

"App"과 "Apple"을 모두 저장해야하지만 "Appl"를 저장하지 않으려면 endOfWord 플래그가 필요합니다.

또는 동일한 문자가있는 두 개의 노드를 사용하여 디자인에 맞출 수 있습니다. 따라서 "Ap"는 자식 노드에 있어야합니다. 리프 노드 "p"와 내부 노드 "p"에 자식 "l"이 있습니다.

Answer 2

키의 끝은 일반적으로 리프 노드를 통해 표시됩니다. 다음 중 하나 :

• 자식 노드가 비어 있습니다. 또는
• 키의 한 접두어와 일부 하위 노드가있는 분기가 있습니다.

디자인에 잎/빈 노드가 없습니다. 예를 들어이를 나타냅니다. null.