Wikipedia의 불균형 AVL 트리에 대한 예는 실제로 불균형합니까?

StackOverflow https://stackoverflow.com/questions/230831

문제

alt text

위의 이미지는 "AVL 나무에 Wikipedia의 입장" Wikipedia가 나타내는 어느 것이 균형이 맞지 않습니다. 이 나무는 어떻게 이미 균형을 이루지 않습니까? 기사의 인용문은 다음과 같습니다.

노드의 밸런스 계수는 오른쪽 하위 트리의 높이로 왼쪽 하위 트리의 높이와 밸런스 계수 1, 0 또는 -1을 갖는 노드는 균형으로 간주됩니다. 다른 균형 계수가있는 노드는 불균형으로 간주되며 트리를 재조정해야합니다. 밸런스 계수는 각 노드에 직접 저장되거나 하위 트리의 높이에서 계산됩니다.

왼쪽 및 오른쪽 서브 트리의 높이는 4입니다. 왼쪽 나무의 오른쪽 하위 트리는 높이가 3이며 여전히 4 미만입니다. 누군가 내가 놓친 것을 설명 할 수 있습니까?

도움이 되었습니까?

해결책

균형을 잡으려면 나무의 모든 노드도

  • 자녀가 없다 ( "잎"노드가 되십시오)
  • 두 자녀가 있습니다.

  • 또는 아이 만있는 경우 그 아이는 잎이어야합니다.

    게시 된 차트에서 9, 54 & 76은 마지막 규칙을 위반합니다.

제대로 균형을 잡으면 나무가 다음과 같습니다.

Root: 23
(23) -> 14 & 67
(14) -> 12 & 17
(12) -> 9
(17) -> 19
(67) -> 50 & 72
(50) -> 54
(72) -> 76

업데이트 : (거의 9 년 후, 나는 그래프에 대한 멋진 온라인 차트를 만들었습니다. draw.io)enter image description here

다른 팁

예를 들어 오른쪽 하위 트리는 높이 0이고 왼쪽은 높이 3이기 때문에 노드 76은 불균형입니다.

직관적으로, 그것은 가능한 한 작지 않기 때문입니다. 예를 들어, 12는 9와 14의 부모 여야합니다. 9는 왼쪽 하위 트리가 없으므로 균형이 맞지 않습니다. 트리는 계층 적 데이터 구조이므로 "밸런스"와 같은 규칙은 종종 루트 노드뿐만 아니라 모든 노드에 적용됩니다.

루트 노드가 균형이 맞지 만 트리의 모든 노드가있는 것은 아닙니다.

이것을 보는 또 다른 방법은 h 모든 노드의 다음은 다음과 같습니다.

h = 1 + max( left.height, right.height )

그리고 노드는 언제든지 균형이 맞지 않습니다.

abs( left.height - right.height ) > 1

위의 나무를보고 :

- Node 12 is a leaf node so its height = 1+max(0,0) = 1
- Node 14 has one child (12, on the left), so its height is = 1+max(1,0) = 2
- Node 9 has one child (14, on the right), so its height is = 1+max(0,2) = 3

노드 9가 균형을 이루는 지 여부를 확인하기 위해 어린이의 높이를 봅니다.

- 9's left child is NULL, so 9.left.height = 0
- 9's right child (14) has height 2, so 9.right.height = 2

이제 노드 9가 불균형임을 보여주기 위해 해결하십시오.

9.unbalanced = abs( 9.left.height - 9.right.height ) > 1
9.unbalanced = abs( 0 - 2 ) > 1
9.unbalanced = abs( -2 ) > 1
9.unbalanced = 2 > 1
9.unbalanced = true

다른 모든 노드에 대해 유사한 계산을 수행 할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top