웹사이트 검색

C/C++의 Trie 데이터 구조


Trie 데이터 구조는 동적 배열의 컨테이너 역할을 합니다. 이 기사에서는 C/C++에서 Trie를 구현하는 방법을 살펴보겠습니다.

이것은 트리 데이터 구조를 기반으로 하지만 반드시 키를 저장하지는 않습니다. 여기서 각 노드는 위치에 따라 정의된 값만 가지고 있습니다.

따라서 각 노드의 값은 일련의 일치 후 루트 노드의 지점이기 때문에 접두사를 나타냅니다.

이러한 일치를 접두사 일치라고 합니다. 따라서 사전의 단어를 저장하기 위해 시도를 사용할 수 있습니다!

예를 들어 위의 그림에서 루트 노드는 비어 있으므로 모든 문자열이 루트 노드와 일치합니다. 노드 7은 to의 접두사 문자열과 일치하고 노드 3은 tea의 접두사 문자열과 일치합니다.

여기서 접두사 일치는 모든 리프 노드에서 중지되므로 키는 리프 노드 위치에만 저장됩니다. 따라서 리프가 아닌 노드는 전체 문자열을 저장하지 않고 접두사 일치 문자만 저장합니다.

이러한 모든 이유로 시도를 접두사 트리라고 합니다. 이제 프로그래머의 관점에서 이 데이터 구조를 구현하는 방법을 이해하겠습니다.

C/C++에서 Trie 데이터 구조 구현

먼저 Trie 구조를 적어 봅시다. Trie Node에는 특히 두 가지 구성 요소가 있습니다.

  • 아이들입니다
  • 리프 노드를 나타내는 마커입니다.

그러나 Trie도 인쇄할 것이므로 데이터 부분에 속성을 하나 더 저장할 수 있으면 더 쉬울 것입니다.

이제 TrieNode 구조를 정의해 보겠습니다. 여기서는 소문자 알파벳만 저장할 것이므로 26-ary-tree로 구현하겠습니다. 따라서 각 노드에는 26개의 자식에 대한 포인터가 있습니다.

// The number of children for each node
// We will construct a N-ary tree and make it
// a Trie
// Since we have 26 english letters, we need
// 26 children per node
#define N 26

typedef struct TrieNode TrieNode;

struct TrieNode {
    // The Trie Node Structure
    // Each node has N children, starting from the root
    // and a flag to check if it's a leaf node
    char data; // Storing for printing purposes only
    TrieNode* children[N];
    int is_leaf;
};

이제 구조를 정의했으므로 메모리에서 TrieNode를 초기화하고 포인터를 해제하는 함수를 작성해 보겠습니다.

TrieNode* make_trienode(char data) {
    // Allocate memory for a TrieNode
    TrieNode* node = (TrieNode*) calloc (1, sizeof(TrieNode));
    for (int i=0; i<N; i++)
        node->children[i] = NULL;
    node->is_leaf = 0;
    node->data = data;
    return node;
}

void free_trienode(TrieNode* node) {
    // Free the trienode sequence
    for(int i=0; i<N; i++) {
        if (node->children[i] != NULL) {
            free_trienode(node->children[i]);
        }
        else {
            continue;
        }
    }
    free(node);
}

Trie에 단어 삽입

이제 루트 노드(최상위 노드)에 대한 포인터를 가져와 Trie에 단어를 삽입하는 insert_trie() 함수를 작성합니다.

삽입 절차는 간단합니다. 문자별로 단어를 반복하고 상대 위치를 평가합니다.

예를 들어, b 문자는 위치가 1이므로 두 번째 자식이 됩니다.

