[Algorithm] 트라이

트라이

트라이는 문자열 집합을 관리하는 트리이다.

간선마다 알파벳 하나가 대응되고, 자식 노드와 연결된 간선 중 어떤 알파벳과 대응되는 간선은 최대 하나이다.

트리를 내려가면서 만나는 간선의 알파벳을 모두 이으면 원래 문자열을 얻을 수 있고, 두 문자열의 접두사가 같다면 그 길이만큼의 간선을 트리에서 공유한다.

T는 문자열의 끝이라는 표시. 루트 노드에서 T 노드로 가는 경로의 알파벳을 이으면 집합에 포함된 문자열을 얻을 수 있다다.

만약 이러한 표시가 없다면 트라이에서 원래 문자열 집합을 전부 뽑아낼 수 없다.

---

트라이에서 문자열의 삽입/삭제/탐색은 언제나 O(문자열의 길이)이다. 이는 해시와 같은 시간 복잡도로 매우 빠르다.

해시는 데이터 순서를 무작위로 저장하지만, 트라이는 다르다. 트라이도 트리의 한 종류이기 때문에 Binary Search Tree의 동작을 응용하여 k번째 문자열 찾기, 같은 접두사를 가지는 문자열 개수 세기 등 해시 테이블로는 할 수 없는 동작까지 할 수 있다.

트라이의 공간 복잡도는 O(삽입된 문자열의 총 길이) 이다.