이진 검색 트리와 AVL 트리의 차이점을 알기 전에 이진 검색 트리와 AVL 트리를 별도로 알아야 합니다.

이진 검색 트리란 무엇입니까?

그만큼 이진 검색 트리 는 나무 이진 트리 . 우리가 알고 있듯이, 그 트리는 'n'개의 자식을 가질 수 있습니다. 이진 트리는 최대 2개의 자식을 포함할 수 있습니다. 따라서 이진 트리의 제약 조건 뒤에는 이진 검색 트리도 따릅니다. 이진 검색 트리의 각 노드에는 최대한 두 개의 자식이 있어야 합니다. 즉, 이진 검색 트리는 이진 트리의 변형이라고 말할 수 있습니다.

이진 검색 트리는 또한 이진 검색의 속성을 따릅니다. 이진 검색에서는 배열의 모든 요소가 정렬된 순서로 되어 있어야 합니다. 중간 요소의 왼쪽 부분에는 중간 값보다 작은 값이 포함되고, 가운데 요소의 오른쪽 부분에는 중간 값보다 큰 값이 포함되는 이진 검색에서 중간 요소를 계산합니다.

이진 탐색 트리에서는 가운데 요소가 루트 노드가 되고 오른쪽 부분이 오른쪽 하위 트리가 되며 왼쪽 부분이 왼쪽 하위 트리가 됩니다. 따라서 이진 검색 트리는 다음과 같은 조합이라고 말할 수 있습니다. 이진 트리 그리고 이진 검색 .

참고: 이진 검색 트리는 왼쪽 하위 트리의 모든 요소가 루트 노드보다 작고 오른쪽 하위 트리의 모든 요소가 루트 노드보다 큰 이진 트리로 정의할 수 있습니다.

이진 검색 트리의 시간 복잡도

이진 검색 트리가 거의 균형 잡힌 트리인 경우 모든 작업의 ​​시간 복잡도는 다음과 같습니다. 오(로그인) 검색이 왼쪽 또는 오른쪽 하위 트리로 나누어지기 때문입니다.

C의 ASCII 테이블

이진 검색 트리가 왼쪽 또는 오른쪽으로 치우쳐 있으면 모든 작업의 ​​시간 복잡도는 다음과 같습니다. 에) n개 요소까지 순회해야 하기 때문입니다.

AVL 트리란 무엇입니까?

안 AVL 트리 왼쪽과 오른쪽 하위 트리의 높이 차이가 1보다 클 수 없는 자체 균형 이진 검색 트리입니다. 이 차이를 균형 요소라고 합니다. AVL 트리에서 균형 요소 값은 -1, 0 또는 1일 수 있습니다.

이진 검색 트리의 자체 균형 조정은 어떻게 발생합니까?

AVL 트리는 자체 균형 이진 검색 트리라는 것을 알고 있습니다. 이진 검색 트리가 균형을 이루지 못한 경우 일부 재배열을 통해 자체 균형을 이룰 수 있습니다. 이러한 재배열은 몇 가지 회전을 사용하여 수행할 수 있습니다.

예를 통해 셀프 밸런싱을 이해해 봅시다.

삽입하고 싶다고 가정 해 보겠습니다. 10, 20, 30 AVL 트리에서.

AVL 트리에 10, 20, 30을 삽입하는 방법은 다음과 같습니다.

삽입순서가 30, 20, 10인 경우

1 단계: 먼저 아래와 같이 이진 검색 트리를 만듭니다.

스크립트 쉘 실행

2 단계: 위 그림에서 노드 30의 균형 인자가 2이기 때문에 트리가 불균형하다는 것을 알 수 있습니다. AVL 트리로 만들기 위해서는 약간의 회전을 수행해야 합니다. 노드 20에서 오른쪽 회전을 수행하면 아래와 같이 노드 30이 아래로 이동하고 노드 20이 위로 이동합니다.

관찰할 수 있듯이 최종 트리는 이진 검색 트리와 균형 트리의 속성을 따릅니다. 따라서 AVL 트리입니다.

그 경우에는 나무였다. 왼쪽 불균형 트리, 그래서 우리는 노드에서 올바른 회전을 수행합니다.

삽입순서가 10, 20, 30인 경우

1 단계: 먼저 아래와 같이 이진 검색 트리를 만듭니다.

2 단계: 위 그림에서 노드 10의 균형 인자가 -2이기 때문에 트리가 불균형하다는 것을 알 수 있습니다. AVL 트리를 만들려면 몇 가지 회전을 수행해야 합니다. 오른쪽 불균형 트리이므로 왼쪽 회전을 수행하겠습니다. 노드 20에서 왼쪽 회전을 수행하면 아래와 같이 노드 20이 위로 이동하고 노드 10이 아래로 이동합니다.

우리가 관찰할 수 있듯이, 최종 트리는 다음의 속성을 따릅니다. 이진 검색 트리 그리고 균형 잡힌 나무 ; 따라서 AVL 트리입니다.

BFS 대 DFS

삽입순서가 30, 10, 20인 경우

1 단계: 먼저 아래와 같이 이진 검색 트리를 만듭니다.

2 단계: 위 그림에서 루트 노드의 균형 인자가 2이기 때문에 트리가 불균형하다는 것을 알 수 있습니다. AVL 트리를 만들기 위해서는 약간의 회전을 수행해야 합니다. 위 시나리오는 한 노드가 상위 노드의 왼쪽이고 다른 노드가 상위 노드의 오른쪽이므로 왼쪽-오른쪽 불균형입니다. 먼저 왼쪽 회전을 수행하고 노드 10과 20 사이에서 회전이 발생합니다. 왼쪽 회전 후 아래와 같이 20은 위로 이동하고 10은 아래로 이동합니다.

그래도 나무의 균형이 맞지 않아 나무에 올바른 회전을 수행합니다. 트리에서 오른쪽 회전이 수행되면 트리는 아래와 같이 됩니다.

위의 트리에서 볼 수 있듯이 트리는 이진 검색 트리와 균형 트리의 속성을 따릅니다. 따라서 AVL 트리입니다.

삽입 순서가 10, 30, 20인 경우

1 단계: 먼저 아래와 같이 이진 검색 트리를 만듭니다.

2 단계: 위 그림에서 루트 노드의 균형 인자가 2이기 때문에 트리가 불균형하다는 것을 알 수 있습니다. AVL 트리로 만들기 위해서는 약간의 회전을 수행해야 합니다. 위의 시나리오는 한 노드가 상위 노드 오른쪽에 있고 다른 노드가 상위 노드 왼쪽에 있으므로 오른쪽-왼쪽 불균형입니다. 먼저 노드 30과 20 사이에서 일어나는 우회전을 수행하겠습니다. 우회전 후 아래와 같이 20은 위로 이동하고 30은 아래로 이동합니다.

그래도 위의 트리는 불균형하므로 노드에서 왼쪽 회전을 수행해야 합니다. 왼쪽 회전이 수행되면 아래와 같이 노드 20이 위로 이동하고 노드 10이 아래로 이동합니다.

위의 트리에서 볼 수 있듯이 트리는 이진 검색 트리와 균형 트리의 속성을 따릅니다. 따라서 AVL 트리입니다.

이진 검색 트리와 AVL 트리의 차이점