트라이

‘트라이’는 기본적으로 ‘트리’ 형태의 자료 구조입니다.

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

예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장한다고 한다면 이 노드는 a부터 z까지의 값을 가지는 배열이 됩니다.

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

 

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

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

 

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

단순히 문자열의 각 문자를 보며 트리를 탐색해나가기만 하면 되니까요.

일반적인 영어 이름의 길이를 n이라고 했을 때, 검색 시간은 O(n)이 되지만, 대부분의 이름은 그리 크지 않은 상수값(예, 20자 이내)이기 때문에 O(1)이나 마찬가지라고 볼 수 있습니다.

 

https://www.boostcourse.org/cs112/lecture/119043?isDesc=false 

모두를 위한 컴퓨터 과학 (CS50 2019)