[자료구조] 트라이(Trie) - javascript

✅ 트라이(Trie)란?

문자열의 집합을 표현하는 트리 자료구조로, 문자열을 검색하는데 최적화된 구조.
루트부터 문자를 하나씩 따라 내려가면서 일치 여부를 확인하면 됨.

📌 구현

아래 코드는 leetcode 208. Implement Trie (Prefix Tree)의 풀이와 같음

// 트라이의 각 노드의 형태
class TrieNode {
    constructor() {
        this.children = {}; // 다음 글자들이 TrieNode로 들어가서 이어짐
        this.endWord = false; // 여기까지가 단어의 끝인지 여부
    }
}

// 트라이 생성
// ex) ap, ab => {children: { a: {children: {p: {children: {}, endWord: true}, b: {children: ...}}, endword: true}}
var Trie = function() {
    this.root = new TrieNode();
};

// 문자열 삽입
Trie.prototype.insert = function(word) {
    let cur = this.root;
    for(let cha of word) {
        if(!cur.children[cha]) cur.children[cha] = new TrieNode();
        cur = cur.children[cha];
    }
    cur.endWord = true;
};

// 문자열 검색
Trie.prototype.search = function(word) {
    let cur = this.root;

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

    return cur.endWord ? true : false; // word로 단어가 끝나면 true
};

// 문자열 포함 여부 확인 (트라이에 삽입할 수 있는지 확인)
Trie.prototype.startsWith = function(prefix) {
    let cur = this.root;

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

    return true;
};