트라이(Trie)

---

트라이(Trie)

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

각 노드는 자식 노드를 구현할때 문자 키를 통해서 노드가 생성되고 연결된다.

트라이 특징

• 검색어 자동완성, 사전 찾기 등에 응용될 수 있다.
• 문자열을 탐색할 때 단순하게 비교하는 것 보다 효율적으로 찾을 수 있다.
• L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.
• 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용한다.

트라이 구조

• 루트는 비어있다.
• 각 간선은 추가될 문자를 키로 가진다.
• 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
• 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.

자동 완성 기능

트라이 구조를 통해서 자동 완성 기능을 구현하고자 한다.

이 그림을 보고 로직을 정리해보자

만약 t에 대한 자동 완성의 결과 값은 to, tea, ted, ten 이렇게 출력되어야 할 것이다.

레벨 순회 Queue를 이용한다면 t의 자식 노드 리스트 부터 enqueue를 수행하고 dequeue를 통해 값을 가져온다. 그리고 dequeue를 진행하면서 노드의 자식 리스트를 또 enqueue를 해준다.

그러면 해당 레벨에 연결되어있는 자식들이 순서대로 출력된다.

내가 저장한 문자?

생각을 해보자 내가 트라이 구조에 저장한 문자열은 to, tea, ted, ten이다. 근데 레벨 순회를 통해 접근한다면 te도 자동 완성 리스트에 추가될 것이다.

te는 tea, ted, ten의 징검다리 역할일 뿐이다.

근데 만약 te도 내가 저장한 문자열이라면 그때는 또 징검다리가 아닌 하나의 문자열로 자동완성 리스트에 추가를 해줘야한다.

어떻게 구별해야할까? 나는 각 노드 구조에 isInclude 요소를 추가하여 각 노드가 트라이 구조에 삽입 될 때 isInclude를 true로 설정하여 해당 노드는 내가 삽입한 문자열을 증명할 수 있게 만들었다.

레벨 순회를 통해 각 노드를 방문하면서 isInclude 요소를 확인하여 만약 true라면 자동완성 결과에 추가하면 된다.

트라이 & 자동완성 구현

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

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

    insert(string) {
        let currentNode = this.root;

        for(const char of string) {
            const str = currentNode.value + char;
            // 현재 노드에서 해당 문자로 시작하는 자식이 없다면
            if(!currentNode.children.has(char)) {
                // 현재 노드 자식으로 문자를 키로 현재 노드 값과 현재 문자 값을 더해 새 노드를 생성한다.
                currentNode.children.set(char, new Node(str, str === string));
            }

            //키가 있다면 이동만 한다.
            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;
    }

    /* 문자열 자동 완성 */
    autoComplete(string) {
        const result = [];
        const queue = [];
        let currentNode = this.root;

        // 입력받은 문자열까지 이동
        for(const char of string) {
            // 해당 문자열이 트라이에 없다면 빈 배열 반환
            if(!currentNode.children.has(char)) {
                return [];
            }
            currentNode = currentNode.children.get(char);
        }

        // 자기 자신 큐에 추가
        queue.push(currentNode);

        while(queue.length > 0) {
            const { value, children, isInclude } = queue.shift(); // { 문자열 값, 자식 문자열 리스트, 입력한 문자열이 맞는지 }

            // 입력한 문자열이 맞다면 결과에 추가
            if(isInclude) {
                result.push(value);
            }

            // 자식 문자열을 모두 enqueue
            for(const [_, nextNode] of children) {
                queue.push(nextNode);
            }
        }

        return result;
    }
}

const trie = new Trie();

trie.insert("to");
trie.insert("te");
trie.insert("tea");
trie.insert("ted'");
trie.insert("ten");

// console.log(trie.has("to")); // true
// console.log(trie.has("te")); // true
// console.log(trie.has("tea")); // true 

console.log(trie.autoComplete("t")); // [ 'to', 'te', 'tea', 'ten', "ted'" ]