트라이(Trie)

이 자료구조를 몰라도 사는데 지장이 없었지만 이 자료구조로 풀리는 문제가 생각보다 있어서 배우게 되었습니다. 대체로 구현하기 쉬운 자료구조에 속합니다.

검색이 빠른 자료구조 입니다. reTRIEval(검색)에서 유래되었습니다. digital tree, prefix tree라고도 불립니다. 트라이는 시간복잡도는 O(len)으로 탐색시 길이만큼의 시간복잡도를 갖습니다. 하지만 공간복잡도가 지랄맞기로 유명합니다. 그렇기 때문에 긴 문자열에는 사용을 자제하는 것이 좋습니다. 공간복잡도는 O(포인터 크기*포인터 배열 갯수*트라이 노드수)입니다.

#include <iostream> #include <algorithm> using namespace std; const int trieCnt = 26; struct Trie {     Trie *children[trieCnt];     bool terminal;       Trie() {         fill(children, children + trieCnt, nullptr);         terminal = false;     }     ~Trie() {         for (int i = 0; i < trieCnt; i++)              if (children[i])                  delete children[i];     }       bool insert(const char *key) {         if (*key == '\0')              terminal = true;         else {             int nextKey = *key - 'a';             if (!children[nextKey])                 children[nextKey] = new Trie;         }     }          bool find(char *key) {         if (*key == '\0') return false;         if (terminal) return true;         int next = *key - 'a';         return children[next]->find(key + 1);     } } Colored by Color Scripter

cs