읽고 나면 진짜 쉬워지는 자료 구조 - 6. 트라이와 적응형 자료 구조

이진 탐색 트리에서 문자열의 특성을 추가로 고려해 최적화한 자료 구조

🔖 6.1 문자열로 이뤄진 이진 탐색 트리

이진 탐색 트리의 한계

• 이진 탐색 트리는 순서대로 정렬할 수 있는 것은 모두 저장할 수 있다.

• 언뜻 보기에는 이진 탐색 트리는 문자열 데이터를 탐색하는 간단하고 효율적인 메커니즘을 제공하는 것 같다.

• 하지만 각각 비교하는 데에 드는 비용을 주목해야 한다.

• 최악의 경우 문자열 비교 연산 비용은 문자열 자체 길이에 비례한다.

문자열 비교의 비용과 한계

• 이진 탐색 트리에서 문자열에 대한 순차 비교는 두 수의 비교보다 더 비싸다.

• 많은 언어에서 문자열의 각 위치에 포함될 수 있는 문자가 많지 않다는 점도 있다.

🔖 6.2 트라이

트라이란?

• 문자열을 접두사를 기준으로 다른 하위 트리로 분할하는 트리 기발 자료구조다.

• 각 노드에서 데이터를 두 집합으로 분할하는 대신, 트라이는 지금까지의 접두사를 기준으로 트리의 가지를 나눈다.

• 느린 메모리 접근 속도를 가진 컴퓨터에서 파일 탐색을 개선하기 위해 등장했다.

트라이의 특징

• 트라이의 각 노드는 지금까지 비교한 문자열의 접두사를 나타낸다.

• 이진 탐색 트리와 마찬가지로 트라이 또한 루트 노드에서 시작하며, 각 노드는 둘 이상의 자식을 가질 수 있다.

• 트라이는 모든 노드에서 극적인 다중 분기를 수행한다.

• 이진 탐색 트리와는 다르게 트라이에서는 모든 노드가 항목을 나타내진 않는다.

• 현재 노드의 접두사 등 유용한 정보를 트라이 노드에 저장할 수 있다.

트라이 탐색하기

• 전체 문자열을 비교하거나 접두사 앞 부분은 비교할 필요가 없어 효율적이다.

• 코드로 구현한다면 현재 단계에서 확인해야 하는 문자의 위치를 나타내는 인덱스를 재귀 함수에 전달해 추적할 수 있다.

• Trie wrapper를 사용하면 루트 노드에 대한 참조와 재귀 함수에 필요한 카운터를 숨겨 단순화할 수 있다.

• 이진 탐색 트리와는 달리 성공적인 트라이 탐색의 비교 횟수는 트라이에 저장된 문자열의 갯수와 무관하다.

트라이 탐색 코드

function TrieNodeSearch(current, target, index) {
  if (index === target.length) { // ①
    if (current.isEntry) {
      return current;
    } else {
      return null;
    }
  }

  const nextLetter = target[index]; // ②
  const nextIndex = LetterToIndex(nextLetter); // ③
  const nextChild = current.children[nextIndex]; // ④

  if (nextChild === null) {
    return null;
  } else {
    return TrieNodeSearch(nextChild, target, index + 1);
  }
}

// LetterToIndex는 특정 문자(nextLetter)를 인덱스 숫자로 변환하는 함수
// current는 현재 노드를 나타내고, target은 탐색할 문자열이며, index는 현재 탐색 중인 문자열의 위치

노드 추가와 제거

• 트라이도 이진 탐색 트리와 같이 데이터 변화를 정확하게 표현하는 동적 자료 구조다.

• 이진 탐색 트리에서의 삽입과는 달리 한 항목을 삽입하는 동안 노드를 여러 개 추가할 수 있다.

🔖 6.3 트라이가 중요한 이유

트라이의 이점

• 더 많은 문자열을 추가하고 공통 접두사를 가지는 문자열 수가 늘어날수록 트라이가 더 효율적이다.

• 문자열 비교 자체가 비용이 많이 들어, 공통 접두사를 기준으로 확인하고 비교한다면 큰 이점을 얻을 수 있다.

트라이 사용 예시

• 짧은 알파벳과 숫자로 이루어진 시리얼 번호, 모델 번호 등 구조적 레이블 추적 자료 구조

• 수십억 개의 제품이 있더라도 시리얼 번호의 접두사를 활용하면 저장 공간을 절약할 수 있다.

• 핵심은, 연산 비용을 최적화할 때 문자열의 구조를 더 활용할 수 있다는 점이다.