트라이: 단계마다 문자열의 문자 하나를 기반으로 분기하는 자료 구조.

Section 1. 문자열로 이뤄진 이진 탐색 트리

1.1 트리에 저장한 문자열

• 이진 탐색 트리는 크기 순서대로 정렬할 수 있는 것은 모두 저장할 수 있다.
• 문자열을 이진 탐색 트리에 저장하기 위해서 문자열을 알파벳 순서로 정렬할 수 있다.
• 트리가 균형 잡혀 있으면 탐색의 최악의 경우 비용은 항목 수의 로그에 비례한다.
• 하지만 한가지 중요한 사실을 놓치고 있다. 바로 각각 비교하는 데 드는 비용
  • 이 트리 탐색 비용은 문자열의 개수와 각 문자열의 길이 모두에 따라 결정된다.
  • 이는 복잡성에 새로운 차원이 추가된다는 말이다.
• 절약하기 위해서는 문자열 자료 구조의 두 가지 중요한 측면을 고려해야 한다.
  • 바로 문자열이 시퀀스라는 사실과 문자의 가짓수가 제한되어 있다는 사실이다.

1.2 문자열 비교의 비용

• 첫 번째는 문자열 비교의 순차적인 성질이다.
  • 알파벳에 따른 문자열 순서를 결정하기 위해서는 문자열의 첫 번째 문자에서 시작해 차이를 발견할 때까지 각각의 문자를 순차적으로 비교해야 한다.
• 이진 탐색 트리에서 문자열에 대한 순차 비교는 두 수의 비교보다 본질적으로 더 비싸다.
• 두 번째는 많은 언어에서 문자열의 각 위치에 포함될 수 있는 문자가 많지 않다는 것이다.
  • 영어 단어는 대소문자 구분을 무시하면 정확히 26개 문자만 사용한다. 숫자나 다른 문자를 포함하더라도 실제로 사용하는 유효한 문자 집합은 제한적이다.

2. 트라이

트라이: 문자열을, 접두사를 기준으로 다른 하위 트리로 분할하는 트리 기반 자료 구조.

• 트라이는 지금까지의 접두사(순차적 비교)를 기준으로 트리의 가지를 나눈다.
  • 여기에서는 더 나아가, 트리가 두 분기보다 더 많은 분기(사용 가능한 문자의 개수)로 분할되도록 허용하겠다.
• 트라이는 루트 노드에서 시작한다
  • 루트 노드는 빈 접두사를 나타낸다.
• 각 트라이 노드의 가지를 포인터의 배열로 구현할 수 있다.