[CS50] 트라이

지금까지 연결 리스트부터 해시 테이블까지 공부해봤는데 혹시 문자열이 일정한 경우라면 어떤 게 가장 최적일까요? 또 이 문자열들을 저장하고 관리하는 건 어떨까요? 오늘은 트라이라는 자료구조에 대해 공부해보도록 하겠습니다.

 

트라이라는 자료구조는 기본적으로는 트리형태를 가지고 있지만, 이때 특이한점은 각 노드가 배열로 이루어져 있다는 것입니다. 만약 알파벳 a ~ z 까지로 이루어진 문자열 값을 저장하려고 한다면 이 노드는 a부터 z까지의 값을 가지는 배열이 되고 각 배열의 요소는 다음 층의 노드(a ~ z 배열)를 가리키게 됩니다.

 

이게 무슨 말이냐 하면 예를들어 Harry, Hagrid, Hermione 이 세 문자열을 트라이에 저장해보겠습니다.

그럼 다음과 같이 표시할 수 있습니다.

초록색은 각 문자열의 마지막 문자입니다.

작아서 잘 안보이겠지만 트라이로 저장하면 맨 위의 노드(첫 번째 줄)인 H부터 시작해서 그다음 A와 E... 이렇게 Harry, Hagrid, Hermione 문자열을 하나하나 끝까지 저장하게 됩니다.

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

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

그만큼 빠르게 이름을 찾을 수 있다는 뜻입니다.

 

그렇다면 트라이의 단점은 뭐가 있을까요?

위 그림에도 나오듯 문자열 3개를 트라이에 저장하는데 저 화면을 꽉 채울 만큼 의 배열이 사용됩니다. 즉 해시 테이블이나 다른 자료구조보다는 많은 메모리를 사용해야 한다는 점이 있습니다.

 

---

출처

본 내용은 CS50의 2019년 강의를 듣고 작성했습니다. (개념이 어느 정도 정리되면 최신강의도 다시 듣고 수정할 내용 있으면 수정하겠습니다.)

 

강의 자료는 EdX에서 무료로 사용할 수 있고 boostcourse에서 한글 강의로도 들을 수 있습니다.