삼항 탐색 트리

delete_worst= O(*n*) 컴퓨터 과학에서 **삼항 탐색 트리**(ternary search tree)는 노드가 이진 탐색 트리와 유사한 방식으로 배열되는 트리(접두사 트리라고도 함)의 유형이지만 이진 트리의 제한인 2개가 아닌 최대 3개의 하위 항목을 갖는다. 다른 접두사 트리와 마찬가지로 삼항 탐색 트리는 증분 문자열 탐색 기능이 있는 연관 맵 구조로 사용될 수 있다. 그러나 삼항 탐색 트리는 속도가 떨어지지만 표준 접두사 트리에 비해 공간 효율적이다. 삼항 탐색 트리의 일반적인 응용 부문에는 맞춤법 검사 및 자동 완성이 포함된다.
# 설명
삼항 탐색 트리의 각 노드는 단일 문자, 객체 (또는 구현에 따라 객체에 대한 포인터), 그리고 통상적으로 equal kid, lo kid, hi kid라고 불리는 세 개의 자식에 대한 포인터를 저장하며, 이들은 각각 middle (child), lower (child), higher (child)로도 지칭될 수 있다.url=http://www.drdobbs.com/database/184410528 노드는 또한 부모 노드에 대한 포인터와 노드가 단어의 끝을 표시하는지 여부를 나타내는 지시자를 가질 수 있다. 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에서 삽입 프로시저가 호출되고 키의 첫 번째 문자가 잘라진다. 이진 탐색 트리 및 다른 자료 구조와 마찬가지로 삼항 탐색 트리는 키의 순서에 따라 퇴화될 수 있다.url=http://lukaszwrobel.pl/blog/ternary-search-tree 키를 알파벳 순서로 삽입하는 것은 가능한 최악의 퇴화 트리를 얻는 한 가지 방법이다. 키를 무작위 순서로 삽입하면 종종 균형 잡힌 트리가 생성된다. 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.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.left := p else last.mid := p p.splitchar := key[idx] idx := idx+1 // 키의 나머지 삽입 while 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.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번의 순회가 있을 뿐만 아니라 트리에서 좌우 자식을 따라 로그 수의 순회가 있을 것이다. 따라서 매우 큰 문자열의 수가 적은 삼항 탐색 트리에서는 문자열의 길이가 런타임을 지배할 수 있다.url=https://www.cs.upc.edu/~ps/downloads/tst/tst.html 삼항 탐색 트리 연산의 시간 복잡도: {| class="wikitable" |- ! !! 평균 실행 시간 !! 최악 실행 시간 |- | 탐색 || O(log n + k) || O(n + k) |- | 삽입 || O(log n + k) || O(n + k) |- | 삭제 || O(log n + k) || O(n + k) |}
# 다른 자료 구조와의 비교

## 트라이
다른 접두사 트리보다 느리지만, 삼항 탐색 트리는 공간 효율성으로 인해 더 큰 데이터 세트에 더 적합할 수 있다.
## 해시 맵
해시 테이블도 문자열을 값에 매핑하는 삼항 탐색 트리 대신 사용될 수 있다. 그러나 해시 맵은 삼항 탐색 트리보다 더 많은 메모리를 사용하는 경우가 많다(하지만 트라이만큼은 아니다). 또한, 해시 맵은 전체 문자열을 비교해야 하고 처음 몇 문자만 비교할 수 없기 때문에 동일한 자료 구조에 없는 문자열을 보고하는 데 일반적으로 더 느리다. 삼항 탐색 트리가 해시 맵보다 더 빠르게 실행된다는 일부 증거가 있다. 또한, 해시 맵은 근접 이웃 탐색과 같은 삼항 탐색 트리의 많은 용도를 허용하지 않는다.
## DAFSA (결정적 비순환 유한 상태 오토마타)
사전 단어 저장이 필요한 경우(즉, 각 단어에 대한 보조 정보 저장이 필요하지 않은 경우), 최소 결정적 비순환 유한 상태 오토마타(DAFSA)는 트라이 또는 삼항 탐색 트리보다 적은 공간을 사용한다. 이는 DAFSA가 저장되는 다른 단어의 동일한 접미사(또는 부분)에 해당하는 트리의 동일한 분기를 압축할 수 있기 때문이다.
# 사용
삼항 탐색 트리는 많은 수의 문자열을 임의의 순서로 저장하고 검색해야 하는 많은 문제를 해결하는 데 사용될 수 있다. 가장 일반적이거나 유용한 몇 가지 용도는 다음과 같다. * 트라이를 사용할 수 있지만 메모리 소모가 적은 구조가 선호되는 경우. * 문자열을 다른 데이터에 매핑하기 위한 빠르고 공간 절약적인 자료 구조. * 자동 완성을 구현하기 위해.url=http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/ * 맞춤법 검사기로.access-date=2020-07-19 * 근접 이웃 탐색(맞춤법 검사는 특별한 경우임). * 특히 여러 비키 필드로 색인화하는 것이 바람직한 데이터베이스로. * 해시 테이블 대신.