검색 트리

Search tree
나무 탐색과 혼동하지 마십시오.

컴퓨터 과학에서 검색 트리는 집합 내에서 특정 키를 찾기 위해 사용되는 트리 데이터 구조입니다.트리가 검색 트리로 기능하려면 각 노드의 키가 왼쪽 서브트리의 키보다 크고 오른쪽 [1]서브트리의 키보다 작아야 합니다.

검색 트리의 장점은 트리의 균형이 적절히 잡혀 있을 때 효율적인 검색 시간, 즉 양 끝에 있는 잎의 깊이가 비슷하다는 것입니다.다양한 검색 트리 데이터 구조가 존재하며, 그 중 몇 가지는 요소를 효율적으로 삽입 및 삭제할 수 있으며, 그 후 운영은 트리 균형을 유지해야 합니다.

검색 트리는 종종 연관 배열을 구현하는 데 사용됩니다.검색 트리 알고리즘은 키와 값 쌍의 키를 사용하여 위치를 찾은 후 해당 위치에 키와 값의 전체 쌍을 저장합니다.

트리의 종류

Binary search tree
이진 검색 트리

이진 검색 트리

주요 기사: 이진 검색 트리

바이너리 검색 트리는 노드 기반 데이터 구조이며, 각 노드는 키와 왼쪽과 오른쪽의 두 개의 하위 트리를 포함합니다.모든 노드에서 왼쪽 하위 트리의 키는 노드의 키보다 작아야 하며 오른쪽 하위 트리의 키는 노드의 키보다 커야 합니다.이러한 하위 트리는 모두 이진 검색 트리로 적합해야 합니다.

바이너리 검색 트리의 검색에서 최악의 시간 복잡도는 트리의 높이이며, 이는 요소가 n개인 트리의 경우 O(log n)만큼 작을 수 있습니다.

B-트리

주요 기사 : B-tree

B-tree는 각 노드에 가변적인 수의 서브트리를 가질 수 있다는 점에서 바이너리 검색 트리의 일반화입니다.하위 노드에는 미리 정의된 범위가 있지만 반드시 데이터로 채워지는 것은 아니며, 이는 B-트리가 공간을 낭비할 수 있음을 의미합니다.장점은 B-트리를 다른 셀프밸런싱 트리만큼 자주 재조정할 필요가 없다는 것입니다.

노드 길이의 가변 범위로 인해 B-트리는 대량의 데이터 블록을 읽는 시스템에 최적화되어 있으며 데이터베이스에서도 일반적으로 사용됩니다.

B-트리를 검색하는 시간의 복잡도는 O(log n)입니다.

(a,b) 트리

주요 기사: (a, b)-트리

(a, b)-트리는 모든 잎의 깊이가 같은 탐색 트리입니다.각 노드에는 적어도 1명, 최대 2명의 자녀가 있으며, 루트는 적어도 2명, 최대 2명의 자녀가 있습니다.

a와 b는 다음 [2]공식으로 결정할 수 있다.

(a, b) 트리를 검색하는 시간의 복잡도는 O(log n)입니다.

삼원 검색 트리

주요 기사:삼원 검색 트리

3진수 검색 트리는 하위 하위, 하위 하위 및 상위 하위의 3가지 노드를 가질 수 있는 트리 유형입니다.각 노드는 하나의 문자를 저장하고 트리 자체의 순서는 가능한 제3 노드를 제외하고 바이너리 검색 트리와 동일하게 지정됩니다.

3진수 검색 트리를 검색하려면 문자열이 포함된 경로가 있는지 테스트해야 합니다.

균형 잡힌 3진수 검색 트리를 검색하기 위한 시간 복잡도는 O(log n)입니다.

알고리즘 검색

특정 키 검색

트리가 주문되었다고 가정하면 키를 가져와 트리 내에서 찾을 수 있습니다.다음 알고리즘은 바이너리 검색 트리에 대해 일반화되어 있지만 다른 형식의 트리에도 동일한 아이디어를 적용할 수 있습니다.

재귀적

노드가 NULL일 경우 search-recursive(키, 노드)는 키 < 노드일 경우 EMTEME_TREE를 반환합니다.key > node일 경우 key return search-module(key, node.left)이 반환됩니다.key return search-right (key, node.right)그렇지 않으면 return 노드

반복적

currentNode의 경우 currentNode가 NULL이 아닌 반면 searchReterative(키, 노드) currentNode : = 노드입니다.키 = 키가 currentNode를 반환합니다. 그렇지 않으면 currentNode가 반환됩니다.key > key currentNode : = currentNode . left else currentNode : = currentNode . right

최소값 및 최대값 검색 중

정렬된 트리에서 최소값은 맨 왼쪽 노드에 있고 최대값은 [3]맨 오른쪽 노드에 있습니다.

최소값

노드가 NULL인 경우 findMinimum(노드)은 EMTY_TREE min := 노드를 반환하고 min.left는 NULL min := min.left가 아닙니다.열쇠

최대치

노드가 NULL인 경우 findMaximum(노드)은 EMTEMPY_TREE max := 노드를 반환하지만 max.right는 NULL max := max.right return max.key가 아님

「 」를 참조해 주세요.

레퍼런스

  1. ^ Black, Paul and Pieterse, Breda (2005)"검색 트리"를 선택합니다.알고리즘 및 데이터 구조 사전
  2. ^ 투알, 레이. (a, b) 나무들.
  3. ^ Gildea, Dan (2004년)."바이너리 검색 트리"