읽고 나면 진짜 쉬워지는 자료 구조 - 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 트라이가 중요한 이유
트라이의 이점
더 많은 문자열을 추가하고 공통 접두사를 가지는 문자열 수가 늘어날수록 트라이가 더 효율적이다.
문자열 비교 자체가 비용이 많이 들어, 공통 접두사를 기준으로 확인하고 비교한다면 큰 이점을 얻을 수 있다.
트라이 사용 예시
짧은 알파벳과 숫자로 이루어진 시리얼 번호, 모델 번호 등 구조적 레이블 추적 자료 구조
수십억 개의 제품이 있더라도 시리얼 번호의 접두사를 활용하면 저장 공간을 절약할 수 있다.
핵심은, 연산 비용을 최적화할 때 문자열의 구조를 더 활용할 수 있다는 점이다.
Last updated