Trie

Prefix tree라고도 불리는 Trie는 집합 내에서 특정 키를 찾는데 사용되는 트리 데이터 구조다. 키는 대부분의 경우 문자열을 나타내며 노드는 키의 개별 문자를 사용한다. 키에 접근하기 위해 노드간의 링크를 따라 DFS를 수행한다. BST와 다르게 Trie는 연관된 키가 아닌, 노드에 위치에서 연결된 하위 노드들을 연결한다. 노드의 모든 하위 노드는 상위 노드와 연결된 문자열의 공통 접두사를 의미하며, 루트는 빈 문자열을 나타낸다.

• Trie의 각 노드는 radix tree를 사용해 메모리 최적화가 가능하다.

• Trie는 접두사 매칭, 문자열 근사 일치 등에 활용된다.

• Aho-Corasick은 문자열 근사 일치에 사용되는 알고리즘 중 하나로 Trie(논문에서는 goto function)을 기반으로 동작한다.