[자료구조] 트라이

학습 목표

트라이의 원리와 구조를 설명할 수 있다.

왜?

문자열의 길이가 일정한 경우 이 문자열들을 저장하고 관리하는 데 최적의 자료 구조는 무엇일까?
연결 리스트, 트리, 해시 테이블이 최선의 방안이 될 수 있을까?
이번엔 트라이라는 자료 구조에 대해 알아보자.

1. 트라이?

트라이는 retrieval의 약자로, 기본적으로 트리형태의 자료 구조이고, 문자열을 빠르게 탐색하게 해주는 자료구조이다.
즉 문자열 탐색에 특화된 자료구조이다. 특이한 점은 각 노드가 배열로 이루어져있다는 것이다.

예를 들어 알파벳으로 이루어진 문자열 값을 저장한다고 한다면, 이 노드는 a부터 z까지의 값을 가지는 배열이 된다. 그리고 이 알파벳은 다음 층의 노드(a~z까지의 배열)를 가리킨다.

Hermione, Harry, Hagrid 세 문자열을 트라이에 저장해보자.

• 루트 노드(H)를 시작으로 각 노드가 가리키는 화살표를 따라가면서 노드를 이어주면 된다.
• 트라이에서 값을 검색하는 데 걸리는 시간은 문자열의 길이에 의해 한정된다.
  문자열의 각 문자를 보면서 트리를 탐색해가면 되기 때문이다.
• 일반적인 영어 이름의 길이를 n이라고 했을 때, 검색 시간은 O(n)이 되는데, 대부분의 이름은 그렇게 크지 않은 상수값이기 때문에 O(1)이나 마찬가지라고 볼 수 있다.