6: 자료구조-7(트라이:Retrieval)

트라이 :  ‘트리’ 형태의 자료 구조 각각의 노드가 배열로 이루어져 있음

 

 

- 트라이에는 많은 메모리가 들지만 자료 구조 안에 있는 이름이나 단어를 찾는 데 일정한 시간을 가짐

- 맨 위에 있는 배열은 트라이의 루트

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

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

 - 그림과 같이 Hermione, Harry, Hagrid 세 문자열을 트라이에 저장해 보면 루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가면서 노드를 이어주면 됨

 

- 단순히 문자열의 각 문자를 보며 트리를 탐색해 나가기만 하면 되어서 위와 같은 트라이에서 값을 검색하는데 걸리는 시간은 ‘문자열의 길이’에 의해 한정됨

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

- 트라이의 단점은 상수 시간의 실행 시간을 제공하기 위해 아주 많은 양의 메모리를 사용함

 

 

https://www.boostcourse.org/cs112/joinLectures/41307

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