Trie

정의

트리 기반 데이터 구조를 가지는 문자열 검색 작업에 효율적인 자료 구조

vs HashTable

• 접두사 기반 검색에 유리하다.
• 모든 단어를 알파벳 순으로 쉽게 인쇄할 수 있다.
• hash 오버헤드가 없다.
• 문자열 검색 시 O(L)의 시간 복잡도를 갖는다.

property

• 하나의 루트 노드를 갖는다.
• 각 노드는 문자열을 나타내고 간선은 문자를 나타낸다.
• 모든 노드는 해시맵 또는 포인터 배열로 구성
• 루트 노드에서 각 노드까지는 문자 또는 문자열을 의미한다.

insert

ant, and 단어 저장 예시

• and
  • and의 첫 글자가 a 이므로 a 노드를 찾아 표시한다.
  • 두번째 글자인 n으로 이동 후 표시한다.
  • 세번째 글자인 d로 이동후 표시한다.
• ant
  • ant의 첫 글자가 a 이르모 a 노드를 찾는다.
  • a 노드에 표시가 되어 있으므로 이동한다.
  • 두번째 글자인 n으로 이동한다.
  • n 노드에 표시가 되어 있으므로 이동한다.
  • 세번째 글자인 t로 이동후 표시한다.