Trie

digital tree, prefix tree라고도 한다.

• k-ary search tree의 일종이다.
• key는 대부분 문자열이다.
• 모든 자식 노드들은 부모 노드와 연결된 문자열이랑 공통된 접두사를 가진다.
• Root node는 빈 문자열과 연결된다.
• radix tree를 이용하면 메모리 최적화가 가능하다.
• Insert, Search 모두 O(M) 시간에 수행된다. (M은 key의 길이)
• 자동완성, 유사 문자열 검색approximate string matching, 철자 검사spell checking 같은 문자열 검색 알고리즘에 효과적이다.

k-ary tree (m-ary tree)
tree of degree트리의 최대 차수가 k 이하인 트리를 말한다.

구현

가장 쉬운 구현으로는 각 노드에 각각의 문자에 해당하는 하위 노드 포인터의 배열을 담는다.
(문자가 영소문자이면 26개이다.)

이는 간단하지만 메모리 낭비가 심하다.

Radix tree

유일한 자식 노드는 부모 노드와 병합해 공간 최적화를 한 트리이다.