Trie (Prefix tree)

 

Trie

 

개념

n-ary tree의 변종으로 각 노드에 문자를 저장하는 자료구조이다.

트리를 아래쪽으로 순회하면 단어 하나가 나온다.

 

* 노드

* 노드는 널 노드라고도 불리며 단어의 끝을 나타낸다.

TrieNode를 상속한 TerminatingTrieNode로 표현할 수도 있고

* 노드의 부모 노드 안에 boolean flag를 새로 정의해 단어의 끝을 표현할 수도 있다.

 

자식 노드 개수

* 노드로 단어의 끝을 표현하면 각 노드는 1개 ~ (ALPHABET_SIZE + 1)개까지 자식을 갖고 있을 수 있다.

단 * 노드 대신 boolean flag로 표현했다면 0개 ~ ALPHABET_SIZE개까지.

 

활용

접두사를 빠르게 찾아보기 위해 모든 문자열을 트라이에 저장해놓을 수 있다.

해시테이블을 이용하면 주어진 문자열의 유효성을 빠르게 확인할 수 있지만,

그 문자열이 어떤 유효한 단어의 접두사인지는 확인할 수 없다.

 

Trie는 길이가 K인 문자열이 주어졌을 때 O(K) 시간에 해당 문자열이 유효한 접두사인지 확인할 수 있다.

이 시간은 해시테이블을 사용했을 때와 정확히 같은 수행 시간이다.

(흔히 해시테이블 검색이 O(1) 시간에 수행된다고 하지만 입력 문자열은 전부 읽어야 하므로 O(K)이다.)

 

 

Reference: 코딩 인터뷰 완전분석 책

 

---

왜 Trie 인가?

1) 길이가 K인 문자열에 대하여 insert와 search를 O(K)에 수행한다.

↔ BST는 K가 문자열의 길이, N이 전체 단어의 개수라고 할 때 insert와 search를 O(KlogN)에 수행한다.

↔ Hashing과 달리 해시 함수를 계산할 필요가 없고 Chaning이나 Open addressing 같은 Collsion handling도 필요 없다.

 

2) (Hashing과 달리) 모든 단어를 알파벳 순서로 출력하기 쉽다.

3) 효율적으로 prefix search를 할 수 있다.

 

 

Trie의 이슈

Trie의 가장 큰 단점은 메모리가 아주 많이 필요하다는 것이다.

각 노드에 대하여 (알파벳 개수만큼) 아주 많은 노드 포인터를 갖게된다.

즉 K가 문자열의 길이, N이 전체 단어의 개수일 때 공간 복잡도가 O(ALPHABET_SIZE * K * N) 이다.

공간 문제가 중요하다면 Compressed Trie, Ternary Search Tree 등을 사용할 수 있다.

 

--> 정리하자면 Trie는 매우 빠르지만 엄청 큰 메모리가 필요하다.

 

 

Reference: https://www.geeksforgeeks.org/advantages-trie-data-structure/,

https://www.geeksforgeeks.org/trie-insert-and-search/

 

---

구현

struct TrieNode{
    TrieNode* children[ALPHABET_SIZE];
    bool isEndOfWord;
};

맨 위 그림처럼, 존재하는 child node만 그려넣는 게 아니라

각 노드마다 ALPHABET_SIZE개 만큼의 TrieNode*를 미리 준비한다고 생각한다.

 

children의 인덱스는 몇 번째 알파벳인지를 의미한다.

가령 'a'라면 children[0], 'b'라면 children[1], 'z'라면 children[25].

 

처음 TrieNode가 생성되었을 때는 children[i]가 모두 NULL이라고 생각한다.

해당 TrieNode 아래 'a'가 온다면 children[0]이 NULL이 아닌 새로운 TrieNode를 가리키도록 하는 식.

(새로운 TrieNode를 가리키도록 하는 것은 getNode() 라는 함수를 이용한다. - 아래 코드를 참고)

 

insert와 search는 매우 비슷하며,

insert는 getNode()를 이용해 새로운 노드를 연결해가는 한편 search는 그냥 아래로 쭉 내려간다.

 

search가 종료되는 조건은 두 가지이다.

1) input string의 끝에 다다랐다.

--> 이 경우 마지막 노드의 isEndOfWord가 true이면 search 결과도 true이다.

2) trie에 해당하는 key가 없다.

--> search 결과는 false이다.

 

아래는 Reference의 코드에서 변수명, 주석 등을 수정한 전체 코드 버전.

가독성을 위해 input string을 맨 위 사진에 있는 단어들로 하였다.

 

// Ref: https://www.geeksforgeeks.org/trie-insert-and-search/

#include<iostream>
#define ALPHABET_SIZE 26
using namespace std;

struct TrieNode{
    TrieNode* children[ALPHABET_SIZE];
    bool isEndOfWord;
};

TrieNode* getNode()
{
    TrieNode* new_node = new TrieNode;
    new_node->isEndOfWord = false;

    for(int i=0; i<ALPHABET_SIZE; i++){
        new_node->children[i] = NULL;
    }

    return new_node;
}

void insert(TrieNode* root, string key)
{
    TrieNode* temp_node = root;

    for(int i=0; i<key.length(); i++){
        int index = key[i] - 'a';
        if(!temp_node->children[index])
            temp_node->children[index] = getNode();
        temp_node = temp_node->children[index];
    }

    temp_node->isEndOfWord = true;
}

bool search(TrieNode* root, string key)
{
    TrieNode* temp_node = root;

    for(int i=0; i<key.length(); i++){
        int index = key[i] - 'a';
        if(!temp_node->children[index])
            return false;
        temp_node = temp_node->children[index];
    }

    return temp_node && temp_node->isEndOfWord;
}

int main()
{
    string keys[] = {"many", "man", "my", "lie", "a"};
    int n = sizeof(keys) / sizeof(keys[0]);

    TrieNode* root = getNode();
    for(int i=0; i<n; i++)
        insert(root, keys[i]);

    if(search(root, "man")) cout << "Yes" << endl;
    else    cout << "No" << endl;

    if(search(root, "lay")) cout << "Yes" << endl;
    else    cout << "No" << endl;

    return 0;
}

 

Reference: https://www.geeksforgeeks.org/trie-insert-and-search/