트리

트리
트리
유형	트리
발명된	1960
발명자	에드워드 프레드킨, 액셀 투, 르네 드 라 브리안다이스
빅 O 표기의 시간 복잡도
알고리즘.
알고리즘.
공간
서치
삽입
삭제

그림 1: 키 "A", "to", "tea", "ted", "ten", "i", "in" 및 "inn"의 트리.각 완전한 영어 단어에는 임의의 정수 값이 관련되어 있습니다.

컴퓨터 과학에서, 디지털 트리 또는 접두사 ^[1]트리라고도 불리는 트리(trie)는 집합 내에서 특정 키를 찾기 위해 사용되는 트리 데이터 구조인 k-ary 검색 트리의 한 유형입니다.대부분의 경우 이러한 키는 문자열이며 노드 간 링크는 키 전체가 아니라 개별 문자로 정의됩니다.키에 액세스하기 위해(값 회복, 변경 또는 삭제), 키 내의 각 문자를 나타내는 노드 간 링크에 이어 trie가 깊이 우선으로 통과됩니다.

바이너리 검색 트리와 달리 트라이의 노드는 연관된 키를 저장하지 않습니다.대신 trie에서 노드의 위치에 따라 노드의 관련 키가 정의됩니다.이는 각 키의 값을 데이터 구조 전체에 분산시켜 모든 노드에 반드시 관련된 값이 있는 것은 아니라는 것을 의미합니다.

노드의 모든 자녀는 해당 부모 노드와 관련된 문자열의 공통 프레픽스를 가지며 루트는 빈 문자열과 관련지어집니다.프리픽스로 액세스 가능한 데이터를 저장하는 이 작업은 기수 트리를 사용함으로써 메모리에 최적화된 방법으로 수행할 수 있습니다.

try는 문자열로 입력할 수 있지만 입력할 필요는 없습니다.예를 들어 숫자 또는 도형의 순열과 같은 기본 유형의 순서 목록에 동일한 알고리즘을 적용할 수 있습니다.특히 비트 단위 trie는 정수 또는 메모리 주소와 같은 고정 길이의 바이너리 데이터의 일부를 구성하는 개별 비트로 키화된다.트라이의 키 검색 복잡도는 키 크기에 비례합니다.압축 시행과 같은 전문화된 시행 시행은 단순한 시행에서 시행되는 엄청난 공간 요구사항을 처리하기 위해 사용됩니다.

역사, 어원, 발음

현의 집합을 나타내기 위한 트라이의 개념은 ^[2]^[3]1912년 Axel Thue에 의해 추상적으로 처음 설명되었습니다.René de la Briandais가 ^[4]^[3]^[5]^{: 336}1959년에 컴퓨터 환경에서 처음 기술했습니다.

이 아이디어는 1960년 ^[6]에드워드 프레드킨에 의해 독립적으로 설명되었는데, 에드워드 프레드킨은 trie라는 용어를 만들어 냈고,^[7]^[8] 검색의 중간 음절 뒤에 /"tri// ("나무"로 발음했다.그러나 다른 저자들은 그것을 "tree"^[7]^[8]^[3]와 구두로 구별하기 위해 /tratra (/ ("try"로 발음한다.

개요

trys는 문자열 색인화된 룩업 데이터 구조의 한 형태로, 검색 가능한 단어의 사전 목록을 저장하기 위해 사용됩니다.이것에 의해, 완성 ^[9]^[10]^{: 1}리스트를 효율적으로 생성할 수 있습니다.프리픽스 트리에는 한정된 알파벳 집합에서 문자열 집합을 표현하기 위해 사용되는 순서 트리 데이터 구조이며, 이를 통해 ^[1]공통 프리픽스를 가진 단어를 효율적으로 저장할 수 있습니다.

이진 검색 트리에 비해 예측 텍스트,^[11]^[8]^[12]^{: 358} 대략적인 문자열 일치 및 철자 검사와 같은 문자열 검색 알고리즘에서 시행이 효과적일 수 있습니다.트리에는 나무 모양의 결정론적 유한 오토마톤이라고 ^[13]볼 수 있다.

운용

그림 2: 현악기 세트의 트리 표현: 바다, 판매, 그녀.