for (int i=0; word[i] != '\0'; i++) {
    // Get the relative position in the alphabet list
    int idx = (int) word[i] - 'a';
    if (temp->children[idx] == NULL) {
        // If the corresponding child doesn't exist,
        // simply create that child!
        temp->children[idx] = make_trienode(word[i]);
    }
    else {
        // Do nothing. The node already exists
    }

접두사 문자를 문자별로 일치시키고 노드가 존재하지 않으면 간단히 초기화합니다.

그렇지 않으면 모든 문자를 일치시킬 때까지 체인 아래로 계속 이동합니다.

temp = temp->children[idx];

마지막으로 일치하지 않는 모든 문자를 삽입하고 업데이트된 Trie를 다시 반환합니다.

TrieNode* insert_trie(TrieNode* root, char* word) {
    // Inserts the word onto the Trie
    // ASSUMPTION: The word only has lower case characters
    TrieNode* temp = root;

    for (int i=0; word[i] != '\0'; i++) {
        // Get the relative position in the alphabet list
        int idx = (int) word[i] - 'a';
        if (temp->children[idx] == NULL) {
            // If the corresponding child doesn't exist,
            // simply create that child!
            temp->children[idx] = make_trienode(word[i]);
        }
        else {
            // Do nothing. The node already exists
        }
        // Go down a level, to the child referenced by idx
        // since we have a prefix match
        temp = temp->children[idx];
    }
    // At the end of the word, mark this node as the leaf node
    temp->is_leaf = 1;
    return root;
}

Trie에서 단어 검색

이제 Trie에 대한 삽입을 구현했으므로 주어진 패턴을 검색하는 방법을 살펴보겠습니다.

위와 동일한 접두사 일치 전략을 사용하여 문자열을 문자별로 일치시키려고 합니다.

체인의 끝에 도달했지만 아직 일치하는 항목을 찾지 못한 경우 완전한 접두사 일치가 수행되지 않았기 때문에 문자열이 존재하지 않는다는 의미입니다.

이것이 올바르게 반환되려면 패턴이 정확히 일치해야 하며 일치가 끝나면 리프 노드에 도달해야 합니다.

int search_trie(TrieNode* root, char* word)
{
    // Searches for word in the Trie
    TrieNode* temp = root;

    for(int i=0; word[i]!='\0'; i++)
    {
        int position = word[i] - 'a';
        if (temp->children[position] == NULL)
            return 0;
        temp = temp->children[position];
    }
    if (temp != NULL && temp->is_leaf == 1)
        return 1;
    return 0;
}

자, 삽입검색 절차를 완료했습니다.

이를 테스트하기 위해 먼저 모든 노드의 데이터를 인쇄하는 print_tree() 함수를 작성합니다.

void print_trie(TrieNode* root) {
    // Prints the nodes of the trie
    if (!root)
        return;
    TrieNode* temp = root;
    printf("%c -> ", temp->data);
    for (int i=0; i<N; i++) {
        print_trie(temp->children[i]); 
    }
}

이제 완료했으므로 지금까지 전체 프로그램을 실행하여 제대로 작동하는지 확인하겠습니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// The number of children for each node
// We will construct a N-ary tree and make it
// a Trie
// Since we have 26 english letters, we need
// 26 children per node
#define N 26

typedef struct TrieNode TrieNode;

struct TrieNode {
    // The Trie Node Structure
    // Each node has N children, starting from the root
    // and a flag to check if it's a leaf node
    char data; // Storing for printing purposes only
    TrieNode* children[N];
    int is_leaf;
};

TrieNode* make_trienode(char data) {
    // Allocate memory for a TrieNode
    TrieNode* node = (TrieNode*) calloc (1, sizeof(TrieNode));
    for (int i=0; i<N; i++)
        node->children[i] = NULL;
    node->is_leaf = 0;
    node->data = data;
    return node;
}

void free_trienode(TrieNode* node) {
    // Free the trienode sequence
    for(int i=0; i<N; i++) {
        if (node->children[i] != NULL) {
            free_trienode(node->children[i]);
        }
        else {
            continue;
        }
    }
    free(node);
}

TrieNode* insert_trie(TrieNode* root, char* word) {
    // Inserts the word onto the Trie
    // ASSUMPTION: The word only has lower case characters
    TrieNode* temp = root;

    for (int i=0; word[i] != '\0'; i++) {
        // Get the relative position in the alphabet list
        int idx = (int) word[i] - 'a';
        if (temp->children[idx] == NULL) {
            // If the corresponding child doesn't exist,
            // simply create that child!
            temp->children[idx] = make_trienode(word[i]);
        }
        else {
            // Do nothing. The node already exists
        }
        // Go down a level, to the child referenced by idx
        // since we have a prefix match
        temp = temp->children[idx];
    }
    // At the end of the word, mark this node as the leaf node
    temp->is_leaf = 1;
    return root;
}

int search_trie(TrieNode* root, char* word)
{
    // Searches for word in the Trie
    TrieNode* temp = root;

    for(int i=0; word[i]!='\0'; i++)
    {
        int position = word[i] - 'a';
        if (temp->children[position] == NULL)
            return 0;
        temp = temp->children[position];
    }
    if (temp != NULL && temp->is_leaf == 1)
        return 1;
    return 0;
}

void print_trie(TrieNode* root) {
    // Prints the nodes of the trie
    if (!root)
        return;
    TrieNode* temp = root;
    printf("%c -> ", temp->data);
    for (int i=0; i<N; i++) {
        print_trie(temp->children[i]); 
    }
}

void print_search(TrieNode* root, char* word) {
    printf("Searching for %s: ", word);
    if (search_trie(root, word) == 0)
        printf("Not Found\n");
    else
        printf("Found!\n");
}

int main() {
    // Driver program for the Trie Data Structure Operations
    TrieNode* root = make_trienode('\0');
    root = insert_trie(root, "hello");
    root = insert_trie(root, "hi");
    root = insert_trie(root, "teabag");
    root = insert_trie(root, "teacan");
    print_search(root, "tea");
    print_search(root, "teabag");
    print_search(root, "teacan");
    print_search(root, "hi");
    print_search(root, "hey");
    print_search(root, "hello");
    print_trie(root);
    free_trienode(root);
    return 0;
}

gcc 컴파일러로 컴파일하면 다음과 같은 결과를 얻을 수 있습니다.

Searching for tea: Not Found
Searching for teabag: Found!
Searching for teacan: Found!
Searching for hi: Found!
Searching for hey: Not Found
Searching for hello: Found!
 -> h -> e -> l -> l -> o -> i -> t -> e -> a -> b -> a -> g -> c -> a -> n -> 

어떻게 인쇄되고 있는지는 분명할 수 있지만 단서는 print_tree() 메서드를 보는 것입니다. 현재 노드를 인쇄한 다음 모든 하위 항목을 인쇄하므로 순서가 이를 나타냅니다.

이제 delete 메서드를 구현해 봅시다!

Trie에서 단어 삭제

이것은 실제로 다른 두 가지 방법보다 약간 까다 롭습니다.

키와 값을 저장하는 명시적인 방법이 없기 때문에 일종의 형식 알고리즘이 존재하지 않습니다.

하지만 이 글의 목적상 삭제할 단어가 리프 노드인 경우에만 삭제를 처리하겠습니다. 즉, 리프 노드까지 접두사가 일치해야 합니다.

시작하겠습니다. 삭제 기능에 대한 서명은 다음과 같습니다.

TrieNode* delete_trie(TrieNode* root, char* word);

앞서 언급했듯이 이것은 리프 노드까지 접두사 일치가 수행된 경우에만 삭제됩니다. 그래서 이 작업을 수행하는 다른 함수 is_leaf_node()를 작성해 봅시다.

int is_leaf_node(TrieNode* root, char* word) {
    // Checks if the prefix match of word and root
    // is a leaf node
    TrieNode* temp = root;
    for (int i=0; word[i]; i++) {
        int position = (int) word[i] - 'a';
        if (temp->children[position]) {
            temp = temp->children[position];
        }
    }
    return temp->is_leaf;
}

자, 완료되었으므로 delete_trie() 메서드의 초안을 살펴보겠습니다.

TrieNode* delete_trie(TrieNode* root, char* word) {
    // Will try to delete the word sequence from the Trie only it 
    // ends up in a leaf node
    if (!root)
        return NULL;
    if (!word || word[0] == '\0')
        return root;
    // If the node corresponding to the match is not a leaf node,
    // we stop
    if (!is_leaf_node(root, word)) {
        return root;
    }
    // TODO
}

이 확인이 완료되면 이제 단어가 리프 노드에서 끝날 것임을 알 수 있습니다.

그러나 처리해야 할 또 다른 상황이 있습니다. 현재 문자열과 부분적으로 일치하는 접두사가 있는 다른 단어가 있으면 어떻게 됩니까?

예를 들어, 아래 Trie에서 단어 tea와 ted는 te까지 부분적으로 일치합니다.

따라서 이런 일이 발생하면 t에서 a까지 전체 시퀀스를 간단히 삭제할 수 없습니다. 그러면 두 체인이 연결되어 있으므로 두 체인이 모두 삭제됩니다!

따라서 이러한 일치가 발생할 때까지 가장 깊은 지점을 찾아야 합니다. 그 후에야 나머지 체인을 삭제할 수 있습니다.

여기에는 가장 긴 접두사 문자열을 찾는 것이 포함되므로 다른 함수를 작성해 보겠습니다.

char* longest_prefix(TrieNode* root, char* word);

그러면 현재 단어(단어)가 아닌 Trie에서 가장 긴 일치 항목이 반환됩니다. 아래 코드는 주석의 모든 중간 단계를 설명합니다.

char* find_longest_prefix(TrieNode* root, char* word) {
    // Finds the longest common prefix substring of word
    // in the Trie
    if (!word || word[0] == '\0')
        return NULL;
    // Length of the longest prefix
    int len = strlen(word);

    // We initially set the longest prefix as the word itself,
    // and try to back-track from the deepest position to
    // a point of divergence, if it exists
    char* longest_prefix = (char*) calloc (len + 1, sizeof(char));
    for (int i=0; word[i] != '\0'; i++)
        longest_prefix[i] = word[i];
    longest_prefix[len] = '\0';

    // If there is no branching from the root, this
    // means that we're matching the original string!
    // This is not what we want!
    int branch_idx  = check_divergence(root, longest_prefix) - 1;
    if (branch_idx >= 0) {
        // There is branching, We must update the position
        // to the longest match and update the longest prefix
        // by the branch index length
        longest_prefix[branch_idx] = '\0';
        longest_prefix = (char*) realloc (longest_prefix, (branch_idx + 1) * sizeof(char));
    }

    return longest_prefix;
}

여기에 또 다른 반전이 있다! 가장 긴 일치 항목을 찾으려고 하기 때문에 알고리즘은 실제로 원래 문자열 자체와 탐욕스럽게 일치합니다! 이것은 우리가 원하는 것이 아닙니다.

입력 문자열이 아닌 가장 긴 일치 항목을 원합니다. 따라서 다른 메서드 check_divergence()로 확인해야 합니다.

루트에서 현재 위치로 분기가 있는지 확인하고 입력이 아닌 가장 일치하는 길이를 반환합니다.

우리가 원래 문자열에 해당하는 잘못된 체인에 있으면 지점에서 분기되지 않습니다! 따라서 이것은 check_divergence()를 사용하여 불쾌한 점을 피하는 좋은 방법입니다.

int check_divergence(TrieNode* root, char* word) {
    // Checks if there is branching at the last character of word
 //and returns the largest position in the word where branching occurs
    TrieNode* temp = root;
    int len = strlen(word);
    if (len == 0)
        return 0;
    // We will return the largest index where branching occurs
    int last_index = 0;
    for (int i=0; i < len; i++) {
        int position = word[i] - 'a';
        if (temp->children[position]) {
            // If a child exists at that position
            // we will check if there exists any other child
            // so that branching occurs
            for (int j=0; j<N; j++) {
                if (j != position && temp->children[j]) {
                    // We've found another child! This is a branch.
                    // Update the branch position
                    last_index = i + 1;
                    break;
                }
            }
            // Go to the next child in the sequence
            temp = temp->children[position];
        }
    }
    return last_index;
}

마지막으로 전체 체인을 맹목적으로 삭제하지 않도록 했습니다. 이제 delete 메서드로 이동하겠습니다.

TrieNode* delete_trie(TrieNode* root, char* word) {
    // Will try to delete the word sequence from the Trie only it 
    // ends up in a leaf node
    if (!root)
        return NULL;
    if (!word || word[0] == '\0')
        return root;
    // If the node corresponding to the match is not a leaf node,
    // we stop
    if (!is_leaf_node(root, word)) {
        return root;
    }
    TrieNode* temp = root;
    // Find the longest prefix string that is not the current word
    char* longest_prefix = find_longest_prefix(root, word);
    //printf("Longest Prefix = %s\n", longest_prefix);
    if (longest_prefix[0] == '\0') {
        free(longest_prefix);
        return root;
    }
    // Keep track of position in the Trie
    int i;
    for (i=0; longest_prefix[i] != '\0'; i++) {
        int position = (int) longest_prefix[i] - 'a';
        if (temp->children[position] != NULL) {
            // Keep moving to the deepest node in the common prefix
            temp = temp->children[position];
        }
        else {
            // There is no such node. Simply return.
            free(longest_prefix);
            return root;
        }
    }
    // Now, we have reached the deepest common node between
    // the two strings. We need to delete the sequence
    // corresponding to word
    int len = strlen(word);
    for (; i < len; i++) {
        int position = (int) word[i] - 'a';
        if (temp->children[position]) {
            // Delete the remaining sequence
            TrieNode* rm_node = temp->children[position];
            temp->children[position] = NULL;
            free_trienode(rm_node);
        }
    }
    free(longest_prefix);
    return root;
}

위의 코드는 접두사 일치에 대한 가장 깊은 노드를 찾고 다른 일치와 독립적이므로 Trie에서 나머지 시퀀스 일치 단어를 삭제합니다.

위 절차의 시간 복잡도

절차의 시간 복잡도는 다음과 같습니다.

Procedure Time Complexity of Implementation
search_trie() O(n) -> n is the length of the input string
insert_trie() O(n) -> n is the length of the input string
delete_trie() O(C*n) -> C is the number of alphabets,
n is the length of the input word

거의 모든 경우에 알파벳의 수는 일정하므로 delete_trie()의 복잡성도 O(n)으로 줄어듭니다.

Trie 데이터 구조를 위한 완전한 C/C++ 프로그램

마침내 delete_trie() 함수를 완료했습니다. 드라이버 프로그램을 사용하여 작성한 내용이 올바른지 확인하십시오.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// The number of children for each node
// We will construct a N-ary tree and make it
// a Trie
// Since we have 26 english letters, we need
// 26 children per node
#define N 26

typedef struct TrieNode TrieNode;

struct TrieNode {
    // The Trie Node Structure
    // Each node has N children, starting from the root
    // and a flag to check if it's a leaf node
    char data; // Storing for printing purposes only
    TrieNode* children[N];
    int is_leaf;
};

TrieNode* make_trienode(char data) {
    // Allocate memory for a TrieNode
    TrieNode* node = (TrieNode*) calloc (1, sizeof(TrieNode));
    for (int i=0; i<N; i++)
        node->children[i] = NULL;
    node->is_leaf = 0;
    node->data = data;
    return node;
}

void free_trienode(TrieNode* node) {
    // Free the trienode sequence
    for(int i=0; i<N; i++) {
        if (node->children[i] != NULL) {
            free_trienode(node->children[i]);
        }
        else {
            continue;
        }
    }
    free(node);
}

TrieNode* insert_trie(TrieNode* root, char* word) {
    // Inserts the word onto the Trie
    // ASSUMPTION: The word only has lower case characters
    TrieNode* temp = root;

    for (int i=0; word[i] != '\0'; i++) {
        // Get the relative position in the alphabet list
        int idx = (int) word[i] - 'a';
        if (temp->children[idx] == NULL) {
            // If the corresponding child doesn't exist,
            // simply create that child!
            temp->children[idx] = make_trienode(word[i]);
        }
        else {
            // Do nothing. The node already exists
        }
        // Go down a level, to the child referenced by idx
        // since we have a prefix match
        temp = temp->children[idx];
    }
    // At the end of the word, mark this node as the leaf node
    temp->is_leaf = 1;
    return root;
}

int search_trie(TrieNode* root, char* word)
{
    // Searches for word in the Trie
    TrieNode* temp = root;

    for(int i=0; word[i]!='\0'; i++)
    {
        int position = word[i] - 'a';
        if (temp->children[position] == NULL)
            return 0;
        temp = temp->children[position];
    }
    if (temp != NULL && temp->is_leaf == 1)
        return 1;
    return 0;
}

int check_divergence(TrieNode* root, char* word) {
    // Checks if there is branching at the last character of word
    // and returns the largest position in the word where branching occurs
    TrieNode* temp = root;
    int len = strlen(word);
    if (len == 0)
        return 0;
    // We will return the largest index where branching occurs
    int last_index = 0;
    for (int i=0; i < len; i++) {
        int position = word[i] - 'a';
        if (temp->children[position]) {
            // If a child exists at that position
            // we will check if there exists any other child
            // so that branching occurs
            for (int j=0; j<N; j++) {
                if (j != position && temp->children[j]) {
                    // We've found another child! This is a branch.
                    // Update the branch position
                    last_index = i + 1;
                    break;
                }
            }
            // Go to the next child in the sequence
            temp = temp->children[position];
        }
    }
    return last_index;
}

char* find_longest_prefix(TrieNode* root, char* word) {
    // Finds the longest common prefix substring of word
    // in the Trie
    if (!word || word[0] == '\0')
        return NULL;
    // Length of the longest prefix
    int len = strlen(word);

    // We initially set the longest prefix as the word itself,
    // and try to back-tracking from the deepst position to
    // a point of divergence, if it exists
    char* longest_prefix = (char*) calloc (len + 1, sizeof(char));
    for (int i=0; word[i] != '\0'; i++)
        longest_prefix[i] = word[i];
    longest_prefix[len] = '\0';

    // If there is no branching from the root, this
    // means that we're matching the original string!
    // This is not what we want!
    int branch_idx  = check_divergence(root, longest_prefix) - 1;
    if (branch_idx >= 0) {
        // There is branching, We must update the position
        // to the longest match and update the longest prefix
        // by the branch index length
        longest_prefix[branch_idx] = '\0';
        longest_prefix = (char*) realloc (longest_prefix, (branch_idx + 1) * sizeof(char));
    }

    return longest_prefix;
}

int is_leaf_node(TrieNode* root, char* word) {
    // Checks if the prefix match of word and root
    // is a leaf node
    TrieNode* temp = root;
    for (int i=0; word[i]; i++) {
        int position = (int) word[i] - 'a';
        if (temp->children[position]) {
            temp = temp->children[position];
        }
    }
    return temp->is_leaf;
}

TrieNode* delete_trie(TrieNode* root, char* word) {
    // Will try to delete the word sequence from the Trie only it 
    // ends up in a leaf node
    if (!root)
        return NULL;
    if (!word || word[0] == '\0')
        return root;
    // If the node corresponding to the match is not a leaf node,
    // we stop
    if (!is_leaf_node(root, word)) {
        return root;
    }
    TrieNode* temp = root;
    // Find the longest prefix string that is not the current word
    char* longest_prefix = find_longest_prefix(root, word);
    //printf("Longest Prefix = %s\n", longest_prefix);
    if (longest_prefix[0] == '\0') {
        free(longest_prefix);
        return root;
    }
    // Keep track of position in the Trie
    int i;
    for (i=0; longest_prefix[i] != '\0'; i++) {
        int position = (int) longest_prefix[i] - 'a';
        if (temp->children[position] != NULL) {
            // Keep moving to the deepest node in the common prefix
            temp = temp->children[position];
        }
        else {
            // There is no such node. Simply return.
            free(longest_prefix);
            return root;
        }
    }
    // Now, we have reached the deepest common node between
    // the two strings. We need to delete the sequence
    // corresponding to word
    int len = strlen(word);
    for (; i < len; i++) {
        int position = (int) word[i] - 'a';
        if (temp->children[position]) {
            // Delete the remaining sequence
            TrieNode* rm_node = temp->children[position];
            temp->children[position] = NULL;
            free_trienode(rm_node);
        }
    }
    free(longest_prefix);
    return root;
}

void print_trie(TrieNode* root) {
    // Prints the nodes of the trie
    if (!root)
        return;
    TrieNode* temp = root;
    printf("%c -> ", temp->data);
    for (int i=0; i<N; i++) {
        print_trie(temp->children[i]); 
    }
}

void print_search(TrieNode* root, char* word) {
    printf("Searching for %s: ", word);
    if (search_trie(root, word) == 0)
        printf("Not Found\n");
    else
        printf("Found!\n");
}

int main() {
    // Driver program for the Trie Data Structure Operations
    TrieNode* root = make_trienode('\0');
    root = insert_trie(root, "hello");
    root = insert_trie(root, "hi");
    root = insert_trie(root, "teabag");
    root = insert_trie(root, "teacan");
    print_search(root, "tea");
    print_search(root, "teabag");
    print_search(root, "teacan");
    print_search(root, "hi");
    print_search(root, "hey");
    print_search(root, "hello");
    print_trie(root);
    printf("\n");
    root = delete_trie(root, "hello");
    printf("After deleting 'hello'...\n");
    print_trie(root);
    printf("\n");
    root = delete_trie(root, "teacan");
    printf("After deleting 'teacan'...\n");
    print_trie(root);
    printf("\n");
    free_trienode(root);
    return 0;
}

산출

Searching for tea: Not Found
Searching for teabag: Found!
Searching for teacan: Found!
Searching for hi: Found!
Searching for hey: Not Found
Searching for hello: Found!
 -> h -> e -> l -> l -> o -> i -> t -> e -> a -> b -> a -> g -> c -> a -> n -> 
After deleting 'hello'...
 -> h -> i -> t -> e -> a -> b -> a -> g -> c -> a -> n -> 
After deleting 'teacan'...
 -> h -> i -> t -> e -> a -> b -> a -> g -> 

이로써 C/C++에서 Trie 데이터 구조 구현이 끝났습니다. 긴 글이지만 이러한 방법을 올바르게 적용하는 방법을 이해하셨기를 바랍니다.

코드 다운로드

내가 업로드한 Github Gist에서 전체 코드를 찾을 수 있습니다. 가장 효율적인 코드는 아닐 수 있지만 제대로 작동하는지 확인하기 위해 최선을 다했습니다.

질문이나 제안 사항이 있으면 아래 댓글 섹션에 올려주세요!

참조

  • 시도에 대한 Wikipedia 기사

추천 읽기:

유사한 주제에 관심이 있는 경우 해시 테이블 및 그래프 이론과 같은 주제가 포함된 데이터 구조 및 알고리즘 섹션을 참조할 수 있습니다.