Trie 자료구조란(김종민)

[rlajm1203]

문제가 무엇인가?

Trie 자료구조가 무엇일까?

왜 이런 문제를 선정하였는가?

영속 자료구조에 대해 찾아보다가 Trie 자료구조라는 걸 알게돼서 가져왔습니다.

자신이 생각한 답변은 무엇인가?

Trie 자료구조

• 문자열에서 검색을 빠르게 해주는 자료구조
• retrieval에서 파생된 이름으로, "트라이" 또는 "프리픽스 트리"라고도 부른다.

import java.util.HashMap;
import java.util.Map;

class TrieNode {
    // 자식 노드를 저장하기 위한 맵
    Map<Character, TrieNode> children;
    // 단어의 끝인지 여부를 나타내는 플래그
    boolean isEndOfWord;

    // 생성자
    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

public class Trie {
    private TrieNode root;

    // 생성자
    public Trie() {
        root = new TrieNode();
    }

    // 단어 삽입 메서드
    public void insert(String word) {
        TrieNode currentNode = root;
        for (char c : word.toCharArray()) {
            currentNode = currentNode.children.computeIfAbsent(c, k -> new TrieNode());
        }
        currentNode.isEndOfWord = true;
    }

    // 단어 검색 메서드
    public boolean search(String word) {
        TrieNode currentNode = root;
        for (char c : word.toCharArray()) {
            currentNode = currentNode.children.get(c);
            if (currentNode == null) {
                return false;
            }
        }
        return currentNode.isEndOfWord;
    }

    // 접두사 검색 메서드
    public boolean startsWith(String prefix) {
        TrieNode currentNode = root;
        for (char c : prefix.toCharArray()) {
            currentNode = currentNode.children.get(c);
            if (currentNode == null) {
                return false;
            }
        }
        return true;
    }
}

장점

• 빠른 검색 : Trie는 문자열을 O(N) 시간 복잡도로 검색할 수 있다. (N은 문자열 길이)
• 자동 완성 기능 : 접두사 기반의 검색이 매우 효율적이어서, 자동완성, 단어 추천 기능을 구현할 때 아주 좋을 듯
• 메모리 효율성 : 공통 접두사를 공유하여 저장 공간을 효율적으로 사용할 수 있다.

단점

• 메모리 사용량 : 자장할 문자열의 수가 많아질수록 Trie의 크기가 커질 수 있으며, 매우 긴 문자열일 경우 많은 메모리를 사용할 수 있다.

활용 사례

• 사전
• 자동완성
• IP 라우팅
• DNA 서열 분석

변형

• Compressed Trie
  • 각 노드가 한 문자만 저장하는 것이 아닌, 조금 더 긴 문자열을 노드에 저장할 수 있도록 한다. (메모리 사용을 줄이고, 성능을 향상 시킬 수 있다.)
• Ternary Search Tree
  • Trie 메모리 사용량을 줄이기 위해 노드마다 최대 세 개의 자식을 가지는 구조로 변형한 트리 검색 성능은 떨어지지만 메모리 사용량은 감소
• DAWG(Directed Acyclic Word Graph)
  • 중복된 경로를 제거해서 효율성을 높인 트라이의 변형. 특히 단어 검색과 자동 완성에 자주 사용된다.

해봅시다

[rlajm1203]

[ typeword , type ]

     t - y - p - e - w - o - r - d

flag :