Trie

Trie란?

문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 비선형 자료구조

특징

• 검색어 자동완성, 사전 찾기 등에 응용된다.
• 문자열 탐색 시, 단순하게 비교하는 것 보다는 효율적이다.
• 문자열의 길이가 L일경우 탐색 및 삽입은 O(L)의 시간 복잡도를 가진다.
• 각 노드의 자식에 대한 링크를 전부 가지고 있기에 저장공간을 많이 사용한다.

구조

• 루트노드는 비어있다.
• 각 간선은 추가될 문자를 키로 가진다.
• 각 노드는 이전 노드의 값 + 간선의 키 값을 가진다.
• 해시 테이블과 연결리스트를 이용하여 구현할 수 있다.