[CS50] 6.8 트라이

트라이는 트리 형태의 자료 구조로 각 노드가 배열로 이루어져있다.

 

예를 들어 Harry라는 영어 알파벳으로 된 문자열이 있으면

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

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

(h,a,r,r,y)

 

 

트라이를 이용했을 때 검색시간은 O(n)이다.

각 문자를 보며 탐색하면 되므로 문자열의 길이만큼이 된다.

하지만 보통 이름들은 그렇게 크지 않은 상수값이기 때문에 O(1)로 보면 된다.

 

 

이렇게 트라이는 검색 시간이 O(1)로 짧지만,

그만큼 메모리를 엄청 많이 잡아먹는다.

 

 

 

 

 

출처: www.boostcourse.org/cs112