이진 검색 트리와 AVL 트리의 차이점을 알기 전에 이진 검색 트리와 AVL 트리를 별도로 알아야 합니다.
이진 검색 트리란 무엇입니까?
그만큼 이진 검색 트리 는 나무 이진 트리 . 우리가 알고 있듯이, 그 트리는 'n'개의 자식을 가질 수 있습니다. 이진 트리는 최대 2개의 자식을 포함할 수 있습니다. 따라서 이진 트리의 제약 조건 뒤에는 이진 검색 트리도 따릅니다. 이진 검색 트리의 각 노드에는 최대한 두 개의 자식이 있어야 합니다. 즉, 이진 검색 트리는 이진 트리의 변형이라고 말할 수 있습니다.
이진 검색 트리는 또한 이진 검색의 속성을 따릅니다. 이진 검색에서는 배열의 모든 요소가 정렬된 순서로 되어 있어야 합니다. 중간 요소의 왼쪽 부분에는 중간 값보다 작은 값이 포함되고, 가운데 요소의 오른쪽 부분에는 중간 값보다 큰 값이 포함되는 이진 검색에서 중간 요소를 계산합니다.
이진 탐색 트리에서는 가운데 요소가 루트 노드가 되고 오른쪽 부분이 오른쪽 하위 트리가 되며 왼쪽 부분이 왼쪽 하위 트리가 됩니다. 따라서 이진 검색 트리는 다음과 같은 조합이라고 말할 수 있습니다. 이진 트리 그리고 이진 검색 .
참고: 이진 검색 트리는 왼쪽 하위 트리의 모든 요소가 루트 노드보다 작고 오른쪽 하위 트리의 모든 요소가 루트 노드보다 큰 이진 트리로 정의할 수 있습니다.
이진 검색 트리의 시간 복잡도
이진 검색 트리가 거의 균형 잡힌 트리인 경우 모든 작업의 시간 복잡도는 다음과 같습니다. 오(로그인) 검색이 왼쪽 또는 오른쪽 하위 트리로 나누어지기 때문입니다.
C의 ASCII 테이블
이진 검색 트리가 왼쪽 또는 오른쪽으로 치우쳐 있으면 모든 작업의 시간 복잡도는 다음과 같습니다. 에) n개 요소까지 순회해야 하기 때문입니다.
AVL 트리란 무엇입니까?
안 AVL 트리 왼쪽과 오른쪽 하위 트리의 높이 차이가 1보다 클 수 없는 자체 균형 이진 검색 트리입니다. 이 차이를 균형 요소라고 합니다. AVL 트리에서 균형 요소 값은 -1, 0 또는 1일 수 있습니다.
이진 검색 트리의 자체 균형 조정은 어떻게 발생합니까?
AVL 트리는 자체 균형 이진 검색 트리라는 것을 알고 있습니다. 이진 검색 트리가 균형을 이루지 못한 경우 일부 재배열을 통해 자체 균형을 이룰 수 있습니다. 이러한 재배열은 몇 가지 회전을 사용하여 수행할 수 있습니다.
예를 통해 셀프 밸런싱을 이해해 봅시다.
삽입하고 싶다고 가정 해 보겠습니다. 10, 20, 30 AVL 트리에서.
AVL 트리에 10, 20, 30을 삽입하는 방법은 다음과 같습니다.
1 단계: 먼저 아래와 같이 이진 검색 트리를 만듭니다.
스크립트 쉘 실행
2 단계: 위 그림에서 노드 30의 균형 인자가 2이기 때문에 트리가 불균형하다는 것을 알 수 있습니다. AVL 트리로 만들기 위해서는 약간의 회전을 수행해야 합니다. 노드 20에서 오른쪽 회전을 수행하면 아래와 같이 노드 30이 아래로 이동하고 노드 20이 위로 이동합니다.
관찰할 수 있듯이 최종 트리는 이진 검색 트리와 균형 트리의 속성을 따릅니다. 따라서 AVL 트리입니다.
그 경우에는 나무였다. 왼쪽 불균형 트리, 그래서 우리는 노드에서 올바른 회전을 수행합니다.
1 단계: 먼저 아래와 같이 이진 검색 트리를 만듭니다.
2 단계: 위 그림에서 노드 10의 균형 인자가 -2이기 때문에 트리가 불균형하다는 것을 알 수 있습니다. AVL 트리를 만들려면 몇 가지 회전을 수행해야 합니다. 오른쪽 불균형 트리이므로 왼쪽 회전을 수행하겠습니다. 노드 20에서 왼쪽 회전을 수행하면 아래와 같이 노드 20이 위로 이동하고 노드 10이 아래로 이동합니다.
우리가 관찰할 수 있듯이, 최종 트리는 다음의 속성을 따릅니다. 이진 검색 트리 그리고 균형 잡힌 나무 ; 따라서 AVL 트리입니다.
BFS 대 DFS
1 단계: 먼저 아래와 같이 이진 검색 트리를 만듭니다.
2 단계: 위 그림에서 루트 노드의 균형 인자가 2이기 때문에 트리가 불균형하다는 것을 알 수 있습니다. AVL 트리를 만들기 위해서는 약간의 회전을 수행해야 합니다. 위 시나리오는 한 노드가 상위 노드의 왼쪽이고 다른 노드가 상위 노드의 오른쪽이므로 왼쪽-오른쪽 불균형입니다. 먼저 왼쪽 회전을 수행하고 노드 10과 20 사이에서 회전이 발생합니다. 왼쪽 회전 후 아래와 같이 20은 위로 이동하고 10은 아래로 이동합니다.
그래도 나무의 균형이 맞지 않아 나무에 올바른 회전을 수행합니다. 트리에서 오른쪽 회전이 수행되면 트리는 아래와 같이 됩니다.
위의 트리에서 볼 수 있듯이 트리는 이진 검색 트리와 균형 트리의 속성을 따릅니다. 따라서 AVL 트리입니다.
1 단계: 먼저 아래와 같이 이진 검색 트리를 만듭니다.
2 단계: 위 그림에서 루트 노드의 균형 인자가 2이기 때문에 트리가 불균형하다는 것을 알 수 있습니다. AVL 트리로 만들기 위해서는 약간의 회전을 수행해야 합니다. 위의 시나리오는 한 노드가 상위 노드 오른쪽에 있고 다른 노드가 상위 노드 왼쪽에 있으므로 오른쪽-왼쪽 불균형입니다. 먼저 노드 30과 20 사이에서 일어나는 우회전을 수행하겠습니다. 우회전 후 아래와 같이 20은 위로 이동하고 30은 아래로 이동합니다.
그래도 위의 트리는 불균형하므로 노드에서 왼쪽 회전을 수행해야 합니다. 왼쪽 회전이 수행되면 아래와 같이 노드 20이 위로 이동하고 노드 10이 아래로 이동합니다.
위의 트리에서 볼 수 있듯이 트리는 이진 검색 트리와 균형 트리의 속성을 따릅니다. 따라서 AVL 트리입니다.
이진 검색 트리와 AVL 트리의 차이점
| 이진 검색 트리 | AVL 트리 |
|---|---|
| 모든 이진 검색 트리는 두 트리 모두 최대 두 개의 자식을 포함하므로 이진 트리입니다. | AVL 트리에는 최대 2개의 자식이 있으므로 모든 AVL 트리는 이진 트리이기도 합니다. |
| BST에는 균형 요소와 같은 용어가 존재하지 않습니다. | AVL 트리에서 각 노드에는 균형 요소가 포함되며 균형 요소의 값은 -1, 0 또는 1이어야 합니다. |
| BST는 균형 트리이거나 불균형 트리일 수 있으므로 모든 이진 검색 트리는 AVL 트리가 아닙니다. | AVL 트리는 BST의 속성을 따르기 때문에 모든 AVL 트리는 이진 검색 트리입니다. |
| 이진 검색 트리의 각 노드는 왼쪽 하위 트리, 노드 값 및 오른쪽 하위 트리의 세 가지 필드로 구성됩니다. | AVL 트리의 각 노드는 왼쪽 하위 트리, 노드 값, 오른쪽 하위 트리 및 균형 요소의 4개 필드로 구성됩니다. |
| 이진 검색 트리의 경우 트리에 노드를 삽입하려면 노드 값을 루트 값과 비교합니다. 노드의 값이 루트 노드 값보다 크면 노드는 오른쪽 하위 트리에 삽입되고 그렇지 않으면 노드는 왼쪽 하위 트리에 삽입됩니다. 노드가 삽입되면 삽입이 완료되기 위해 높이 균형 요소를 확인할 필요가 없습니다. | AVL 트리의 경우 먼저 노드를 삽입하기에 적합한 위치를 찾습니다. 노드가 삽입되면 각 노드의 균형 요소를 계산합니다. 각 노드의 균형 요소가 만족되면 삽입이 완료됩니다. 균형 요소가 1보다 크면 트리 균형을 맞추기 위해 몇 가지 회전을 수행해야 합니다. |
| 이진 검색 트리에서 트리의 높이 또는 깊이는 O(n)입니다. 여기서 n은 이진 검색 트리의 노드 수입니다. | AVL 트리에서 트리의 높이 또는 깊이는 O(logn)입니다. |
| 노드를 삽입하려면 이진 검색 속성을 따라야 하므로 구현이 간단합니다. | AVL 트리에서는 먼저 AVL 트리를 구성한 다음 높이 균형을 확인해야 하기 때문에 구현하기가 복잡합니다. 높이가 불균형한 경우 트리의 균형을 맞추기 위해 약간의 회전을 수행해야 합니다. |
| BST는 균형 요소의 개념을 따르지 않기 때문에 균형 트리가 아닙니다. | AVL 트리는 균형 요소의 개념을 따르기 때문에 높이 균형 트리입니다. |
| BST에서는 트리에 사용 가능한 노드 수가 많으면 높이 균형이 맞지 않아 검색이 비효율적입니다. | AVL 트리에서는 높이가 균형을 이루므로 트리에 노드 수가 많아도 검색이 효율적입니다. |