먼저, 우리는 이진 트리 그리고 이진 검색 트리 그런 다음 이진 트리와 이진 검색 트리의 차이점을 살펴보겠습니다.
이진 트리란 무엇입니까?
ㅏ 이진 트리 는
이진 트리는 다음과 같이 표현될 수 있습니다.
위 그림에서 각 노드에는 최대 2개의 자식이 포함되어 있음을 확인할 수 있습니다. 노드에 왼쪽 또는 오른쪽 자식이 포함되어 있지 않으면 해당 자식에 대한 포인터 값은 NULL이 됩니다.
이진 트리에 사용되는 기본 용어는 다음과 같습니다.
이진 트리에는 다음과 같은 트리가 있습니다. 완벽한 이진 트리 . 이것은 모든 내부 노드는 두 개의 노드를 포함해야 하며 모든 리프 노드는 동일한 깊이에 있어야 합니다. 완전 이진 트리의 경우 이진 트리에 존재하는 총 노드 수는 다음 방정식을 사용하여 계산할 수 있습니다.
n = 2m+1-1
여기서 n은 노드 수이고, m은 노드의 깊이입니다.
이진 검색 트리란 무엇입니까?
ㅏ 이진 검색 트리 요소를 배열하기 위해 어떤 순서를 따르는 트리인 반면, 이진 트리는 어떤 순서도 따르지 않습니다. 이진 탐색 트리에서는 왼쪽 노드의 값이 부모 노드보다 작아야 하고, 오른쪽 노드의 값이 부모 노드보다 커야 합니다.
예제를 통해 이진 검색 트리의 개념을 이해해 봅시다.
위 그림에서 루트 노드의 값은 15로 왼쪽 하위 트리에 있는 모든 노드의 값보다 크다는 것을 알 수 있습니다. 루트 노드의 값은 오른쪽 하위 트리에 있는 모든 노드의 값보다 작습니다. 이제 루트 노드의 왼쪽 자식으로 이동합니다. 10은 8보다 크고 12보다 작습니다. 이는 또한 이진 검색 트리의 속성을 만족합니다. 이제 루트 노드의 오른쪽 자식으로 이동합니다. 값 20은 17보다 크고 25보다 작습니다. 이는 또한 이진 검색 트리의 특성을 만족합니다. 그러므로 위의 트리는 이진 탐색 트리라고 할 수 있다.
이제 위 이진 트리에서 12의 값을 16으로 변경하면 여전히 이진 검색 트리인지 여부를 찾아야 합니다.
루트 노드의 값은 15로 10보다 크고 16보다 작으므로 이진 탐색 트리의 속성을 만족하지 않습니다. 따라서 이진 검색 트리가 아닙니다.
이진 검색 트리에서의 작업
이진 검색 트리에서 삽입, 삭제 및 검색 작업을 수행할 수 있습니다. 이진 검색에서 검색이 수행되는 방법을 이해해 보겠습니다. 검색 작업을 수행해야 하는 이진 트리는 아래와 같습니다.
위의 이진 트리에서 10을 검색해야 한다고 가정합니다. 이진 검색을 수행하기 위해 정렬된 배열의 모든 정수를 고려합니다. 먼저 검색 공간에 완전한 목록을 생성하면 모든 숫자가 검색 공간에 존재하게 됩니다. 검색 공간은 시작과 끝이라는 두 개의 포인터로 표시됩니다. 위 이진 트리의 배열은 다음과 같이 표현될 수 있습니다.
먼저 중간 요소를 계산하고, 검색할 요소와 중간 요소를 비교하겠습니다. 중간 요소는 n/2를 사용하여 계산됩니다. n의 값은 7입니다. 따라서 중간 요소는 15입니다. 중간 요소는 검색된 요소, 즉 10과 동일하지 않습니다.
참고: 검색 중인 요소가 중간 요소보다 작으면 왼쪽 절반에서 검색이 수행됩니다. 그렇지 않으면 오른쪽 절반에서 검색이 수행됩니다. 동등의 경우 요소가 발견됩니다.
검색할 요소가 중간 요소보다 작으므로 왼쪽 배열에서 검색이 수행됩니다. 이제 아래와 같이 검색이 절반으로 줄어듭니다.
왼쪽 배열의 mid 요소는 10이며, 이는 검색된 요소와 같습니다.
755 chmod
시간 복잡도
이진 검색에는 n개의 요소가 있습니다. 중간 요소가 검색된 요소와 동일하지 않으면 검색 공간은 n/2로 줄어들고 요소를 찾을 때까지 계속해서 검색 공간을 n/2만큼 줄입니다. 전체 축소에서 n에서 n/2, n/4 등으로 이동하면 로그가 필요합니다.2n 단계.
이진 트리와 이진 검색 트리의 차이점
| 비교의 기초 | 이진 트리 | 이진 검색 트리 |
|---|---|---|
| 정의 | 이진 트리는 노드가 최대 2개의 자식을 가질 수 있는 비선형 데이터 구조입니다. 즉, 노드는 0, 1 또는 최대 2개의 자식을 가질 수 있습니다. 이진 검색 트리는 트리의 노드를 구성하기 위해 어떤 순서를 따르는 정렬된 이진 트리입니다. | |
| 구조 | 이진 트리의 구조는 첫 번째 노드 또는 최상위 노드가 루트 노드로 알려져 있다는 것입니다. 이진 트리의 각 노드에는 왼쪽 포인터와 오른쪽 포인터가 포함됩니다. 왼쪽 포인터에는 왼쪽 하위 트리의 주소가 포함되고 오른쪽 포인터에는 오른쪽 하위 트리의 주소가 포함됩니다. | 이진 탐색 트리(Binary Search Tree)는 왼쪽 하위 트리에 있는 모든 노드의 값이 루트 노드보다 작거나 같고, 오른쪽 하위 트리에 있는 모든 노드의 값이 루트 노드보다 크거나 같은 이진 트리 유형 중 하나입니다. 루트 노드의 값. |
| 운영 | 이진 트리에서 구현할 수 있는 작업은 삽입, 삭제, 순회입니다. | 이진 검색 트리는 빠른 삽입, 삭제 및 검색 기능을 제공하는 정렬된 이진 트리입니다. 조회는 모든 키가 정렬된 순서로 정렬되므로 주로 이진 검색을 구현합니다. |
| 종류 | 이진 트리의 네 가지 유형은 완전 이진 트리, 완전 이진 트리, 완전 이진 트리 및 확장 이진 트리입니다. | AVL 트리, Splay 트리, Tango 트리 등과 같은 다양한 유형의 이진 검색 트리가 있습니다. |