[CS50] 자료구조 - 트라이

트라이(Trie) 데이터 구조

‘트라이(Trie)’는 기본적으로 ‘트리’ 형태의 자료 구조이다. 특이한 점은 각 노드가 ‘배열’로 이루어져 있다는 것이다.

 

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

 

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

 

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

 

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

 

 

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

 

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

 

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

 

 

References

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

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