[면접대비] 트라이(trie)

트라이(trie)

트라이는 다른 구조처럼 명확한 정의가 있는 것이 아니라, 조금씩 다르게 구현한다.

트라이 노드는 자식 노드의 개수에 제한이 없다.

트라이 노드마다 해시 테이블을 포함하여, 키는 알파벳이고 값은 트라이의 다른 노드다.

트라이 구조의 단어 저장 구현

• 각 알파벳은 key를 나타낸다.
• *는 단어가 끝났음을 알려준다. 값은 null이다.
• *의 값을 인기도와 같이 순위를 지정할 수 있다면, 자동완성 기능을 제공할 때 인기도에 따라 제공할 수도 있다.
• {*, 't'}에서 *와 t는 모두 key다.

 

출처: 누구나 자료 구조와 알고리즘, 그림17-6

트라이 구조의 시간복잡도

탐색: 검색 문자열 내 문자 수에 따라 달라진다. O(K)

• 변수를 만든다. 처음 시작할 때 이 변수는 루트 노드를 가리킨다.
• 검색 문자열의 첫 문자를 키로 하는 자식이 있는지 확인한다.
• 자식이 없다면 none을 반환한다.
• 자식이 있다면 변수를 그 자식 노드로 업데이트한다.
• 검색 문자의 다음 문자로 순회하면서 확인한다.

삽입: 검색 문자열 내 문자 수에 따라 달라진다. O(K)

 

트라이 구조를 적용하기 좋은 경우

데이터의 양(N)에 영향을 받지 않으므로 빠른 검색에 효과적이다.