트라이

문자열 여러 개를 글자 단위로 쪼개 트리에 담는 자료구조다. 루트에서 한 글자씩 내려가면 단어가 되고, 앞부분이 같은 단어는 같은 가지를 나눠 쓴다. 그래서 「app」으로 시작하는 단어를 찾을 때 app까지 세 칸만 내려가면 그 아래가 전부 답이라 자동완성에 쓴다.