트라이 Trie (c++ 구조체 구현)

Trie

 

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

• 트리 구조로 문자열을 저장하기 때문에 단순히 비교하면서 탐색하는 것보다 효율성이 좋습니다.
• 주로 문자열이 키인 경우가 많습니다.
• 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않습니다.
  즉, 키의 값은 자료구조 전체에 분산됩니다.
• 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유하기 때문에 '접두사 트리'라고도 불립니다.
• 루트는 빈 문자열 입니다.
• 정수나 메모리 주소 같은 고정 길이 이진 자료를 표현하는 각각의 비트로 구성된 트라이를 특별히 비트 트라이라고 부릅니다.

 

 

Trie 의 장점

• 불완전한 해시 함수를 사용하는 해시테이블과 비교할 때, 자료에 접근할 때 최악의 경우 더 유리한 시간복잡도를 갖습니다.
  why? 보통 해시테이블은 탐색시간이 O(1)이고 평균탐색시간이 O(m)이지만, 불완전한 해시 테이블은 키 충돌이 일어날 수 있으므로, O(N)이 될 수 있습니다.
• m이 탐색할 문자열의 길이일 때 시간복잡도는 O(m) 입니다.
• 트라이에서는 키 충돌이 일어나지 않습니다. (해시테이블은 일어날 수 있습니다.)
• 해시함수가 없어도 됩니다. 키가 늘어날 때 해시 함수를 변경할 필요도 없습니다.
• 모든 항목에 키에 따라 사전순으로 정렬되어 있습니다.

 

 

Trie 의 단점

• read는 해시 테이블보다 느릴 수 있습니다.
• 부동소수점과 같이 문자열로 장황하게 표시되는 자료의 경우 무의미하게 길게 늘어진 접두사와 노드를 가질 수 있습니다.
  (비트트라이로 처리할 수 있다고 합니다.)
• 트라이가 메모리를 더 소비할 수 있습니다.
  대부분의 해시 테이블은 전체 항목을 하나의 메모리 청크에 올리곤 하지만, 트라이에서는 검색 문자열의 각 문자마다 메모리가 할당될 수 있습니다.
• 공간복잡도가 커질 수 있다는 단점이 있습니다.

 

 

알고리즘

트라이는 탐색과 삽입을 지원하는 노드로 구성된 트리입니다.

키 문자열과 연관된 값을 반환하고, 삽입은 문자열(키)과 그 값을 삽입합니다.

키의 길이가 m일때, 탐색과 삽입 모두 O(m) 시간에 수행됩니다.

 

 

구현

1. insert
   • 루트부터 단어의 글자를 차례대로 탐색
   • 현재 노드 자식 중 해당 자식이 있다면 -> 이동
   • 현재 노드 자식 중 해단 자식이 없다면 -> 새로운 자식 생성
   • 단어 삽입 후 마지막 노드에 입력된 단어 정보를 추가
2. search
   • 루트에서 시작해서 단어의 첫 글자부터 트라이 탐색
   • 현재 노드의 자식 중 단어의 철자가 맞는 자식이 있다면 -> 자식으로 이동
   • 현재 노드의 자식 중 단어의 철자가 맞는 자식이 없다면 -> 탐색 실패
   • 탐색이 끝났다면 탐색된 마지막 노드의 정보를 이용해 단어를 알아냄

 

 

예시

백준 14725 개미굴 문제에 쓰인 Trie 구조체 입니다.

여기서는 알파벳 한글자 한글자가 아닌 string 으로 문자열을 각 노드가 가지고 있습니다.

삽입과 출력(탐색?)을 구현하였습니다.

 

vector<string> name;	// insert 할 이름들

struct Trie {	// Trie 구조체
    map<string, Trie*> next;	// vecotr로 만들어도 되지만 중복 안되는 map으로 생성 (시간단축!)
    
    // insert
    void insert(vector<string>& strVector, int strSize, int index) {
        if (strSize <= index) {
            return;
        }
        
        map<string, Trie*>::iterator iter = next.find(strVector[index]);
        
        // 다음 철자와 맞는 글자가 없다면 새로 next Trie 생성
        if (iter == next.end()) {
            Trie* newNext = new Trie;
            next.insert({strVector[index], newNext});
            newNext->insert(strVector, strSize, index + 1);
        }
        // 다음 철자와 맞는 글자가 있다면 다음 글자로 이동후 insert
        else {
            iter->second->insert(strVector, strSize, index + 1);
        }
    }
    
    // print(search) 여기선 완벽한 search는 아니고 모두 출력
    void print(int level) {
        for (auto& food : next) {
            for (int i=0; i<level; i++) {
                cout << "--";
            }
            cout << food.first << "\n";
            food.second->print(level + 1);
        }
    }
};

 

 

 

 

 

 

<참고 사이트>

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85)

트라이 (컴퓨팅) - 위키백과, 우리 모두의 백과사전

https://hanbi97.tistory.com/346

07. 트라이(Trie)