[자료 구조] 트라이(접두사 트리)

---

트라이(접두사 트리)

---

개요

 - 트라이는 n-차 트리 중 하나이다. 

 - 각 노드에 문자를 저장하는 자료구조이며, 트리를 이래쪽으로 순회하면 하나의 단어가 나온다. 

---

트라이의 구조

 - 트라이의 각 노드는 문자 또는 문자의 끝을 나타낸다. 

 - 문자의 끝을 나타내는 노드를 널 노드라고 부른다. 

트라이

 - 위의 예를 보면 노드들을 순회하다가 *노드가 나오면 단어가 완성되는 것을 볼 수 있다. 

  (가장 왼쪽부터 BOOK, BOY, BAN, MAN, M, Z)

 - 트라이에서 각 노드는 1~(1+26(알파벳의 개수))의 자식 노드를 가질 수 있다. 

 - 이 자료구조는 접두사를 빠르게 찾아보기 위한 방식이다. 길이가 K인 문자열이 주어졌을 때 배열로 구현한 트라이를 이용하면 O(K) 시간에 문자열이 유효한 접두사인지 알 수 있다. 반면 map을 기반으로한 트라이를 이용하면 O(KlogN)이 걸린다. 

---

트라이 구현 (map 기반) 

 - 트라이는 루트 노드를 표현하는 트라이 노드를 멤버 변수로 갖는다. 

class Trie{
private:
    TrieNode root;
}

 

- 트라이 노드는 각 문자별로 자식 노드를 갖기 위한 map 자료구조, 노드의 문자를 나타내는 char, 노드가 단어의 마지막임을 표현하는 bool을 맴버 변수로 갖는다. 

class TrieNode{
private:
    map<char, TrieNode> children;
    char value;
    bool isLast;
}

 

 - root 노드에 단어를 삽입하는 과정은 다음과 같다.

  1. 단어를 앞자리부터 한자리씩 읽어서 해당 문자를 가진 자식 노드가 있는지 판단한다. 

  2. 해당 문자를 가진 자식 노드가 없으면 자식 노드를 만들어준다. 

  3. 다음 문자부터 탐방하되 탐방할 문자가 마지막 문자라면 마지막이라는 표시만 한다. 마지막 문자가 아니라면 자식 노드에서 1번 과정부터 다시 수행한다. 

    void addWord(string word){
        char firstChar = word.at(0);
        
        /* 첫번째 문자를 가진 자식 노드를 조회한다. */
        map<char, TrieNode>::iterator temp = findChild(firstChar);
        
        /* 자식이 존재하지 않을 경우 */
        if(temp == children.end()){
            TrieNode insertNode(firstChar);
            
            children.insert({firstChar, insertNode});
            
            temp = findChild(firstChar);
        }
        
        /* 탐방할 문자가 마지막 문자인지 판단한다. */
        if(word.length()>1){
            temp->second.addWord(word.substr(1));
        }
        else{
            temp->second.isLast = true;
        }
    }
    
    map<char, TrieNode>::iterator findChild(char c){
        return children.find(c);
    }

 

 - 마지막으로 Trie 자료구조에서 단어를 입력받아 앞자리부터 끝자리까지 root노드에서부터 자식 노드들을 탐방해나간다. 자식 노드가 없으면 유효하지 않은 단어라고 판단한다. 

    bool contains(string word){
        TrieNode* temp = &root;
        
        for(int i=0;i<word.size();i++){
            if(temp->findChild(word.at(i)) == temp->getChildren().end()){
                return false;
            }
            else{
                temp = &(temp->findChild(word.at(i))->second);
            }
        }
        
        return true;
    }