8) 트라이

트라이란

‘트라이’는 기본적으로 ‘트리’ 형태의 자료 구조이며, 각 노드가 ‘배열’로 이루어져있습니다.

예시

Hermione, Harry, Hagrid 세 문자열을 트라이에 넣어주었습니다.

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

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

각 문자를 보며 트리를 탐색해나가기만 하면 되니까요.

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

생각해보기

트라이가 해시 테이블에 비해 가지는 장점과 단점은 무엇일까요?

언제나와 같이, 빠르다는 장점과 메모리를 많이 차지한다는 단점을 가지고 있다.

note

written by CaesiumY