자바스크립트를 이용한 Trie 구현

단어를 검색할 때 많이 사용하는 Trie 자료구조를 자바스크립트로 구현해 보도록 하겠습니다.

먼저 Trie 란 무엇인지부터 알아보도록 하겠습니다.

Trie 란 공간 복잡도가 큰 대신, 빠른 시간 안에 단어를 검색할 수 있는 트리입니다.

가령

• hell
• hep
• hel

이라는 3개의 문자열이 Trie 에 삽입되었다고 가정해 봅시다.

각각의 node 는

value: string
child: object
end: boolean

의 형태로 구성되어있습니다

그럼 직접 문자열을 trie에 넣어보며 이해해 보도록 하겠습니다.

먼저 hell 이라는 문자열을 trie 에 삽입하게 되면 첫 글자인 h 가 root 노드의 자식인지 확인합니다.

최초의 root 는 자식이 존재하지 않기때문에, h 라는 값을 가지는 자식 또한 없습니다.
그럴 경우, h 라는 자식을 노드로 만들어줍니다.
h 를 삽입했으니 이번에는 e 를 삽입할 차례입니다.
h 노드의 경우도, 방금 만들어진 노드이기때문에 he 라는 자식이 존재하지 않습니다.
같은 방식으로 he 라는 자식을 노드로 만들어줍니다.
같은 방식으로 l 을 두번 넣게 되면, hell 이라는 문자열의 삽입은 종료됩니다.
문자열의 삽입이 종료되었기 때문에, 마지막 자식 노드의 end 를 true 로 변경해줍니다.

이때 이와같은 트라이가 만들어지게 됩니다.

트라이를 구현하는데는 많은 방법이 있을 수 있고, 저같은 경우 value에 여태까지의 누적 값을
합산하도록 구현했습니다.

이제 나머지 두개의 문자열까지 넣게되면 아래와 같은 형태가 만들어집니다.

해당 트라이에서, End의 값이 true 인 hep, hell, hel 3개의 단어가 삽입된 상황임을 알 수 있습니다.

삽입을 이해하셨다면, 탐색은 정말 쉽습니다.
현재 노드를 기준으로 원하는 자식 노드가 있다면 자식 노드로 이동해 다시 탐색하고,
원하는 자식 노드가 없다면 해당 문자열이 없다고 판단하면 됩니다.

그럼 코드와 함께 이해해보도록 합시다.

class Node {
    constructor(value = ''){
        this.value = value; //현재 경로까지의 누적값
        this.end = false; //해당 노드에서 끝나는 문자열이 있는지 여부
        this.child = {} //자식
    }
}

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

     insert(string){
        let currentNode = this.root; //루트노드를 시작으로 탐색하면서 삽입한다
    
        for(let i = 0; i <string.length ; i++) {
            
            const currentChar = string[i];

            //만일, 해당 키를 가진 자식이 없다면 새 노드를 만들어준다.
            if(currentNode.child[currentChar] === undefined){
                currentNode.child[currentChar] = new Node(currentNode.value + currentChar);
            }

            currentNode = currentNode.child[currentChar]; // 자식 노드로 이동한다.
        }
        currentNode.end = true //해당 노드에서 끝나는 단어가 있음을 알린다
     }

     search(string) {
        let currentNode = this.root; //역시나 시작은 루트

        for(let i = 0; i <string.length ; i++) {
            const currentChar = string[i]; 
            if(currentNode.child[currentChar]){
                currentNode = currentNode.child[currentChar]; // 있으면 노드 이동
            } else {
                return ''
            }
        }
        //찾는 문자열의 마지막까지 탐색했다는것은, 문자열을 찾았다는 것. 
        return currentNode.value;
     }
 }

 const myTrie = new Trie();

 myTrie.insert("hell");
 myTrie.insert("hep");
 myTrie.insert("hel");

 console.log(myTrie.search("hell")) // 찾아야함
 console.log(myTrie.search("hello"))
 console.log(myTrie.search("hep")) // 찾아야함 
 console.log(myTrie.search("help"))
 console.log(myTrie.search("world"))

이해가 잘 되셨나요?
여기서 왜 단어의 끝을 나타내는 End 가 필요한지에 대한 의문이 있으실 수도 있는데요,
가령 자동 완성 기능을 구현할 경우에 유용합니다.
가령 he 까지 쳤을 때, 자동 완성을 구현하려면 he 의 자식 노드들을 말단 노드까지 탐색하면서
end 가 true 인것을 모두 알려주면 되겠습니다.

간단하게 Trie 에 대해 알아보았습니다.