Trie는 효율적인 정보 검색 데이터 구조입니다. Trie를 사용하면 검색 복잡성을 최적의 한계(키 길이)까지 끌어올릴 수 있습니다. 이진 검색 트리에 키를 저장하는 경우 균형이 잘 잡힌 BST는 M * log N에 비례하는 시간이 필요합니다. 여기서 M은 최대 문자열 길이이고 N은 트리의 키 수입니다. Trie를 사용하여 O(M) 시간에 키를 검색할 수 있습니다. 그러나 패널티는 Trie 저장 요구 사항에 있습니다(자세한 내용은 Trie 응용 프로그램 참조).

Trie의 모든 노드는 여러 분기로 구성됩니다. 각 분기는 키의 가능한 문자를 나타냅니다. 모든 키의 마지막 노드를 단어 노드의 끝으로 표시해야 합니다. Trie 노드 필드 isEndOfWord는 노드를 단어 노드의 끝으로 구별하는 데 사용됩니다. 영어 알파벳의 노드를 나타내는 간단한 구조는 다음과 같을 수 있습니다.

//시도 노드
구조체 트리노드
{
struct TrieNode *children[ALPHABET_SIZE];

 // isEndOfWord is true if the node
 // represents end of a word
 bool isEndOfWord;

};

C 프로그램:

//검색 및 삽입 작업의 C 구현
//시도에서

포함

포함

포함

포함

ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) 정의

//알파벳 크기(기호 수)

ALPHABET_SIZE 정의(26)

//현재 키 문자를 인덱스로 변환
//'a' ~ 'z' 및 소문자만 사용

CHAR_TO_INDEX(c) 정의 ((int)c - (int)'a')

//시도 노드
구조체 트리노드
{
struct TrieNode *children[ALPHABET_SIZE];

// isEndOfWord is true if the node represents
// end of a word
bool isEndOfWord;

};

//새로운 트라이 노드를 반환합니다(NULL로 초기화됨)
구조체 TrieNode *getNode(무효)
{
구조체 TrieNode *pNode = NULL;

pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));

if (pNode)
{
    int i;

    pNode->isEndOfWord = false;

    for (i = 0; i < ALPHABET_SIZE; i++)
        pNode->children[i] = NULL;
}

return pNode;

}

//존재하지 않으면 키를 트라이에 삽입
//키가 트리 노드의 접두사이면 리프 노드만 표시합니다.
무효 삽입(구조 TrieNode *루트, const char *키)
{
정수 수준;
정수 길이 = strlen(키);
정수 인덱스;

struct TrieNode *pCrawl = root;

for (level = 0; level < length; level++)
{
    index = CHAR_TO_INDEX(key[level]);
    if (!pCrawl->children[index])
        pCrawl->children[index] = getNode();

    pCrawl = pCrawl->children[index];
}

// mark last node as leaf
pCrawl->isEndOfWord = true;

}

//key가 tri에 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
부울 검색(구조 TrieNode *루트, const char *키)
{
정수 수준;
정수 길이 = strlen(키);
정수 인덱스;
구조체 TrieNode *pCrawl = 루트;

for (level = 0; level < length; level++)
{
    index = CHAR_TO_INDEX(key[level]);

    if (!pCrawl->children[index])
        return false;

    pCrawl = pCrawl->children[index];
}

return (pCrawl != NULL && pCrawl->isEndOfWord);

}

//드라이버
정수 메인()
{
//입력 키('a'~'z' 및 소문자만 사용)
char keys[][8] = {"the", "a", "거기", "대답", "any",
"바이", "안녕", "그들의"};

char output[][32] = {"Not present in trie", "Present in trie"};


struct TrieNode *root = getNode();

// Construct trie
int i;
for (i = 0; i < ARRAY_SIZE(keys); i++)
    insert(root, keys[i]);

// Search for different keys
printf("%s --- %s\n", "the", output[search(root, "the")] );
printf("%s --- %s\n", "these", output[search(root, "these")] );
printf("%s --- %s\n", "their", output[search(root, "their")] );
printf("%s --- %s\n", "thaw", output[search(root, "thaw")] );

return 0;

}