트라이 ( Trie ) 자료구조

트라이

문자열에 특화된 자료구조이며, 문자열 집합을 표현하는 트리 자료구조이다.

우리가 원하는 원소를 O(n)으로 찾을 수 있다.

 

위 그림을 보면, blog를 예로 들 때, b, bl, blo, blog 순으로 트리에 저장되어 있는 것을 볼 수 있다.

이는 각각 blog의 접두사들이다. 

 

이러한 이유들 때문에 트라이는 접두사 트리 ( Prefix Tree )라고도 불린다고 한다.

 

 

 

트라이 단점

트라이의 치명적 단점은 공간 복잡도다.

문자열에서 각각의 문자별로 하나의 노드가 필요한데, 예를 들어 알파벳 소문자 a~z가 포함되어있다면

기본적으로 26개의 포인터 배열을 가지고 있어야 하는 문제가 생긴다.

 

이렇게 되면, 최종 메모리는 ( 포인터 크기 * 포인터 배열 개수 * 트라이에 존재하는 총 노드의 개수 ) 가 되게 된다.

 

 

 

 

참고

www.crocus.co.kr/1053

트라이(Trie) 자료구조