삼항 탐색 트리

컴퓨터 과학에서 삼항 탐색 트리(ternary search tree)는 노드가 이진 탐색 트리와 유사한 방식으로 배열되는 트리(접두사 트리라고도 함)의 유형이지만 이진 트리의 제한인 2개가 아닌 최대 3개의 하위 항목을 갖는다. 다른 접두사 트리와 마찬가지로 삼항 탐색 트리는 증분 문자열 탐색 기능이 있는 연관 맵 구조로 사용될 수 있다. 그러나 삼항 탐색 트리는 속도가 떨어지지만 표준 접두사 트리에 비해 공간 효율적이다. 삼항 탐색 트리의 일반적인 응용 부문에는 맞춤법 검사 및 자동 완성이 포함된다.

설명
삼항 탐색 트리의 각 노드는 단일 문자, 객체 (또는 구현에 따라 객체에 대한 포인터), 그리고 통상적으로 equal kid, lo kid, hi kid라고 불리는 세 개의 자식에 대한 포인터를 저장하며, 이들은 각각 middle (child), lower (child), higher (child)로도 지칭될 수 있다. 노드는 또한 부모 노드에 대한 포인터와 노드가 단어의 끝을 표시하는지 여부를 나타내는 지시자를 가질 수 있다. lo kid 포인터는 문자 값이 현재 노드보다 작은 노드를 가리켜야 한다. hi kid 포인터는 문자가 현재 노드보다 큰 노드를 가리켜야 한다. equal kid는 단어의 다음 문자를 가리킨다.
아래 그림은 "cute", "cup", "at", "as", "he", "us", "i" 문자열을 포함하는 삼항 탐색 트리를 보여준다.

           c
         / | \
        a  u  h
        |  |  | \
        t  t  e  u
      /  / |   / |
     s  p  e  i  s

다른 트라이 자료 구조와 마찬가지로 삼항 탐색 트리의 각 노드는 저장된 문자열의 접두사를 나타낸다. 노드의 중간 서브트리에 있는 모든 문자열은 해당 접두사로 시작한다.

연산

삽입

삼항 탐색 트리에 값을 삽입하는 것은 탐색과 마찬가지로 재귀적으로 또는 반복적으로 정의될 수 있다. 이 재귀적 메서드는 키의 앞부분에서 문자를 잘라내어 점진적으로 짧아지는 키를 고려하여 트리의 노드에서 지속적으로 호출된다. 이 메서드가 생성되지 않은 노드에 도달하면 노드를 생성하고 키의 첫 번째 문자의 문자 값을 할당한다. 새 노드가 생성되었는지 여부와 관계없이 메서드는 문자열의 첫 번째 문자가 노드의 문자 값보다 큰지 작은지를 확인하고 탐색 연산과 마찬가지로 적절한 노드에서 재귀 호출을 수행한다. 그러나 키의 첫 번째 문자가 노드의 값과 같으면 equal kid에서 삽입 프로시저가 호출되고 키의 첫 번째 문자가 잘라진다. 이진 탐색 트리 및 다른 자료 구조와 마찬가지로 삼항 탐색 트리는 키의 순서에 따라 퇴화될 수 있다. 키를 알파벳 순서로 삽입하는 것은 가능한 최악의 퇴화 트리를 얻는 한 가지 방법이다. 키를 무작위 순서로 삽입하면 종종 균형 잡힌 트리가 생성된다.
function insertion(string key) is
	node p := root
    //root가 null인 경우를 대비하여 동일하게 초기화
	node last := root
	int idx := 0
	while p is not null do
        //적절한 서브트리에서 재귀
		if key[idx] < p.splitchar then
			last := p
			p := p.left
		else if key[idx] > p.splitchar then
			last := p
			p := p.right
		else:
            // 키가 이미 트리에 있음
			if idx == length(key) then
				return
            //키에서 문자 제거
			idx := idx+1
			last := p
			p := p.mid
	p := node()
    //마지막으로 null이 아닌 노드의 자식으로 p를 추가 (root가 null이면 root)
    if root == null then
        root := p
	else if last.splitchar < key[idx] then
		last.right := p
	else if last.splitchar > key[idx] then
		last.left := p
	else
		last.mid := p
	p.splitchar := key[idx]
	idx := idx+1
    // 키의 나머지 삽입
	while idx < length(key) do
		p.mid := node()
        p.mid.splitchar := key[idx]
		idx += 1

