[c언어] 트라이 구조

26 Dec 2023

c언어

트라이(Trie) 구조는 문자열 검색과 관련된 애플리케이션에서 효율적인 자료구조로 사용됩니다. 이 자료구조는 문자열을 저장하고 검색하는 데 사용됩니다. 이 포스트에서는 C언어를 사용하여 트라이 구조를 구현하는 방법에 대해 알아보겠습니다.

트라이란?

트라이는 트라이 트리(Trie Tree)라고도 불리며, 각 노드가 문자를 나타내는 트리 자료구조입니다. 각 노드는 문자와 해당 문자가 끝나는지 여부를 나타내는 플래그를 포함합니다. 트라이는 공통 접두사를 공유함으로써 문자열을 저장하고 효율적으로 검색할 수 있습니다.

C언어로 구현

아래는 C언어를 사용하여 간단한 트라이 구조를 구현하는 예제 코드입니다.

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

#define ALPHABET_SIZE 26

struct TrieNode {
    struct TrieNode *children[ALPHABET_SIZE];
    bool isEndOfWord;
};

struct TrieNode *createNode() {
    struct TrieNode *node = (struct TrieNode *)malloc(sizeof(struct TrieNode));
    node->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}

void insert(struct TrieNode *root, char *key) {
    struct TrieNode *current = root;
    for (int level = 0; key[level] != '\0'; level++) {
        int index = key[level] - 'a';
        if (!current->children[index]) {
            current->children[index] = createNode();
        }
        current = current->children[index];
    }
    current->isEndOfWord = true;
}

bool search(struct TrieNode *root, char *key) {
    struct TrieNode *current = root;
    for (int level = 0; key[level] != '\0'; level++) {
        int index = key[level] - 'a';
        if (!current->children[index]) {
            return false;
        }
        current = current->children[index];
    }
    return (current != NULL && current->isEndOfWord);
}

int main() {
    struct TrieNode *root = createNode();
    char *keys[] = {"apple", "banana", "apricot", "avalanche", "ball"};
    int n = sizeof(keys) / sizeof(keys[0]);
    for (int i = 0; i < n; i++) {
        insert(root, keys[i]);
    }
    printf("%s\n", search(root, "apple") ? "Found" : "Not found");
    printf("%s\n", search(root, "apricot") ? "Found" : "Not found");
    printf("%s\n", search(root, "orange") ? "Found" : "Not found");
    return 0;
}

마무리

이것은 C언어로 간단한 트라이 구조를 구현하는 방법에 대한 간단한 예제입니다. 트라이는 문자열 검색 문제에 유용한 자료구조이며, C언어를 사용하여 효율적으로 구현할 수 있습니다.

더 많은 정보를 원하시는 경우 GeeksforGeeks 웹사이트를 방문하시기 바랍니다.