javascript - 트라이(Trie)

트라이(Trie) 알고리즘

트라이는 문자열들을 저장하고 효율적으로 탐색할 수 있는 트리 기반의 자료구조입니다. 특히, 자동 완성, 사전 검색 등의 기능에 유용하게 사용됩니다.

기본 구조

트라이의 각 노드는 알파벳을 키로 가지는 자식 노드들의 맵(또는 배열)과, 문자열의 끝을 나타내는 플래그로 구성됩니다.

1. 트라이 노드 정의

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

2. 트라이 클래스 정의

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

    // 문자열 삽입
    insert(word) {
        let node = this.root;

        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }

        node.isEndOfWord = true;
    }

    // 문자열 검색
    search(word) {
        let node = this.root;

        for (let char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }

        return node.isEndOfWord;
    }

    // 문자열이 트라이의 접두사인지 확인
    startsWith(prefix) {
        let node = this.root;

        for (let char of prefix) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }

        return true;
    }
}

3. 사용 예제

let trie = new Trie();

trie.insert("apple");
console.log(trie.search("apple"));   // true
console.log(trie.search("app"));     // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app"));     // true

트라이는 문자열 검색 및 저장에 효율적인 자료구조로서, 다양한 애플리케이션에서 활용할 수 있습니다. JavaScript로 간단하게 구현해 보았지만, 실제 환경에서는 더 많은 최적화와 기능 확장이 필요할 수 있습니다.