트라이 자료구조: 문자열 검색과 자동 완성의 핵심

트라이(Trie), 또는 접두사 트리는 문자열 데이터를 저장하고 효율적으로 탐색할 수 있도록 설계된 특별한 형태의 트리 기반 자료구조입니다. 이 글에서는 트라이의 구조, 특징 및 자바스크립트를 사용한 구현 방법을 알아보겠습니다.

---

 

트라이의 기본 구조

트라이는 각 노드가 자식 노드를 가리키는 링크를 배열 형태로 가지고 있으며, 각 링크는 특정 문자를 키로 사용합니다. 이 구조는 다음과 같은 특징을 가집니다:

• 루트 노드: 루트 노드는 비어 있으며, 검색을 시작하는 지점입니다.
• 간선: 각 간선은 문자를 표현하며, 노드와 노드를 연결합니다.
• 노드: 각 노드는 이전 노드의 값에 간선의 문자를 더한 값을 가집니다.

---

트라이의 주요 특징

• 탐색 효율성: 트라이를 사용하면 문자열 길이 L에 대해 O(L)의 시간 복잡도로 탐색 및 삽입이 가능합니다.
• 자동 완성 및 사전 탐색: 검색어 자동 완성, 사전 탐색 등의 기능에 매우 유용합니다.
• 메모리 사용량: 각 노드가 가능한 모든 자식에 대한 링크를 유지해야 하므로, 메모리 사용량이 상대적으로 큽니다.

---

자바스크립트에서의 트라이 구현

class TrieNode {
    constructor() {
        this.children = {};
        this.endOfWord = false; // 특정 단어의 끝을 표시
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let current = this.root;
        for (let char of word) {
            if (!current.children[char]) {
                current.children[char] = new TrieNode();
            }
            current = current.children[char];
        }
        current.endOfWord = true;
    }

    search(word) {
        let current = this.root;
        for (let char of word) {
            if (!current.children[char]) {
                return false;
            }
            current = current.children[char];
        }
        return current.endOfWord;
    }
}