디지털 트리

17장 트라이(trie)해 보는 것도 나쁘지 않다

스마트폰의 자동 완성 기능은 어떻게 동작할까? 특수한 트리 기반 자료 구조를 사용하면 O(1)의 속도로 원하는 단어에 접근할 수 있다.(!) 트라이는 자동 완성이나 자동 수정 같은 중요한 기능을 지원한다. 1. 트라이 트라이는 프리픽스 트리Prefix tree 혹은 디지털Digital tree 트리라고도 부른다. 트라이는 명쾌하게 설명되지 않는다. 교재마다, 설명마다 트라이를 조금씩 다르게 구현한다. 1.1 트라이 노드 트라이도 다른 노드를 가리키는 노드들의 컬렉션이다. 트라이 노드는 이진 트리와 다르게 자식 노드 개수에 제한이 없다. 이 교재의 구현에서는 각 트라이 노드마다 해시 테이블을 포함하며, 해시 테이블에서 키는 알파벳이고 값은 트라이의 다른 노드다. 즉, 해시 테이블에서 키는 개개 문자열이고 ..