삼원 검색 트리
Ternary search tree | 이 문서는 컴퓨팅 분야의 전문가로부터 주의를 받아야 합니다.구체적인 문제는 다음과 같습니다. "몇 가지 설명이 누락되었지만 이 경우 매우 중요한 작업입니다. 모든 조작의 의사 코드가 누락되어 있습니다(앞으로 설명한 조작이 누락되어 있는 것도 포함). 의사 코드는, 조작의 이해를 큰폭으로 향상시킵니다. 실행 시간 복잡도에 대한 엄격한 수학적 분석이 누락되었습니다. 할 수 . (2016년 9월) |
| Ternary 검색 트리(TST) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 유형 | 트리 | ||||||||||||||||
| 빅 O 표기의 시간 복잡도 | |||||||||||||||||
| |||||||||||||||||
컴퓨터 과학에서 3진수 검색 트리는 노드가 2진수 검색 트리와 유사한 방식으로 배열되는 트리(예: 접두사 트리)의 일종입니다. 그러나 2진수 트리의 제한이 아닌 최대 3명의 자식들로 구성됩니다.다른 프리픽스트리와 마찬가지로 3진수 검색 트리는 증분 문자열 검색 기능을 가진 관련 맵구조로 사용할 수 있습니다.단, 3진수 검색 트리는 표준 프리픽스트리에 비해 공간 효율이 높지만 속도가 저하됩니다.3진수 검색 트리의 일반적인 응용 프로그램에는 맞춤법 검사 및 자동 완성이 있습니다.
묘사
3진수 검색 트리의 각 노드는 각각 미들(자녀), 로우(자녀), 하이(자녀)[1]라고도 불릴 수 있는, 종래에는 같은 아이, 로키드, 하이키드라고 불렸던 3명의 아이에 대한 포인터를 기억한다.노드는 부모 노드에 대한 포인터뿐만 아니라 노드가 [2]단어의 끝을 표시하는지 여부를 나타내는 인디케이터를 가질 수도 있다.lokid 포인터는 문자 값이 현재 노드보다 작은 노드를 가리켜야 합니다.hi kid 포인터는 현재 [1]노드보다 큰 문자를 가진 노드를 가리켜야 합니다.동등한 아이는 단어의 다음 문자를 가리킵니다.다음 그림은 문자열 "cute", "cup", "at", "as", "he", "us" 및 "i"를 포함하는 3진 검색 트리를 보여 줍니다.
c / \ a u h \ t e u / / s p e s
다른 trie 데이터 구조와 마찬가지로 3진수 검색 트리 내의 각 노드는 저장된 문자열의 프레픽스를 나타냅니다.노드의 중간 서브트리에 있는 모든 문자열은 해당 프리픽스로 시작합니다.
운용
삽입
3진 검색에 값을 삽입하는 것은 룩업이 정의된 만큼 재귀적으로 또는 반복적으로 정의할 수 있습니다.이 재귀적 메서드는 키의 앞부분에서 문자를 제거함으로써 점차 짧아지는 키가 주어진 트리의 노드에서 계속 호출됩니다.이 메서드가 생성되지 않은 노드에 도달하면 노드가 생성되어 키에 포함된 첫 번째 문자의 문자 값이 할당됩니다.새 노드가 생성되었는지 여부에 관계없이 메서드는 문자열 내의 첫 번째 문자가 노드 내의 문자 값보다 크거나 작은지 여부를 확인하고 검색 조작과 같이 적절한 노드에서 재귀 호출을 수행합니다.단, 키의 첫 번째 문자가 노드의 값과 동일한 경우 삽입 절차가 동일한 키드로 호출되고 키의 첫 번째 문자가 [1]제거됩니다.이진 검색 트리 및 기타 데이터 구조와 마찬가지로 3진 검색 트리는 [3][self-published source?]키의 순서에 따라 저하될 수 있습니다.키를 알파벳 순으로 삽입하는 것은 최악의 퇴화 [1]트리를 얻는 한 가지 방법입니다.키를 랜덤 순서로 삽입하면 균형 잡힌 [1]트리가 생성되는 경우가 많습니다.
기능. 삽입(스트링 열쇠) 이 노드 p := 뿌리 //루트가 null인 경우 같도록 초기화됨 노드 지난 := 뿌리 인트 idx := 0 하는 동안에 p 이 것은 아니다. 무효 하다 //적절한 서브트리로 선택 한다면 열쇠[idx] < > p.스플릿 그리고나서 지난 := p p := p.왼쪽 또 다른 한다면 열쇠[idx] > p.스플릿 그리고나서 지난 := p p := p.맞다 또 다른: // 키가 이미 트리에 있습니다. 한다면 idx == 길이(열쇠) 그리고나서 돌아가다 //키에서 문자 삭제 idx := idx+1 지난 := p p := p.중앙의 p := 노드() //마지막 비패킷노드(루트가 늘인 경우 루트)의 자녀로 p를 추가합니다. 한다면 뿌리 == 무효 그리고나서 뿌리 := p 또 다른 한다면 지난.스플릿 < > 열쇠[idx] 그리고나서 지난.맞다 := p 또 다른 한다면 지난.스플릿 > 열쇠[idx] 그리고나서 지난.왼쪽 := p 또 다른 지난.중앙의 := p p.스플릿 := 열쇠[idx] idx := idx+1 // 키의 나머지 부분을 삽입합니다. 하는 동안에 idx < > 길이(열쇠) 하다 p.중앙의 := 노드() p.중앙의.스플릿 := 열쇠[idx] idx += 1 서치
특정 노드 또는 노드와 관련된 데이터를 검색하려면 문자열 키가 필요합니다.검색 절차는 트리의 루트 노드를 확인하고 다음 중 어떤 상태가 발생했는지 확인하는 것으로 시작됩니다.문자열의 첫 번째 문자가 루트 노드의 문자보다 작을 경우, 현재 루트의 lokid인 루트를 가진 트리로 재귀 룩업을 호출할 수 있습니다.마찬가지로 첫 번째 문자가 트리 내의 현재 노드보다 클 경우 루트가 현재 [1]노드의 하이키드인 트리로 재귀 호출할 수 있습니다.마지막으로 문자열의 첫 번째 문자가 현재 노드의 문자와 동일한 경우 키에 문자가 더 이상 없으면 노드가 반환됩니다.키에 문자가 더 많을 경우 키의 첫 번째 문자를 삭제하고 동일한 키노드와 변경된 [1]키를 지정하면 재귀 호출이 이루어집니다.또한 현재 노드에 대한 포인터와 [1]키의 현재 문자에 대한 포인터를 사용하여 비재귀적인 방법으로 쓸 수도 있습니다.
유사 코드
기능. 서치(스트링 질문하다) 이 한다면 is_empty(질문하다) 그리고나서 돌아가다 거짓의 노드 p := 뿌리 인트 idx := 0 하는 동안에 p 이 것은 아니다. 무효 하다 한다면 질문하다[idx] < > p.스플릿 그리고나서 p := p.왼쪽 또 다른 한다면 질문하다[idx] > p.스플릿 그리고나서 p := p.맞다; 또 다른 한다면 idx = 길이(질문하다) 그리고나서 돌아가다 진실의 idx := idx + 1 p := p.중앙의 돌아가다 거짓의 삭제
삭제 조작은 검색 트리에서 키 문자열을 검색하고 다음 의사 코드에서 firstMid라고 하는 노드를 찾아 firstMid의 중간 아이에서 키 문자열의 검색 경로 끝에 이르는 경로에는 왼쪽 아이 또는 오른쪽 아이가 없습니다.이것은 키 문자열에 대응하는 3진 트리의 고유한 접미사를 나타냅니다.이러한 경로가 없는 경우 키 문자열이 다른 문자열의 접두사로 완전히 포함되거나 검색 트리에 없음을 의미합니다.많은 구현에서는 문자열 끝 문자를 사용하여 후자의 경우만 발생하도록 합니다.그런 다음 검색 경로의 마지막까지 경로가 삭제됩니다.firstMid가 루트인 경우 키 문자열은 트리의 마지막 문자열이어야 합니다.따라서 삭제 후 루트는 null로 설정됩니다.
기능. 삭제하다(스트링 열쇠) 이 한다면 is_empty(열쇠) 그리고나서 돌아가다 노드 p := 뿌리 인트 idx := 0 노드 첫 번째 미드 := 무효 하는 동안에 p 이 것은 아니다. 무효 하다 한다면 열쇠[idx] < > p.스플릿 그리고나서 첫 번째 미드 := 무효 p := p.왼쪽 또 다른 한다면 열쇠[idx] > p.스플릿 그리고나서 첫 번째 미드 := 무효 p := p.맞다 또 다른 첫 번째 미드 := p 하는 동안에 p 이 것은 아니다. 무효 그리고. 열쇠[idx] == p.스플릿 하다 idx := idx + 1 p := p.중앙의 한다면 첫 번째 미드 == 무효 그리고나서 돌아가다 // 고유한 문자열 접미사가 없습니다. // 이 시점에서 firstMid는 문자열의 고유한 서픽스가 발생하기 전에 노드를 가리킵니다. 노드 q := 첫 번째 미드.중앙의 노드 p := q 첫 번째 미드.중앙의 := 무효 // 트리에서 접미사 연결 끊기 하는 동안에 q 이 것은 아니다. 무효 하다 //서픽스 경로를 걷고 노드를 삭제합니다. p := q q := q.중앙의 삭제하다(p) // 노드 p에 연결된 빈 메모리 한다면 첫 번째 미드 == 뿌리 그리고나서 삭제하다(뿌리) //트리 전체 삭제 뿌리 := 무효 트래버설
부분 일치 검색
근린 검색
실행 시간
3진수 검색 트리의 실행 시간은 입력에 따라 크게 다릅니다.3진수 검색 트리는 여러 개의 유사한 문자열을 지정했을 때, 특히 이러한 문자열이 공통 접두사를 공유하는 경우에 가장 잘 작동합니다.또는 삼진수 검색 트리는 비교적 짧은 문자열(예: [1]사전의 단어)을 많이 저장할 때 효과적입니다.3진수 검색 트리의 실행 시간은 이진수 검색 트리와 비슷하지만 일반적으로 로그 시간으로 실행되지만 퇴화(최악)의 경우 선형 시간으로 실행될 수 있습니다.또한 실행 시간을 고려할 때 문자열의 크기도 고려해야 합니다.예를 들어 길이 k의 문자열 검색 경로에는 트리의 중간 자식 아래로 k개의 통과가 있을 뿐만 아니라 트리의 왼쪽 및 오른쪽 자식 아래로 로그 통과 횟수가 있습니다.따라서, 소수의 매우 큰 문자열에 대한 3진수 검색 트리에서는 문자열의 길이가 [4]실행 시간을 지배할 수 있습니다.
3진수 검색 트리 [1]작업의 시간 복잡성:
| 평균 케이스 실행 시간 | 최악의 실행 시간 | |
|---|---|---|
| 찾다 | O(로그 n + k) | O(n+k) |
| 삽입 | O(로그 n + k) | O(n+k) |
| 삭제 | O(로그 n + k) | O(n+k) |
다른 데이터 구조와의 비교
시도하다
3차 검색 트리는 다른 프리픽스트리보다 느리지만 공간 효율이 [1]높기 때문에 대규모 데이터 세트에 적합합니다.
해시 맵
3진수 검색 트리 대신 해시 테이블을 사용하여 문자열을 값에 매핑할 수도 있습니다.단, 해시 맵은 삼진수 검색 트리보다 더 많은 메모리를 사용하는 경우가 많습니다(단, 시도 횟수만큼 많이 사용하는 것은 아닙니다).또한 해시 맵은 처음 몇 글자뿐만 아니라 문자열 전체를 비교할 필요가 있기 때문에 일반적으로 동일한 데이터 구조 내에 없는 문자열을 보고하는 속도가 느립니다.해시 [1]맵보다 3진수 검색 트리가 더 빨리 실행된다는 증거가 있습니다.또한 해시 맵에서는 근접 네이버 검색과 같은 삼원 검색 트리의 많은 사용을 허용하지 않습니다.
DAFSA(결정론적 비순환 유한 상태 오토마톤)
사전 단어 저장만 필요한 경우(즉, 각 단어에 보조적인 정보의 저장은 필요하지 않음), 최소 결정론적 비순환 유한 상태 자동화(DAFSA)는 트라이 또는 3진 검색 트리보다 적은 공간을 사용할 것이다.이는 DAFSA가 trie에서 동일한 분기를 압축할 수 있기 때문에 저장되는 다른 단어의 동일한 서픽스(또는 부분)에 대응합니다.
사용하다
3진수 검색 트리는 다수의 문자열을 임의의 순서로 저장하고 검색해야 하는 많은 문제를 해결하기 위해 사용할 수 있습니다.이들 중 가장 일반적이거나 유용한 것은 다음과 같습니다.
- Trie를 사용할 수 있지만 메모리 사용량이 적은 구조가 선호됩니다.[1]
- 문자열을 다른 [3]데이터에 매핑하기 위한 빠르고 공간 절약적인 데이터 구조입니다.
- 자동 [2][self-published source?]완료를 구현합니다.
- 맞춤법 [5]검사로요.
- 근린 검색(스펠링 체크는 특수한 [1]경우).
- 데이터베이스로서 특히 키가 아닌 여러 필드로 인덱싱하는 것이 좋습니다.[5]
- 해시 [5]테이블 대신.
「 」를 참조해 주세요.
레퍼런스
- ^ a b c d e f g h i j k l m n "Ternary Search Trees". Dr. Dobb's.
- ^ a b Ostrovsky, Igor. "Efficient auto-complete with a ternary search tree".
- ^ a b Wrobel, Lukasz. "Ternary Search Tree".
- ^ Bentley, Jon; Sedgewick, Bob. "Ternary Search Tree".
- ^ a b c Flint, Wally (February 16, 2001). "Plant your data in a ternary search tree". JavaWorld. Retrieved 2020-07-19.
외부 링크
- Ternary Search Tree 페이지 (Jon Bentley와 Robert Sedgewick)는 3진 검색 트리 및 "문자열 정렬 및 검색" 알고리즘에 대한 논문을 제공합니다.
- Ternary Search Tries – Robert Sedgewick의 비디오
- Robert Sedgewick 및 Kevin Wayne에 의한 TST의 Java에서의 TST.java.html 실장