문자열 키 삽입, 삭제 및 검색 등 다양한 작업을 지원합니다.시행은 다른 하위 서픽스 하위 노드에 대한 참조 링크 또는 $(\$ 을 포함하는 노드 $(\$ 로 ${\text{nodes}}$ 구성됩니다.루트를 제외하고 각 노드는 부모라고 불리는 다른 하나의 노드만 가리킵니다.각 ${\text{R}}$ 에는 R $\$ 포함됩니다. $R}}$ 개의 ${\text{R}}$ 링크 $($ 서 $R\style\$ text{\styleR $}}$ 은 ${\text{R}}$ 알파벳 집합의 카디널리티입니다.단, 시도에는 많은 ${\text{nil}}$ 의 0 $(\$ 링크가 ${\text{nil}}$ 있습니다.대부분의 경우 Children $\display {Children}$ 배열의 ${\text{Children}}$ 크기는 문자 인코딩의 비트 길이입니다. (서명되지 않은) ^[14]^{: 732}ASCII의 경우 256입니다.

$노드($ Node $)$ 의 Children( $Children)$ ${\text{Children}}$ 의 ${\text{Children}}$ null $(\$ $\text{nil})$ 링크는 ${\text{nil}}$ ${\text{nil}}$ ^[14]^{: 734}^[5]^{: 336}특성을 강조합니다 ${\text{Node}}$ .

문자 및 문자열 키는 trie 데이터 구조 표현에 암묵적으로 기억되며 문자열 종료를 나타내는 문자 센티넬 값을 포함한다.
각 노드에는 세트의 강력한 키 프리픽스에 대한 링크가 1개 포함되어 있습니다.

trie의 노드의 기본 구조 유형은 다음과 같습니다. $(\$ 에는 ${\text{Node}}$ ${\text{Value}}$ 의 ${\text{Value}}$ 값(\ $displaystyle\text{Value$ 이 포함될 수 있습니다.이 값은 문자열의 마지막 문자에 저장된 각 키 또는 터미널 노드에 관련지어집니다.

structure Node Children 노드[알파벳 크기] Is-Terminal 부울값 데이터 타입 엔드 구조

검색 중

trie 내의 값 $(\$ ${\text{Value}}$ 은 ${\text{Value}}$ 검색 문자열 키 내의 문자에 따라 이루어집니다.trie 내의 각 노드에는 지정된 문자열 내의 가능한 각 문자에 대한 링크가 포함되어 있습니다.따라서 trie 내의 문자열을 따라가면 지정된 문자열 키에 ${\text{Value}}$ 된 ${\text{Value}}$ 값(\ $displaystyle\text{Value})$ 이 ${\text{Value}}$ 생성됩니다.검색 실행 중 0 $(\$ 링크는 ${\text{nil}}$ ^[14]^{: 732-733} ${\text{nil}}$ 가 존재하지 않음을 나타냅니다.

다음 의사 코드에서는 루트 트리( $\$ ^[15]^{: 135} 내의 특정 문자열 키 $(\$ key ${\text{key}}$ 에 대한 검색 절차가 구현됩니다.

0 † i < key . length x 、 Trie - Find ( x , key )는 x 의 경우에 사용합니다.Children[key[i] = 0인 경우 x := x이면 false end를 반환합니다.아이[키]는 x 반환을 반복한다.가치

위의 의사 코드에서는 x $\$ \text ${x}$ 와 ${\text{x}}$ key $\$ 는 ${\text{key}}$ 각각 trie의 루트 노드의 포인터와 스트링 키의 포인터에 대응합니다. $표준$ trie에서 검색 $O({\text{dm}})$ 은 O $O({\text{dm}})$ ( $O({\text{dm}})$ ) { $displaystyle$ O ( { \ $text$ { $dm$ } ) $O({\text{dm}})$ 。 ${\text{m}}$ ${$ $displaystyle$ ${\text{key}}$ ${$ text { $m$ ${\text{m}}$ }}는 ${\text{m}}$ ${\text{d}}$ 문자열 ${\text{key}}$ 키 $크기$ 입니다 $.$ { $displaystyle$ { key ${\text{d}}$ ${\text{key}}$ 는 알파벳 크기에 ^[16]^{: 754} $대응$ 합니다.한편 바이너리 검색 트리는 최악의 경우 O $m$ log $O(m\log n)$ n $)$ 를 $O(m\log n)$ $O(m\log n)$ .검색은 BST(밸런스 트리의 경우 log ${\$ $\log n$ \ $displaystyle \log$ n )의 높이(\ $displaystyle$ \ $log$ $\log n$ n)에 의존하기 때문입니다. ${\text{n}}$ 서 n $\$ n $}$ 및 ${\text{m}}$ $displaystyle o$ m ${$ ${\text{m}}$ text n $}$ 는 ${\text{n}}$ ${\text{m}}$ text number입니다.f 키와 ^[12]^{: 358}키의 길이.

노드가 공통의 초기 스트링의 시퀀스를 공유하고 키를 구조체에 ^[12]^{: 358}암묵적으로 저장하기 때문에 짧은 스트링을 다수 포함하는 경우 BST에 비해 공간을 적게 차지하려고 합니다.트리의 터미널 노드에는 $non-nil$ Value $(\displaystyle\text$ {Value ${\text{Value}}$ 가 포함되어 있으며, 관련 값이 trie에서 발견되면 검색 히트, 발견되지 ^[14]^{: 733}않으면 검색 미스입니다.

삽입

$문자열$ 키의 마지막 문자에 ^[14]^{: 733-734}도달할 때까지 ${\text{Children}}$ 세트를 Children $\$ text ${Children}$ 배열에 ${\text{Children}}$ 인덱스로 사용하여 trie에 삽입할 수 있습니다.trie의 각 노드는 trie 구조가 top-down radix ^[15]^{: 135}sort의 paten 실행을 반영하기 때문에 radix sort 루틴의 1개의 호출에 대응한다.

1 Trie-Insert(x, key, value) 2는 0 † i < key.length는 x일 경우 3을 수행합니다.Children[key[i] = 0 다음 4 x.Children[key[i] := Node() 6 x := x이면 5가 끝납니다.Children[key[i] 7은 8 x를 반복합니다.Value : = 값 9 x.Is-Terminal : = True

문자열 키의 마지막 문자에 도달하기 전에 0 $(\displaystyle\text{nil$ }) ${\text{nil}}$ 가 발견되면 ${\text{x.Value}}$ .^[14]^{: 745} ${\text{x.Value}}$ value $\$ x}행과 같이 ${\text{Node}}$ 노드 $(\$ $text{$ $n})$ 가 ${\text{Node}}$ 생성됩니다. $Value}}$ 는 $(\$ style $\text{value$ 에 할당됩니다 ${\text{x.Value}}$ 의 경우). $(\$ Value $}}$ 는 ${\text{x.Value}}$ 삽입 시 영이 ${\text{nil}}$ .\ $style {\text{nil}}$ 는 ${\text{nil}}$ 지정된 문자열 키와 관련된 값이 현재 문자열 키로 대체됩니다.

삭제

trie에서 키와 값의 쌍을 삭제하려면 대응하는 문자열 키를 사용하여 단말 노드를 검색하여 단말 인디케이터와 값을 false로 표시하고 ${\text{nil}}$ 하는 ^[14]^{: 740}null $(\$ 로 표시합니다.

다음으로 루트 트리( $\$ 에서 문자열 키 $(\$ ${$ key ${\text{key}}$ 를 삭제하는 재귀적인 절차를 나타냅니다.

1 Trie-Delete(x, key) 2 키가 0이면 3이고 x.Is-Terminal = True이면 4 x.Is-Terminal : = False 5 x.Value : = nil 6 end 7이 nil 8end를 반환하면 9x.Children [ key [ 0 ] : = Trie - Delete ( x ) 。Children [ key [ 0 ] 、 key [ 1 : ] 10 반환 x

이 절차는 ${\text{key}}$ 키 $(\displaystyle\text{$ key ${\text{key}}$ 를 검사하는 것으로 ${\text{nil}}$ 합니다 $.\$ text ${nil}$ 는 ${\text{nil}}$ $단말$ 노드 또는 문자열 키의 끝을 나타냅니다.단말기의 경우 노드가 trie에서 삭제됩니다(9행은 문자 인덱스를 0 $(\displaystyle\nil})$ 에 할당합니다).단, 노드가 단말기가 아닌 문자열 키의 끝은 키가 존재하지 않음을 나타내므로 이 절차는 trie를 수정하지 않습니다.재귀는 키 $(\$ style $\display\text$ key})의 인덱스를 ${\text{key}}$ 으로써 진행됩니다.

다른 데이터 구조 교체

해시 테이블 대체

해시 테이블을 대체하기 위해 trie를 사용할 수 있습니다.해시 테이블에는 다음과 같은 ^[12]^{: 358}이점이 있습니다.

관련 키가 $m$ 인 $m$ 노드를 검색할 때 복잡도는 O $){displaystyle$ O $(m$ 입니다.단, 불완전한 해시함수는 다수의 충돌 키를 가질 수 있으며, 이러한 테이블의 최악의 경우 검색 속도는 O $)\displaystyle$ O $(N$ 입니다. $N$ 서 N $(displaystyle$ N $)$ 은 $N$ 다음을 나타냅니다.테이블 내의 노드의 총수.
Trys는 해시 테이블과 달리 작업에 해시 함수를 필요로 하지 않습니다.또, 트라이에 다른 키의 충돌도 없습니다.
trie 내의 버킷은 키 충돌을 저장하는 해시 테이블버킷과 유사하며 단일 키가 여러 값에 관련되어 있는 경우에만 필요합니다.
trie 내의 문자열 키는 소정의 알파벳 순서로 정렬할 수 있다.

다만, ^[6]메인 메모리보다 랜덤 액세스 시간이 긴 하드 디스크 드라이브등의 2차 기억 장치에 직접 액세스 하는 경우는, 해시 테이블보다 효율이 떨어진다.시행은 키 값을 여러 개의 표현이 가능한 부동소수점 번호(예: 1은 1.0, +1.0, 1.00 등)와 같이 문자열로 쉽게 표현할 수 없는 경우에도 불리하지만 IEEE 754에서는 2개의 보완 ^[17]형식과 비교하여 2진수로 모호하지 않게 나타낼 수 있습니다.^[12]^{: 359}

도입 전략

그림 3: 좌자 우회전 바이너리 트리로 구현된 트라이: 세로 화살표는하위 포인터, 점선된 수평 화살표가 다음 포인터입니다.이 트리에는 '아기, 배드, 뱅크, 박스, 아빠, 댄스'라는 문자열이 저장되어 있습니다.목록은 사전순으로 트래버설할 수 있도록 정렬됩니다.

시행은 메모리 사용량과 작업 속도 ^[5]^{: 341}간의 다른 균형에 따라 여러 가지 방법으로 나타낼 수 있습니다.trie를 나타내기 위해 포인터의 벡터를 사용하면 엄청난 공간이 소비되지만, 각 노드 벡터에 대해 단일 링크 리스트를 사용하면 실행 시간을 단축할 수 있습니다.이는 벡터의 대부분의 엔트리에 제로 $(\$ ^[3]^{: 495}가 ${\text{nil}}$ 되기 때문입니다.

알파벳 축소 등의 기술은 원래 문자열을 작은 알파벳 위에 긴 문자열로 재해석함으로써 높은 공간의 복잡성을 완화할 수 있다.즉, n바이트의 $문자열$ 은 $2n$ 의 4비트 단위의 문자열로 간주되어 노드당 16개의 포인터를 가진 트라이에 저장될 수 있다.단, 최악의 경우 룩업은 2배의 노드를 방문해야 합니다.단, 공간 요건은 ^[5]^{: 347–352}8배 감소합니다.다른 기술로는 256개의 ASCII 포인터의 벡터를 ASCII 알파벳을 나타내는 256비트의 비트맵으로 저장하여 개별 노드의 크기를 ^[18]대폭 줄입니다.

Bitwise 시행

비트 단위 시행은 단순한 포인터 벡터 구현에서 트라이 노드의 엄청난 공간 요구사항을 해결하기 위해 사용됩니다.문자열 키 집합의 각 문자는 개별 비트를 통해 표현되며, 이 비트는 문자열 키를 통해 트라이를 통과하기 위해 사용됩니다.이러한 타입의 trie의 실장은 벡터화된 CPU 명령을 사용하여 고정길이 키 입력의 첫 번째 세트 비트를 찾습니다(예를 들어 GCC).__builtin_clz() 내장 기능).따라서 설정 비트는 32 엔트리 또는 64 엔트리 기반의 비트 단위 트리에서 첫 번째 항목, 즉 자녀 노드를 색인화하기 위해 사용된다.그런 다음 키의 ^[19]각 후속 비트를 테스트하여 검색을 계속합니다.

또한 이 절차는 캐시 로컬이며 레지스터의 독립성에 의해 고도로 병렬화되므로 순서가 잘못된 실행 CPU에서 성능이 ^[19]향상됩니다.

압축 시행

압축 트리라고도 불리는 Radix 트리는 한 명의 자식만 있는 노드가 상위 노드와 병합되는 공간 최적화 트리입니다. 한 명의 자식만 있는 노드의 분기를 제거하면 공간 및 시간 ^[20]^[21]^{: 452}메트릭 모두에서 더 나은 결과를 얻을 수 있습니다.이는 트라이가 정적인 상태로 유지되고 저장된 키 세트가 표현 ^[22]^{: 3–16}공간 내에 매우 희박한 경우에 가장 적합합니다.

또 하나의 접근방식은 trie를 "패킹"하는 것입니다.여기서 공간 효율이 높은 sparse packed trie의 실장은 자동 하이픈화에 적용되어 각 노드의 하위 노드가 메모리에 ^[8]인터리브될 수 있습니다.

패트리샤 나무

그림 4: 문자열 키의 Patricia 트리 표현: in, integer, interval, string 및 structure.

Patricia Tree는 문자열 키의 이진 부호화를 ^[23]^[15]^{: 140}표현에 사용하는 압축 이진 trie의 특별한 구현입니다.Patricia 트리의 모든 노드에는 "건너뛰기 번호"로 알려진 인덱스가 포함되어 있으며, 이 인덱스는 통과 중에 ^[15]^{: 140-141}비어 있는 하위 트리를 방지하기 위해 노드의 분기 인덱스를 저장합니다.키의 희박한 배포로 인해 발생하는 리프 노드의 수가 증가하므로 트라이를 단순하게 구현하면 엄청난 스토리지가 소모됩니다. 이러한 ^[15]^{: 142}^[24]^{: 3}경우 Patricia 트리가 효율적입니다.

는 패트리샤 나무의 문자열 키({\displaystyle\와 같이{in,integer,interval,string,structure\}}과 표현 그림 4에, 각 지표 값이 노드에 근처의"흡수 계수"-로 진출이 결정되야 되는 부분의 인덱스를 나타내는 표시되어 있다.[24]:3 노드 0의 건너뛰기 번호 1은 키 $세트$ X $(\displaystyle$ X $X$ ^[24]^{: 3-4}에서 가장 왼쪽 비트가 다른 바이너리로 인코딩된 ASCII의 위치 1에 해당합니다.스킵 번호는 패트리샤 트리의 노드 검색, 삽입 및 삭제에 매우 중요하며 비트 마스킹 조작은 ^[15]^{: 143}반복할 때마다 수행됩니다.

적용들

트리 데이터 구조는 예측 텍스트 또는 자동 완성 사전 및 대략적인 일치 ^[11]알고리즘에서 일반적으로 사용됩니다.빠른 검색을 활성화하고 공간을 적게 차지합니다. 특히 집합에 짧은 문자열이 다수 포함되어 있기 때문에 철자 검사, 하이픈 처리 응용 프로그램 및 최장 접두사 ^[8]^[12]^{: 358}일치 알고리즘에 사용됩니다.그러나 사전 단어 저장만 필요한 경우(즉, 각 단어와 관련된 메타데이터를 저장할 필요가 없음) 최소 결정론적 비순환 유한 상태 자동화(DAFSA) 또는 기수 트리는 trie보다 적은 저장 공간을 사용합니다.이는 DAFSA와 기수 트리가 trie에서 동일한 분기를 압축할 수 있기 때문에 저장되는 다른 단어의 동일한 서픽스(또는 부분)에 대응합니다.문자열 사전은 텍스트 ^[25]^{: 73}코퍼스의 어휘 검색과 같은 자연어 처리에도 이용된다.

정렬

문자열 키 세트의 사전 정렬은 주어진 키에 대한 트리를 작성하고 미리 정렬된 방식으로 ^[26]트리를 통과함으로써 구현할 수 있습니다. 이 또한 기수 ^[27]정렬의 한 형태입니다.trys는 버스트소트의 기본 데이터 구조이기도 합니다.^[28]이것은 CPU ^[29]캐시를 효율적으로 사용하기 위해 2007년 현재 가장 빠른 문자열 정렬 알고리즘으로 주목됩니다.

전체 텍스트 검색

접미사 트리라고 하는 특수한 종류의 트리(trie)를 사용하여 텍스트의 모든 접미사를 색인화하여 전체 텍스트 ^[30]검색을 빠르게 수행할 수 있습니다.

웹 검색 엔진

압축 trie라고 불리는 특수한 종류의 trie는 웹 검색 엔진에서 인덱스를 저장하기 위해 사용됩니다. 즉, 모든 검색 가능한 ^[31]단어의 집합입니다.각 터미널 노드는 키워드와 일치하는 페이지에 대한 URL 목록(오카렌스리스트라고 불립니다)과 관련지어집니다.trie는 메인 메모리에 저장되지만 발생은 외부 스토리지(대규모 클러스터)에 저장되거나 메모리 내 인덱스가 외부 ^[32]위치에 저장된 문서를 가리킵니다.

생물정보학

시행은 생물정보학, 특히 BLAST와 같은 시퀀스 정렬 소프트웨어 애플리케이션에서 사용되며, BLAST는 발생 위치를 압축된 트라이 시퀀스 데이터베이스에 ^[25]^{: 75}저장하여 텍스트 길이 k(k-mers라고 함)의 모든 다른 서브스트링을 색인화합니다.

인터넷 라우팅

Forwarding Information Base(FIB; 전송 정보 기반)를 관리하기 위한 데이터베이스 등의 압축된 배리언트는 IP ^[25]^{: 75}라우팅에서의 마스크 기반 동작을 해결하기 위해 프리픽스 기반 룩업을 위해 라우터 및 브리지 내에 IP 주소 프레픽스를 저장하는 데 사용됩니다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b Maabar, Maha (17 November 2014). "Trie Data Structure". CVR, University of Glasgow. Archived from the original on 27 January 2021. Retrieved 17 April 2022.
^ Thue, Axel (1912). "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen". Skrifter Udgivne Af Videnskabs-Selskabet I Christiania. 1912 (1): 1–67. 크누스가 인용했다.
^ ^a ^b ^c ^d Knuth, Donald (1997). "6.3: Digital Searching". The Art of Computer Programming Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. p. 492. ISBN 0-201-89685-0.
^ de la Briandais, René (1959). File searching using variable length keys (PDF). Proc. Western J. Computer Conf. pp. 295–298. doi:10.1145/1457838.1457895. S2CID 10963780. Archived from the original (PDF) on 2020-02-11. 브라스와 크누스가 인용했다.
^ ^a ^b ^c ^d Brass, Peter (8 September 2008). Advanced Data Structures. UK: Cambridge University Press. doi:10.1017/CBO9780511800191. ISBN 978-0521880374.
^ ^a ^b Edward Fredkin (1960). "Trie Memory". Communications of the ACM. 3 (9): 490–499. doi:10.1145/367390.367400. S2CID 15384533.
^ ^a ^b Black, Paul E. (2009-11-16). "trie". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Archived from the original on 2011-04-29.
^ ^a ^b ^c ^d ^e Franklin Mark Liang (1983). Word Hy-phen-a-tion By Com-put-er (PDF) (Doctor of Philosophy thesis). Stanford University. Archived (PDF) from the original on 2005-11-11. Retrieved 2010-03-28.
^ "Trie". School of Arts and Science, Rutgers University. 2022. Archived from the original on 17 April 2022. Retrieved 17 April 2022.
^ Connelly, Richard H.; Morris, F. Lockwood (1993). "A Generalization of the Trie Data Structure". Electrical Engineering and Computer Science. New York: Syracuse University. doi:10.1017/S0960129500000803.
^ ^a ^b Aho, Alfred V.; Corasick, Margaret J. (Jun 1975). "Efficient String Matching: An Aid to Bibliographic Search" (PDF). Communications of the ACM. 18 (6): 333–340. doi:10.1145/360825.360855. S2CID 207735784.
^ ^a ^b ^c ^d ^e ^f Thareja, Reema (13 October 2018). "Hashing and Collision". Data Structures Using C (2 ed.). Oxford University Press. ISBN 9780198099307.
^ Daciuk, Jan (24 June 2003). Comparison of Construction Algorithms for Minimal, Acyclic, Deterministic, Finite-State Automata from Sets of Strings. International Conference on Implementation and Application of Automata. Springer Publishing. pp. 255–261. doi:10.1007/3-540-44977-9_26. ISBN 978-3-540-40391-3.
^ ^a ^b ^c ^d ^e ^f ^g Sedgewick, Robert; Wayne, Kevin (3 April 2011). Algorithms (4 ed.). Addison-Wesley, Princeton University. ISBN 978-0321573513.
^ ^a ^b ^c ^d ^e ^f Gonnet, G. H.; Yates, R. Baeza (January 1991). Handbook of algorithms and data structures: in Pascal and C (2 ed.). Boston, United States: Addison-Wesley. ISBN 978-0-201-41607-7.
^ Patil, Virsha H. (10 May 2012). Data Structures using C++. Oxford University Press. ISBN 9780198066231.
^ S. Orley; J. Mathews. "The IEEE 754 Format". Department of Mathematics and Computer Science, Emory University. Archived from the original on 28 March 2022. Retrieved 17 April 2022.
^ Bellekens, Xavier (2014). "A Highly-Efficient Memory-Compression Scheme for GPU-Accelerated Intrusion Detection Systems". Proceedings of the 7th International Conference on Security of Information and Networks - SIN '14. Glasgow, Scotland, UK: ACM. pp. 302:302–302:309. arXiv:1704.02272. doi:10.1145/2659651.2659723. ISBN 978-1-4503-3033-6. S2CID 12943246.
^ ^a ^b Willar, Dan E. (27 January 1983). "Log-logarithmic worst-case range queries are possible in space O(n)". Information Processing Letters. ScienceDirect. 17 (2): 81–84. doi:10.1016/0020-0190(83)90075-3.
^ Sartaj Sahni (2004). "Data Structures, Algorithms, & Applications in C++: Tries". University of Florida. Archived from the original on 16 July 2016. Retrieved 17 April 2022.
^ Mehta, Dinesh P.; Sahni, Sartaj (7 March 2018). "Tries". Handbook of Data Structures and Applications (2 ed.). Chapman & Hall, University of Florida. ISBN 978-1498701853.
^ Jan Daciuk; Stoyan Mihov; Bruce W. Watson; Richard E. Watson (1 March 2000). "Incremental Construction of Minimal Acyclic Finite-State Automata". Computational Linguistics. MIT Press. 26 (1): 3–16. arXiv:cs/0007009. Bibcode:2000cs........7009D. doi:10.1162/089120100561601.
^ "Patricia tree". National Institute of Standards and Technology. Archived from the original on 14 February 2022. Retrieved 17 April 2022.
^ ^a ^b ^c Crochemore, Maxime; Lecroq, Thierry (2009). "Trie". Encyclopedia of Database Systems. Boston, United States: Springer Publishing. doi:10.1007/978-0-387-39940-9. ISBN 978-0-387-49616-0 – via HAL (open archive).
^ ^a ^b ^c Martinez-Prieto, Miguel A.; Brisaboa, Nieves; Canovas, Rodrigo; Claude, Francisco; Navarro, Gonzalo (March 2016). "Practical compressed string dictionaries". Information Systems. Elsevier. 56: 73–108. doi:10.1016/j.is.2015.08.008. ISSN 0306-4379.
^ Kärkkäinen, Juha. "Lecture 2" (PDF). University of Helsinki. The preorder of the nodes in a trie is the same as the lexicographical order of the strings they represent assuming the children of a node are ordered by the edge labels.
^ Kallis, Rafael (2018). "The Adaptive Radix Tree (Report #14-708-887)" (PDF). University of Zurich: Department of Informatics, Research Publications.
^ Ranjan Sinha and Justin Zobel and David Ring (Feb 2006). "Cache-Efficient String Sorting Using Copying" (PDF). ACM Journal of Experimental Algorithmics. 11: 1–32. doi:10.1145/1187436.1187439. S2CID 3184411.
^ J. Kärkkäinen and T. Rantala (2008). "Engineering Radix Sort for Strings". In A. Amir and A. Turpin and A. Moffat (ed.). String Processing and Information Retrieval, Proc. SPIRE. Lecture Notes in Computer Science. Vol. 5280. Springer. pp. 3–14. doi:10.1007/978-3-540-89097-3_3. ISBN 978-3-540-89096-6.
^ Giancarlo, Raffaele (28 May 1992). "A Generalization of the Suffix Tree to Square Matrices, with Applications". SIAM Journal on Computing. Society for Industrial and Applied Mathematics. 24 (3): 520–562. doi:10.1137/S0097539792231982. ISSN 0097-5397.
^ Yang, Lai; Xu, Lida; Shi, Zhongzhi (23 March 2012). "An enhanced dynamic hash TRIE algorithm for lexicon search". Enterprise Information Systems. 6 (4): 419–432. doi:10.1080/17517575.2012.665483.
^ Transier, Frederik; Sanders, Peter (December 2010). "Engineering basic algorithms of an in-memory text search engine". ACM Transactions on Information Systems. Association for Computing Machinery. 29 (1): 1–37. doi:10.1145/1877766.1877768.

외부 링크

NIST의 사전 알고리즘 및 데이터 구조물의:.트리

[cvr14-1] Maabar, Maha (17 November 2014). "Trie Data Structure". CVR, University of Glasgow. Archived from the original on 27 January 2021. Retrieved 17 April 2022.

[thue-2] Thue, Axel (1912). "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen". Skrifter Udgivne Af Videnskabs-Selskabet I Christiania. 1912 (1): 1–67. 크누스가 인용했다.

[KnuthVol3-3] Knuth, Donald (1997). "6.3: Digital Searching". The Art of Computer Programming Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. p. 492. ISBN 0-201-89685-0.

[4] Briandais, René (1959). File searching using variable length keys (PDF). Proc. Western J. Computer Conf. pp. 295–298. doi:10.1145/1457838.1457895. S2CID 10963780. Archived from the original (PDF) on 2020-02-11. 브라스와 크누스가 인용했다.

[brass-5] Brass, Peter (8 September 2008). Advanced Data Structures. UK: Cambridge University Press. doi:10.1017/CBO9780511800191. ISBN 978-0521880374.

[triememory-6] Edward Fredkin (1960). "Trie Memory". Communications of the ACM. 3 (9): 490–499. doi:10.1145/367390.367400. S2CID 15384533.

[DADS-7] Black, Paul E. (2009-11-16). "trie". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Archived from the original on 2011-04-29.

[Liang1983-8] Franklin Mark Liang (1983). Word Hy-phen-a-tion By Com-put-er (PDF) (Doctor of Philosophy thesis). Stanford University. Archived (PDF) from the original on 2005-11-11. Retrieved 2010-03-28.

[9] "Trie". School of Arts and Science, Rutgers University. 2022. Archived from the original on 17 April 2022. Retrieved 17 April 2022.

[10] Connelly, Richard H.; Morris, F. Lockwood (1993). "A Generalization of the Trie Data Structure". Electrical Engineering and Computer Science. New York: Syracuse University. doi:10.1017/S0960129500000803.

[aho75-11] Aho, Alfred V.; Corasick, Margaret J. (Jun 1975). "Efficient String Matching: An Aid to Bibliographic Search" (PDF). Communications of the ACM. 18 (6): 333–340. doi:10.1145/360825.360855. S2CID 207735784.

[reema18-12] ^ ^a ^b ^c ^d ^e ^f Thareja, Reema (13 October 2018). "Hashing and Collision". Data Structures Using C (2 ed.). Oxford University Press. ISBN 9780198099307.

[13] Daciuk, Jan (24 June 2003). Comparison of Construction Algorithms for Minimal, Acyclic, Deterministic, Finite-State Automata from Sets of Strings. International Conference on Implementation and Application of Automata. Springer Publishing. pp. 255–261. doi:10.1007/3-540-44977-9_26. ISBN 978-3-540-40391-3.

[robert11-14] ^ ^a ^b ^c ^d ^e ^f ^g Sedgewick, Robert; Wayne, Kevin (3 April 2011). Algorithms (4 ed.). Addison-Wesley, Princeton University. ISBN 978-0321573513.

[gonnet91-15] ^ ^a ^b ^c ^d ^e ^f Gonnet, G. H.; Yates, R. Baeza (January 1991). Handbook of algorithms and data structures: in Pascal and C (2 ed.). Boston, United States: Addison-Wesley. ISBN 978-0-201-41607-7.

[patil_12-16] Patil, Virsha H. (10 May 2012). Data Structures using C++. Oxford University Press. ISBN 9780198066231.

[17] S. Orley; J. Mathews. "The IEEE 754 Format". Department of Mathematics and Computer Science, Emory University. Archived from the original on 28 March 2022. Retrieved 17 April 2022.

[18] Bellekens, Xavier (2014). "A Highly-Efficient Memory-Compression Scheme for GPU-Accelerated Intrusion Detection Systems". Proceedings of the 7th International Conference on Security of Information and Networks - SIN '14. Glasgow, Scotland, UK: ACM. pp. 302:302–302:309. arXiv:1704.02272. doi:10.1145/2659651.2659723. ISBN 978-1-4503-3033-6. S2CID 12943246.

[willar83-19] Willar, Dan E. (27 January 1983). "Log-logarithmic worst-case range queries are possible in space O(n)". Information Processing Letters. ScienceDirect. 17 (2): 81–84. doi:10.1016/0020-0190(83)90075-3.

[20] Sartaj Sahni (2004). "Data Structures, Algorithms, & Applications in C++: Tries". University of Florida. Archived from the original on 16 July 2016. Retrieved 17 April 2022.

[21] Mehta, Dinesh P.; Sahni, Sartaj (7 March 2018). "Tries". Handbook of Data Structures and Applications (2 ed.). Chapman & Hall, University of Florida. ISBN 978-1498701853.

[22] Jan Daciuk; Stoyan Mihov; Bruce W. Watson; Richard E. Watson (1 March 2000). "Incremental Construction of Minimal Acyclic Finite-State Automata". Computational Linguistics. MIT Press. 26 (1): 3–16. arXiv:cs/0007009. Bibcode:2000cs........7009D. doi:10.1162/089120100561601.

[23] "Patricia tree". National Institute of Standards and Technology. Archived from the original on 14 February 2022. Retrieved 17 April 2022.

[maxime09-24] Crochemore, Maxime; Lecroq, Thierry (2009). "Trie". Encyclopedia of Database Systems. Boston, United States: Springer Publishing. doi:10.1007/978-0-387-39940-9. ISBN 978-0-387-49616-0 – via HAL (open archive).

[prieto16-25] Martinez-Prieto, Miguel A.; Brisaboa, Nieves; Canovas, Rodrigo; Claude, Francisco; Navarro, Gonzalo (March 2016). "Practical compressed string dictionaries". Information Systems. Elsevier. 56: 73–108. doi:10.1016/j.is.2015.08.008. ISSN 0306-4379.

[26] Kärkkäinen, Juha. "Lecture 2" (PDF). University of Helsinki. The preorder of the nodes in a trie is the same as the lexicographical order of the strings they represent assuming the children of a node are ordered by the edge labels.

[27] Kallis, Rafael (2018). "The Adaptive Radix Tree (Report #14-708-887)" (PDF). University of Zurich: Department of Informatics, Research Publications.

[cachestringsort-28] Ranjan Sinha and Justin Zobel and David Ring (Feb 2006). "Cache-Efficient String Sorting Using Copying" (PDF). ACM Journal of Experimental Algorithmics. 11: 1–32. doi:10.1145/1187436.1187439. S2CID 3184411.

[stringradix-29] J. Kärkkäinen and T. Rantala (2008). "Engineering Radix Sort for Strings". In A. Amir and A. Turpin and A. Moffat (ed.). String Processing and Information Retrieval, Proc. SPIRE. Lecture Notes in Computer Science. Vol. 5280. Springer. pp. 3–14. doi:10.1007/978-3-540-89097-3_3. ISBN 978-3-540-89096-6.

[30] Giancarlo, Raffaele (28 May 1992). "A Generalization of the Suffix Tree to Square Matrices, with Applications". SIAM Journal on Computing. Society for Industrial and Applied Mathematics. 24 (3): 520–562. doi:10.1137/S0097539792231982. ISSN 0097-5397.

[Xu12-31] Yang, Lai; Xu, Lida; Shi, Zhongzhi (23 March 2012). "An enhanced dynamic hash TRIE algorithm for lexicon search". Enterprise Information Systems. 6 (4): 419–432. doi:10.1080/17517575.2012.665483.

[32] Transier, Frederik; Sanders, Peter (December 2010). "Engineering basic algorithms of an in-memory text search engine". ACM Transactions on Information Systems. Association for Computing Machinery. 29 (1): 1–37. doi:10.1145/1877766.1877768.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

v t 트리 데이터 구조
트리 검색 (다이나믹 세트/어소시에이션 어레이)	2–3 2–3–4 AA (a, b) AVL B B+ B* B^x. (최적) 바이너리 검색 춤추다 HTree 간격 주문통계 (좌향) 레드-블랙 희생양 스플라이 T 나무 UB 무게 밸런스
수북이	바이너리 이항 브로달 피보나치 좌파 페어링 스큐 판 엠데 보아스 약한
시도하다	Ctrie C-trie(압축 ADT) 해시 기수 서픽스 삼진수 검색 X-Fast 고속
공간 데이터 파티션 트리	공 BK BSP 데카르트어 힐베르트 R k-d(표준 k-d) M 미터법 MVP 옥트리 PH 우선 순위 R 쿼드 R R+ R* 부분 부사장 X
기타 트리	덮다 지수 펜윅 손가락. 프랙탈 트리 인덱스 퓨전 해시 캘린더 i디스턴스 K-ary 좌측자녀 우측자매 링크/컷 로그 구조화 결합 머클 p q. 범위 SPQR 정상

v t 잘 알려진 데이터 구조
종류들	수집 컨테이너.
추상적인	연관 배열 멀티맵 데이터 구조 검색 목록. 스택 큐 더블 엔드 큐 priority 큐 이중 엔드 priority 큐 세트 멀티셋 디조인트 세트
어레이	비트 배열 순환 버퍼 다이내믹 어레이 해시 테이블 해시 어레이 트리 희박 행렬
링크되어 있다	어소시에이션리스트 링크 리스트 스킵 리스트 언롤링된 링크 리스트 XOR 링크 리스트
나무들	B-트리 이진 검색 트리 AA나무 AVL 트리 붉은색-검은색 셀프밸런싱 트리 스플레이 트리 히프 이진 힙 이항 힙 피보나치 힙 R 트리 R* 트리 R+ 트리 힐베르트 R-트리 트리 해시 트리
그래프	이항 결정도 방향 비순환 그래프 지시 비순환 단어 그래프
데이터 구조 목록

v t 줄들
문자열 메트릭	대략적인 문자열 매칭 비트맵 알고리즘 다메라우-레벤슈테인 거리 거리 편집 게스탈트 패턴 매칭 해밍 거리 자로-윙클러 거리 리 거리 레벤슈테인 오토마톤 레벤슈테인 거리 바그너-피셔 알고리즘
문자열 검색 알고리즘	사도-장칼로 알고리즘 Boyer-Moore 문자열 검색 알고리즘 보이어-무어-호스풀 알고리즘 크누스-모리스-프랫 알고리즘 라빈-카르프 알고리즘
다중 문자열 검색	아호코라식 Commentz-Walter 알고리즘
정규 표현	정규 표현 엔진 비교 정규 문법 톰슨 구조 비결정론적 유한 오토마톤
시퀀스 얼라인먼트	히르슈베르크 알고리즘 니들맨분쉬 알고리즘 스미스-워터맨 알고리즘
data 구조	DAFSA 서픽스 배열 서픽스 오토마톤 접미사 트리 일반 접미사 트리 출렁 삼원 검색 트리 트리
다른.	해석 패턴 매칭 압축 패턴 매칭 최장 공통 서브시퀀스 최장 공통 서브스트링 순차적 패턴 마이닝 정렬

Search

트리

네임스페이스

더

목차

역사, 어원, 발음

개요

운용

검색 중

삽입

삭제

다른 데이터 구조 교체

해시 테이블 대체

도입 전략

Bitwise 시행

압축 시행

패트리샤 나무

적용들

정렬

전체 텍스트 검색

웹 검색 엔진

생물정보학

인터넷 라우팅

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

트리

역사, 어원, 발음

개요

운용

검색 중

삽입

삭제

다른 데이터 구조 교체

해시 테이블 대체

도입 전략

Bitwise 시행

압축 시행

패트리샤 나무

적용들

정렬

전체 텍스트 검색

웹 검색 엔진

생물정보학

인터넷 라우팅

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.