[Data Structure] 트라이

'트라이'는 기본적으로 ' 트리' 형태의 자료 구조이다.

특이한 점은 각 노드가 '배열'로 이루어져 있다는 것이다.

예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장 한다고 하면

이 노드는 a부터 z까지의 값을 가지는 배열이 된다.

 

그리고 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z배열)를 가리킨다.

 

아래 그림과 같이 Hermione, Harry, Hagrid 세 문자열을 트라이에 저장해보자

루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가면서 노드를 이어주면 된다.

단순히 문자열의 각 문자를 보며 트리를 탐색해나가기만 하면 되기때문에,

위와 같은 트라이에서 값을 검색하는데 걸리는 시간은 '문자열의 길이'에 의해 한정된다.

 

일반적인 영어 이름의 길이를 n이라고 할때, 검색 시간은 O(n)이 되지만,

대부분의 이름은 그리 크지 않은 상수값이여서 O(1)이나 마찬가지라고 볼 수 있다.