[CS50] 자료구조: 트라이
❄️ David Malan 교수의 모두를 위한 컴퓨터 과학(CS50 2019)을 바탕으로 정리한 내용입니다.
‘트라이’는 기본적으로 ‘트리’ 형태의 자료 구조입니다.
특이한 점은 각 노드가 ‘배열’로 이루어져있다는 것입니다.
예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장한다고 한다면 이 노드는 a부터 z까지의 값을 가지는 배열이 됩니다.
그리고 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z 배열)를 가리킵니다.
아래 그림과 같이 Hermione, Harry, Hagrid 세 문자열을 트라이에 저장해보겠습니다.
루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가면서 노드를 이어주면 됩니다.
위와 같은 트라이에서 값을 검색하는데 걸리는 시간은 ‘문자열의 길이’에 의해 한정됩니다.
단순히 문자열의 각 문자를 보며 트리를 탐색해나가기만 하면 되니까요.
일반적인 영어 이름의 길이를 n이라고 했을 때, 검색 시간은 O(n)이 되지만, 대부분의 이름은 그리 크지 않은 상수값(예, 20자 이내)이기 때문에 O(1)이나 마찬가지라고 볼 수 있습니다.
생각해보기
트라이가 해시 테이블에 비해 가지는 장점과 단점은 무엇일까요?
- 장점: O(n)인 해시 테이블에 비해 O(1)으로 검색 속도가 빠릅니다.
- 단점: 각 노드가 배열로 이루어져있기 때문에 해시 테이블에 비하여 훨씬 많은 메모리를 필요로 합니다.
💛 개인 공부 기록용 블로그입니다. 👻