[Tech] Trie

Trie

• 트라이는 단어 자동 완성, 검색 기능에 많이 사용되는 트리 자료구조중 하나입니다.
• 공간 복잡도는 크지만, 빠른 시간안에 단어를 검색할 수 있습니다.
• 루트노드를 시작으로 문자열을 순회하면서 부모 문자를 prefix로 갖는 자식 문자열을 추가함으로써 트리에 삽입합니다.
• 특정 단어를 찾기 위해선, 삽입과 마찬가지로 문자열을 순회하면서 같은 prefix를 갖는 자식 노드와 단어가 같은지 확인합니다.

소스 코드

class Node {
    constructor(value = "") {
        this.value = value;
        this.children = new Map();
        this.isWord = false;
    }
}
class Trie {
    constructor() {
        this.root = new Node();
    }
    
    insert(string) {
        let currentNode = this.root;
        for(const char of string) {
            if (!currentNode.children.has(char)) {
                currentNode.children.set(
                    char,
                    new Node(currentNode.value + char)
                );
            }
            currentNode = currentNode.children.get(char);
        }
        currentNode.isWord = true;
    }
    has(string) {
        let currentNode = this.root;
        for(const char of string) {
            if(!currentNode.children.has(char)) {
                return false;
            }
            currentNode = currentNode.children.get(char);
        }
        return true;
    }
    autoComplete(string) {
        let wordList = [];
        const stack = [];
        let currentNode = this.root;
        if(!string.length) return wordList;
        
        for(const char of string) {
            if(currentNode.children.has(char)) 
                currentNode = currentNode.children.get(char);
            else 
                return wordList;        
        }

        if (currentNode.isWord) wordList.push(currentNode.value);

        stack.push(currentNode);
        while(stack.length > 0) {
            currentNode = stack.shift();
            if(currentNode.children.size > 0) {
                for (const [_, node] of currentNode.children) {
                    stack.push(node);

                    if (node.isWord)
                      wordList.push(node.value);
                }
            } 
        }

        return wordList;

trie.insert('cow');
trie.insert('coworker');
trie.insert('cookie');
trie.insert('mic');
trie.insert('mickey');
console.log(trie.autoComplete('co')); // ['cow', 'cookie', 'coworker', 'code']
console.log(trie.autoComplete('ca')); // [ 'cat', 'can', 'cap' ]
console.log(trie.autoComplete('mi')); // [ 'mic', 'mickey' ]
console.log(trie.autoComplete('')); // []