정수나 실수형 변수는 그 크기가 항상 정해져 있기 때문에 비교에 상수 시간이 걸린다고 가정해도 되는 반면, 문자열 변수를 비교하는 데는 최악의 경우 문자열의 길이에 비례하는 시간이 걸린다.
정수나 실수 키에 대해서는 잘 동작하는 탐색 자료 구조들이 문자열을 키로 사용할 때는 시간이 오래 걸릴 수 있다.
예를 들어, N개의 원소를 갖는 이진 검색 트리에서 원하는 원소를 찾으려면 O(lgN)번 비교.
문자열의 경우는 문자열 길이에 비례하므로 문자열의 최대 길이 M을 곱한 O(MlgN)이다.
trie는 집합 내에서 원하는 원소를 찾는 작업을 O(M) 시간만에 할 수 있다. //문자열의 최대 길이 M
문자열 집합 S = {”BE”, “BET”, “BUS”, “TEA”, “TEN”}
짙은 회색으로 표시된 노드들이 종료 노드들이다.
트라이의 중요한 속성은 루트(길이 0인 문자열)에서 한 노드까지 내려가는 경로에서 만나는 글자들을 모으면 해당 노드에 대응되는 접두사를 얻을 수 있다는 것이다.
즉, 노드에 접두사를 저장하는 게 아니라 자손으로 가지는 알파벳을 저장하면 된다. (+ 종료 노드인지 나타내는 불린 값)
알파벳은 고정 길이 배열로 한다. 이와 같은 구조는 메모리를 많이 쓰지만 다음 노드를 찾는 과정에서 어떤 탐색도 필요하지 않다는 장점이 있다.