Trie(트리, 트라이) with JavaScript

* node 에서는 기본적으로 class를 사용하지 못하므로 babel을 사용해야 한다. 적용법은 최하단 링크에 있다. 귀찮으면 아래 링크의 git을 clone을 하시면 된다. 

Trie ( 이미지 출처 : 나무위키 )

Trie : 트리의 응용 자료구조로, 단어를 찾는데 몹시 효과적이라고 한다. 

찾고자 하는 단어의 길이만큼의 시간복잡도를 가진다.

나무위키를 보자. 

https://namu.wiki/w/%ED%8A%B8%EB%9D%BC%EC%9D%B4

트라이 - 나무위키

---

class Node {

    data;

    constructor(data) {
        this.data = data;
        for (let i = 0; i < 26; i++) {
            const tmp = String.fromCharCode(97 + i);
            this[tmp] = undefined;
        }
    }
}

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

    add = (word) => {
        let currentNode = this.root;
        let previousWhileChar = '';
        for (let i = 0; i < word.length; i++) {
            let currentChar = word.charAt(i);
            previousWhileChar += currentChar;
            if (currentNode[currentChar] === undefined) {
                const newNode = new Node(previousWhileChar);
                currentNode[currentChar] = newNode;
                currentNode = newNode;
            } else {
                currentNode = currentNode[currentChar];
            }
        }
    };


    lookUp = (word) => {
        let currentNode = this.root;
        for (let i = 0; i < word.length; i++) {
            let currentChar = word.charAt(i);
            currentNode = currentNode[currentChar];

            if (currentNode.data === word) return currentNode;
        }
        return 'no match';
    }

}


const trie = new Trie(new Node('Root'));
trie.add('concatenate');
trie.add('apple');
trie.add('disguise');

const foundNode = trie.lookUp('apple');
console.log(foundNode);

간단하게 Trie를 만들어보았다.

후다닥 뿌지직 하는 느낌으로 짠 코드이므로, 문제가 있을 수 있다. 발견하면 알려주세요

간략하게 설명하자면, 각 Node 는 data와 a~z 까지의 속성값들을 가진다. 

data는 해당 노드가 가지는 총 문자열을, 속성값들은 하위에 속성값들의 내용으로 연결해주는 역할을 한다.

해당하는 속성값을 타고가다보면 단어를 찾을 수 있다. 

사전을 구현하기 참 좋은 것 같다.

요렇게!!! 악필이다 ㅠㅠ

---

위에도 있지만, 아래의 내 깃허브에서 소스를 볼 수 있다. 

https://github.com/iamdap91/basic-data-structure

iamdap91/basic-data-structure

http://jeonghwan-kim.github.io/2016/07/19/babel.html

Babel로 ES6 코드 사용하기