이 문서는 Google Cloud Translation API를 사용해 자동 번역되었습니다.
어떤 문서는 원문을 읽는게 나을 수도 있습니다.
디지털 트리 또는 때때로 기수 트리 또는 접두사 트리(접두사로 검색할 수 있음)라고도 하는 트리는 키가 일반적으로 문자열인 동적 집합 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 데이터 구조입니다. 이진 검색 트리와 달리 트리의 어떤 노드도 해당 노드와 관련된 키를 저장하지 않습니다. 대신 트리에서 해당 위치는 연결된 키를 정의합니다. 노드의 모든 자손은 해당 노드와 연결된 문자열의 공통 접두사를 가지며 루트는 빈 문자열과 연결됩니다. 값이 반드시 모든 노드와 연관되는 것은 아닙니다. 오히려 값은 리프 및 관심 키에 해당하는 일부 내부 노드와 연결되는 경향이 있습니다.
단순화를 위해 이 기사에서는 키가 단일 문자라고 가정합니다. 보다 현실적인 가정은 키가 문자열이라는 것입니다. 그러나 이 보다 일반적인 경우도 문자열의 문자를 일련의 키 입력으로 간주하여 단일 문자의 경우로 줄일 수 있습니다.
트리는 매우 특별한 속성을 가진 트리로 볼 수 있습니다. 즉, 루트에서 리프까지의 모든 경로의 길이가 동일하고 경로의 각 노드에서 이 길이는 노드의 깊이와 같습니다. 나무. 즉, 트리는 모든 잎이 같은 수준에 있는 트리입니다.
트리의 각 노드에는 문자로 레이블이 지정됩니다. 루트에서 리프까지의 경로는 단어에 해당하며 경로의 각 노드의 레이블은 단어를 형성하는 문자입니다. 예를 들어, 위의 그림에서 루트에서 문자 'c'로 레이블이 지정된 노드까지의 경로는 단어 "car"에 해당합니다.
trie 알고리즘의 기본 아이디어는 검색할 문자열을 trie 데이터 구조에 저장한 다음 trie에서 원하는 문자열을 검색하는 것입니다.
검색 알고리즘은 트리의 루트에서 시작하여 각 노드에서 노드의 레이블이 검색할 문자열의 다음 문자와 일치하는지 확인합니다. 일치하는 항목이 있으면 트리의 다음 노드(즉, 현재 노드의 자식)로 이동합니다. 일치하는 항목이 없으면 트리의 다음 노드(즉, 현재 노드의 형제 노드)로 이동합니다. 일치 항목을 찾지 못한 채 검색이 리프 노드에 도달하면 문자열이 트리에 없습니다.
예를 들어 위의 그림에 표시된 트라이를 고려하고 "car"라는 문자열을 검색한다고 가정합니다. 검색 알고리즘은 문자 'a'로 레이블이 지정된 루트 노드에서 시작합니다. 이것은 문자열의 첫 번째 문자와 일치하므로 문자 'c'로 레이블이 지정된 자식 노드로 이동합니다. 이것은 문자열의 두 번째 문자와도 일치하므로 문자 'a'로 레이블이 지정된 자식 노드로 이동합니다. 이것은 문자열의 세 번째 문자와 일치하지 않으므로 문자 'r'로 레이블이 지정된 다음 노드로 이동합니다. 이 역시 일치하지 않기 때문에 문자 'b'로 레이블이 지정된 다음 노드로 이동합니다. 더 이상 노드가 없기 때문에 검색이 종료되고 문자열이 트리에 존재하지 않는다는 결론을 내립니다.
삽입 알고리즘은 삽입할 문자열의 다음 문자와 일치하지 않는 노드에 도달하면 다음 문자의 레이블로 새 노드를 생성하여 다음 문자의 자식으로 삽입한다는 점을 제외하면 검색 알고리즘과 유사합니다. 현재 노드.
예를 들어, 위의 그림에 표시된 trie를 고려하고 문자열 "cat"을 삽입한다고 가정합니다. 삽입 알고리즘은 문자 'a'로 레이블이 지정된 루트 노드에서 시작합니다. 이것은 문자열의 첫 번째 문자와 일치하므로 문자 'c'로 레이블이 지정된 자식 노드로 이동합니다. 이것은 문자열의 두 번째 문자와도 일치하므로 문자 'a'로 레이블이 지정된 자식 노드로 이동합니다. 이것은 문자열의 세 번째 문자와 일치하지 않기 때문에 't' 레이블이 있는 새 노드를 만들고 현재 노드의 자식으로 삽입합니다.
삭제 알고리즘은 삽입 알고리즘과 유사하지만 삭제할 문자열의 다음 문자와 일치하지 않는 노드에 도달하면 해당 노드와 모든 자손을 삭제한다는 점이 다릅니다.
예를 들어 위의 그림에 표시된 트라이를 고려하고 "cat"이라는 문자열을 삭제한다고 가정합니다. 삭제 알고리즘은 문자 'a'로 레이블이 지정된 루트 노드에서 시작됩니다. 이것은 문자열의 첫 번째 문자와 일치하므로 문자 'c'로 레이블이 지정된 자식 노드로 이동합니다. 이것은 문자열의 두 번째 문자와도 일치하므로 문자 'a'로 레이블이 지정된 자식 노드로 이동합니다. 이것은 문자열의 세 번째 문자와 일치하지 않기 때문에 노드와 모든 자손을 삭제합니다.
trie 데이터 구조는 연결 목록 또는 배열을 사용하여 구현할 수 있습니다.
연결된 목록은 노드 집합으로 구성된 데이터 구조이며 각 노드에는 목록의 다음 노드에 대한 참조가 포함됩니다.
목록의 각 노드에는 두 개의 필드가 있습니다.
목록의 첫 번째 노드를 헤드 노드라고 하고 목록의 마지막 노드를 테일 노드라고 합니다.
trie의 연결 목록 구현은 매우 간단합니다. 문자열을 검색하려면 헤드 노드에서 시작하고 문자열의 각 문자에 대해 테일 노드에 도달할 때까지 다음 노드에 대한 참조를 따릅니다. 문자열이 trie에 없으면 문자열 끝에 도달하기 전에 검색이 꼬리 노드에 도달합니다.
문자열을 삽입하려면 헤드 노드에서 시작하고 문자열의 각 문자에 대해 꼬리 노드에 도달할 때까지 다음 노드에 대한 참조를 따릅니다. 문자열이 trie에 없으면 삽입은 문자열 끝에 도달하기 전에 꼬리 노드에 도달하고 그 지점에서 다음 문자의 레이블이 있는 새 노드를 삽입하고 참조를 업데이트합니다. 꼬리 노드가 새 노드를 가리키도록 합니다.
문자열을 삭제하려면 헤드 노드에서 시작하고 문자열의 각 문자에 대해 꼬리 노드에 도달할 때까지 다음 노드에 대한 참조를 따릅니다. 문자열이 트리에 없으면 삭제는 문자열의 끝에 도달하기 전에 테일 노드에 도달합니다. 문자열이 트리에 있는 경우 삭제는 문자열의 끝에 도달하고 해당 지점에서 노드와 모든 하위 항목을 삭제합니다.
배열은 각각 인덱스로 식별되는 일련의 요소로 구성된 데이터 구조입니다.
트리의 배열 구현에서 트리의 각 노드는 크기 26의 배열로 표시되며 여기서 배열의 각 요소는 트리의 다음 노드에 대한 참조입니다. 배열은 알파벳 문자로 인덱싱되므로 문자 'a'의 인덱스는 0, 문자 'b'의 인덱스는 1 등입니다.
문자열을 검색하려면 루트 노드에서 시작하고 문자열의 각 문자에 대해 다음 노드에 대한 참조를 따릅니다. 문자열이 trie에 없으면 검색은 문자열의 끝에 도달하기 전에 null 노드에 도달합니다.
문자열을 삽입하려면 루트 노드에서 시작하고 문자열의 각 문자에 대해 다음 노드에 대한 참조를 따릅니다. 문자열이 트리에 없으면 삽입은 문자열의 끝에 도달하기 전에 null 노드에 도달하고 그 시점에서 새 노드를 삽입하고 노드의 참조를 업데이트합니다.
문자열을 삭제하려면 루트 노드에서 시작하고 문자열의 각 문자에 대해 다음 노드에 대한 참조를 따릅니다. 문자열이 트리에 없으면 삭제는 문자열의 끝에 도달하기 전에 null 노드에 도달합니다. 문자열이 트리에 있는 경우 삭제는 문자열의 끝에 도달하고 해당 지점에서 노드와 모든 하위 항목을 삭제합니다.
trie 데이터 구조는 맞춤법 검사기, 단어 게임 및 데이터 압축과 같은 많은 응용 프로그램에서 사용됩니다.
맞춤법 검사기 응용 프로그램은 트라이를 사용하여 단어 사전을 저장하고 검색 알고리즘을 사용하여 주어진 단어가 사전에 있는지 여부를 확인합니다.
단어 게임 응용 프로그램은 트라이를 사용하여 게임에 단어를 저장하고 검색 알고리즘을 사용하여 주어진 문자 집합에서 형성될 수 있는 모든 단어를 찾습니다.
데이터 압축 애플리케이션은 트라이를 사용하여 단어 사전을 저장하고 검색 알고리즘을 사용하여 주어진 문자열의 접두사인 사전에서 가장 긴 단어를 찾습니다. 가장 긴 단어의 길이는 문자열을 인코딩하는 데 사용됩니다.
연결된 목록을 사용하여 trie 데이터 구조를 구현합니다.
배열을 사용하여 trie 데이터 구조를 구현합니다.
trie 데이터 구조를 사용하여 단어 사전을 저장하고 검색 알고리즘을 사용하여 주어진 단어가 사전에 있는지 확인하는 맞춤법 검사기 애플리케이션을 구현합니다.
trie 데이터 구조를 사용하여 단어 게임에 단어를 저장하고 검색 알고리즘을 구현하여 주어진 문자 집합에서 형성될 수 있는 모든 단어를 찾습니다.
trie 데이터 구조를 사용하여 단어 사전을 저장하고 검색 알고리즘을 구현하여 주어진 문자열의 접두사인 사전에서 가장 긴 단어를 찾습니다.