탐색

특정 노드 또는 노드와 관련된 데이터를 찾기 위해서는 문자열 키가 필요하다. 탐색 절차는 트리의 루트 노드를 확인하고 다음 조건 중 어떤 조건이 발생했는지 확인하는 것으로 시작한다. 문자열의 첫 번째 문자가 루트 노드의 문자보다 작으면 현재 루트의 lo kid를 루트로 하는 트리에서 재귀적 탐색을 호출할 수 있다. 마찬가지로, 첫 번째 문자가 트리의 현재 노드보다 크면 현재 노드의 hi kid를 루트로 하는 트리에서 재귀 호출을 할 수 있다.
마지막 경우로, 문자열의 첫 번째 문자가 현재 노드의 문자와 같으면 키에 더 이상 문자가 없으면 함수는 노드를 반환한다. 키에 문자가 더 있으면 키의 첫 번째 문자를 제거해야 하며, equal kid 노드와 수정된 키를 사용하여 재귀 호출을 수행한다.
이것은 현재 노드에 대한 포인터와 키의 현재 문자에 대한 포인터를 사용하여 비재귀적인 방식으로도 작성될 수 있다.

의사 코드
 function search(string query) is
     if is_empty(query) then
         return false

     node p := root
     int idx := 0

     while p is not null do
         if query[idx] < p.splitchar then
             p := p.left
         else if query[idx] > p.splitchar then
             p := p.right;
         else
             if idx = length(query) then
                 return true
             idx := idx + 1
             p := p.mid

     return false

삭제

삭제 연산은 탐색 트리에서 키 문자열을 검색하고, firstMid라고 불리는 노드(아래 의사 코드에서)를 찾아, firstMid의 중간 자식에서 키 문자열의 탐색 경로 끝까지 좌 또는 우 자식이 없는 경로를 찾는 것으로 구성된다. 이는 키 문자열에 해당하는 삼항 트리에서 고유한 접미사를 나타낸다. 이러한 경로가 없으면 키 문자열이 다른 문자열의 접두사로 완전히 포함되어 있거나 탐색 트리에 없는 것을 의미한다. 많은 구현에서는 후자 경우만 발생하도록 문자열 끝 문자를 사용한다. 그런 다음 경로는 firstMid.mid에서 탐색 경로의 끝까지 삭제된다. firstMid가 루트인 경우, 키 문자열은 트리에서 마지막 문자열이었을 것이므로 삭제 후 루트는 null로 설정된다.
 function delete(string key) is
     if is_empty(key) then
         return

     node p := root
     int idx := 0

 	 node firstMid := null
     while p is not null do
         if key[idx] < p.splitchar then
             firstMid := null
             p := p.left
         else if key[idx] > p.splitchar then
             firstMid := null
             p := p.right
         else
             firstMid := p
             while p is not null and key[idx] == p.splitchar do
             	idx := idx + 1
             	p := p.mid

     if firstMid == null then
         return  // 고유한 문자열 접미사 없음

     // 이 시점에서 firstMid는 문자열의 고유한 접미사가 나타나기 전의 노드를 가리킨다
     node q := firstMid.mid
     node p := q
     firstMid.mid := null // 트리에서 접미사 연결 끊기
     while q is not null do //접미사 경로를 따라가며 노드 삭제
         p := q
         q := q.mid
         delete(p)			// 노드 p와 관련된 메모리 해제
     if firstMid == root then
         delete(root)       //전체 트리 삭제
         root := null

