[알고리즘] 트라이 - JavaScript

트라이? 

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

트라이의 특징

• 검색어 자동완성, 사전 찾기 등에 사용할 수 있다. 
• 문자열을 탐색할 때 단순 비교보다 효율적으로 찾을 수 있다. 
• L이 문자열의 길이일 때 탐색, 삽입은 O(L) 만큼의 시간 복잡도를 가진다. 
• 자식에 대한 링크를 전부 가져야 하기 때문에 저장 공간을 많이 차지한다. 

JavaScript에서 사용하기

class Node {
    constructor(value = "") {
        this.value = value;
        this.children = new Map();
    }
}

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);
        }
    }
    
    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
    }
}