트리(3) - 문자열 검색 문제에 최적화된 트라이(Trie) 자료구조(C언어, Java, Python 예시코드 포함)

트라이

 

 

1. 트라이(Trie) 자료구조란?

트라이(Trie)는 문자열을 효율적으로 저장하고 검색하기 위해 설계된 트리(Tree) 기반 자료구조입니다. 주로 문자열 탐색, 자동 완성, 사전(dictionary) 구현에 사용됩니다. 이번 포스팅에서는 트라이의 구조, 구현 방법, 장단점, 활용 사례를 소개합니다.

---

 

2. 트라이의 원리와 구조

(1) 트라이의 기본 개념

• **트라이(Trie)**는 각 노드가 문자열의 문자 하나를 나타내는 자료구조입니다.
• 루트 노드에서 시작하여 문자열의 각 문자를 따라가며 데이터를 저장하거나 탐색합니다.
• 문자열의 끝은 특별한 "종료 노드" 또는 플래그로 표시됩니다.

 

(2) 트라이의 특징

1. 효율적인 검색: 문자열 검색 시간이 문자열 길이에 비례합니다. (O(L), L: 문자열 길이)
2. 공간 절약: 공통 접두사를 공유하여 중복 저장을 방지합니다.
3. 동적 집합 관리: 데이터의 삽입, 삭제, 검색을 쉽게 처리할 수 있습니다.

 

(3)트라이 구조 예시

반응형

다음 문자열들을 저장한 트라이로 표현하겠습니다

• "cat"
• "car"
• "dog"

       (root)
       /   \
      c     d
     / \      \
    a   a      o
   /     \       \
  t       r       g

---

3. 트라이 구현 예제

아래는 C, Java, Python으로 구현한 트라이의 예제 코드입니다.

C 언어

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

#define ALPHABET_SIZE 26

// 트라이 노드 구조체 정의
struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    int isEndOfWord; // 단어의 끝을 표시
};

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

// 문자열 삽입
void insert(struct TrieNode* root, const char* key) {
    struct TrieNode* pCrawl = root;
    for (int i = 0; i < strlen(key); i++) {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            pCrawl->children[index] = createNode();
        pCrawl = pCrawl->children[index];
    }
    pCrawl->isEndOfWord = 1;
}

// 문자열 검색
int search(struct TrieNode* root, const char* key) {
    struct TrieNode* pCrawl = root;
    for (int i = 0; i < strlen(key); i++) {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            return 0;
        pCrawl = pCrawl->children[index];
    }
    return pCrawl->isEndOfWord;
}

int main() {
    struct TrieNode* root = createNode();

    insert(root, "cat");
    insert(root, "car");
    insert(root, "dog");

    printf("Search result for 'cat': %d\n", search(root, "cat"));
    printf("Search result for 'cap': %d\n", search(root, "cap"));

    return 0;
}

---

Java

import java.util.HashMap;

class TrieNode {
    HashMap<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord;

    TrieNode() {
        isEndOfWord = false;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current = current.children.computeIfAbsent(ch, c -> new TrieNode());
        }
        current.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current = current.children.get(ch);
            if (current == null) return false;
        }
        return current.isEndOfWord;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat");
        trie.insert("car");
        trie.insert("dog");

        System.out.println("Search result for 'cat': " + trie.search("cat"));
        System.out.println("Search result for 'cap': " + trie.search("cap"));
    }
}

---

Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

# 사용 예시
trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("dog")

print("Search result for 'cat':", trie.search("cat"))
print("Search result for 'cap':", trie.search("cap"))

---

 

4. 트라이의 장단점

장점

1. 빠른 검색: 검색 시간이 문자열 길이에 비례하여 효율적입니다.
2. 공간 절약: 공통 접두사를 공유해 중복 저장을 방지합니다.
3. 다양한 활용: 자동 완성, 사전 구현 등 다양한 용도로 사용됩니다.

 

단점

1. 메모리 사용량: 알파벳 크기(26) 또는 유니코드 크기만큼 자식을 저장해야 하므로 메모리 사용이 많을 수 있습니다.
2. 구현 복잡성: 단순 배열보다 구현이 까다롭습니다.

 

 

2024.12.18 - [자료구조] - 트리 (1) - 이진 트리(Binary Tree)의 모든 것: 원리, 구조, 예제 코드(C언어 Java, Python), 장단점, 사용 사례

트리 (1) - 이진 트리(Binary Tree)의 모든 것: 원리, 구조, 예제 코드(C언어 Java, Python), 장단점, 사용

 

 

2024.12.18 - [자료구조] - 트리(2) - 이진 탐색 트리(Binary Search Tree)의 원리, 구조, 예제 코드(C언어, Java, Python), 장단점, 사용 사례 총정리

트리(2) - 이진 탐색 트리(Binary Search Tree)의 원리, 구조, 예제 코드(C언어, Java, Python), 장단점, 사용