실행 시간
삼항 탐색 트리의 실행 시간은 입력에 따라 크게 달라진다. 삼항 탐색 트리는 여러 유사한 문자열, 특히 공통 접두사를 공유하는 문자열이 주어졌을 때 가장 잘 실행된다. 또는, 삼항 탐색 트리는 상대적으로 짧은 많은 수의 문자열(예: 사전의 단어)을 저장할 때 효과적이다.
삼항 탐색 트리의 실행 시간은 이진 탐색 트리와 유사하며, 일반적으로 로그 시간에 실행되지만 퇴화(최악)의 경우 선형 시간에 실행될 수 있다. 또한 런타임을 고려할 때 문자열의 크기도 염두에 두어야 한다. 예를 들어, 길이 k의 문자열에 대한 탐색 경로에는 트리에서 중간 자식을 따라 k번의 순회가 있을 뿐만 아니라 트리에서 좌우 자식을 따라 로그 수의 순회가 있을 것이다. 따라서 매우 큰 문자열의 수가 적은 삼항 탐색 트리에서는 문자열의 길이가 런타임을 지배할 수 있다.

삼항 탐색 트리 연산의 시간 복잡도:

   평균 실행 시간  최악 실행 시간 탐색  O(log n + k)  O(n  + k) 삽입  O(log n  + k)  O(n  + k) 삭제  O(log n  + k)  O(n  + k)

다른 자료 구조와의 비교

트라이
다른 접두사 트리보다 느리지만, 삼항 탐색 트리는 공간 효율성으로 인해 더 큰 데이터 세트에 더 적합할 수 있다.

해시 맵
해시 테이블도 문자열을 값에 매핑하는 삼항 탐색 트리 대신 사용될 수 있다. 그러나 해시 맵은 삼항 탐색 트리보다 더 많은 메모리를 사용하는 경우가 많다(하지만 트라이만큼은 아니다). 또한, 해시 맵은 전체 문자열을 비교해야 하고 처음 몇 문자만 비교할 수 없기 때문에 동일한 자료 구조에 없는 문자열을 보고하는 데 일반적으로 더 느리다. 삼항 탐색 트리가 해시 맵보다 더 빠르게 실행된다는 일부 증거가 있다. 또한, 해시 맵은 근접 이웃 탐색과 같은 삼항 탐색 트리의 많은 용도를 허용하지 않는다.

DAFSA (결정적 비순환 유한 상태 오토마타)
사전 단어 저장이 필요한 경우(즉, 각 단어에 대한 보조 정보 저장이 필요하지 않은 경우), 최소 결정적 비순환 유한 상태 오토마타(DAFSA)는 트라이 또는 삼항 탐색 트리보다 적은 공간을 사용한다. 이는 DAFSA가 저장되는 다른 단어의 동일한 접미사(또는 부분)에 해당하는 트리의 동일한 분기를 압축할 수 있기 때문이다.

사용
삼항 탐색 트리는 많은 수의 문자열을 임의의 순서로 저장하고 검색해야 하는 많은 문제를 해결하는 데 사용될 수 있다. 가장 일반적이거나 유용한 몇 가지 용도는 다음과 같다.

 트라이를 사용할 수 있지만 메모리 소모가 적은 구조가 선호되는 경우.
 문자열을 다른 데이터에 매핑하기 위한 빠르고 공간 절약적인 자료 구조.
 자동 완성을 구현하기 위해.
 맞춤법 검사기로.
 근접 이웃 탐색(맞춤법 검사는 특별한 경우임).
 특히 여러 비키 필드로 색인화하는 것이 바람직한 데이터베이스로.
 해시 테이블 대신.

 같이 보기 
 트라이 (컴퓨팅)
 이진 탐색 트리
 해시 테이블

 각주 

 외부 링크 
 Ternary Search Trees  page with papers (by Jon Bentley and Robert Sedgewick) about ternary search trees and algorithms for "sorting and searching strings"
 Ternary Search Tries – a video by Robert Sedgewick
 TST.java.html Implementation in Java of a TST by Robert Sedgewick and Kevin Wayne

분류:트리 구조
분류:검색 알고리즘