Trie (“retrieval”, Prefix Tree, ‘트리’ 또는 ‘트라이’로 발음)는 string을 key로 하는 정렬된 트리다. 하나의 부모를 공유하는 자식들은 동일한 prefix를 갖는다. 사전을 구성할 때 단어의 중복 저장을 피할 수 있어 나름 압축효과가 크다. BST(Binary Search Tree, O(logN))보다도 성능이 좋아서 m사이즈의 스트링에서 O(m)의 성능을 보인다. 충돌(collision)이 발생할 수 있는 완벽하지 않은 해쉬테이블(imperfect hash table) 보다 성능이 좋다. Approximate Matching Algorithm으로 활용가능하다.
