trie (try로 발음)는 영어 단어와 같이 컬렉션으로 표현할 수있는 데이터 저장을 전문으로하는 트리입니다.

문자열의 각 문자는 노드에 매핑됩니다. 각 문자열의 마지막 노드는 종료 노드로 표시됩니다 (위 이미지의 점). Trie의 이점은 접두사 일치와 관련하여 살펴 보는 것이 가장 좋습니다.

이 장에서는 먼저 트라이의 성능을 배열과 비교합니다. 그런 다음 처음부터 트라이를 구현합니다!

Example

문자열 모음이 제공됩니다. 접두사 일치를 처리하는 구성 요소를 어떻게 구축 하시겠습니까?

한 가지 방법이 있습니다.

class EnglishDictionary { 
	private var words: [String] 
	func words(matching prefix: String) -> [String] {
		words.filter { $0.hasPrefix(prefix) }
	}
}

words (matching :)는 문자열 모음을 살펴보고 접두사와 일치하는 문자열을 반환합니다.

단어 배열의 요소 수가 적으면 합리적인 전략입니다. 그러나 수천 단어 이상을 다루는 경우 단어 배열을 통과하는 데 걸리는 시간은 용납 될 수 없습니다. words (matching :)의 시간 복잡도는 O (k * n) 입니다. 여기서 k는 모음에서 가장 긴 문자열이고 n은 확인해야 할 단어의 수입니다.

Google이 구문 분석해야하는 단어의 수를 상상해보십시오

trie 데이터 구조는 이러한 유형의 문제에 대해 우수한 성능 특성을 갖습니다. 여러 하위를 지원하는 노드가있는 트리로서 각 노드는 단일 문자를 나타낼 수 있습니다.

검은 점으로 표시되는 특수 표시기 (터미네이터)를 사용하여 루트에서 노드로 문자 모음을 추적하여 단어를 형성합니다. 트리의 흥미로운 특징은 여러 단어가 동일한 문자를 공유 할 수 있다는 것입니다.

Trie의 성능 이점을 설명하기 위해 접두사 CU가있는 단어를 찾아야하는 다음 예를 고려하십시오.

먼저 C가 포함 된 노드로 이동합니다. 그러면 트리의 다른 분기가 검색 작업에서 빠르게 제외됩니다.