자바스크립트의 AVL 회전

<시간/>

균형을 맞추기 위해 AVL 트리는 다음 네 가지 회전을 수행할 수 있습니다. -

처음 두 회전은 단일 회전이고 다음 두 회전은 이중 회전입니다. 불균형한 나무를 가지려면 최소한 높이 2의 나무가 필요합니다. 이 간단한 나무로 하나씩 이해해 봅시다.

왼쪽 회전

트리가 불균형 상태가 되면 오른쪽 하위 트리의 오른쪽 하위 트리에 노드가 삽입될 때 왼쪽으로 한 번 회전 -

자바스크립트의 AVL 회전

이 예에서 노드 A A의 오른쪽 하위 트리의 오른쪽 하위 트리에 노드가 삽입되면서 불균형이 되었습니다. A를 만들어 왼쪽 회전을 수행합니다. B의 왼쪽 하위 트리 . 이 회전을 LL 회전이라고도 합니다. 구현 방법을 살펴보겠습니다 -

function rotationLL(node) {
let tmp = node.left;
node.left = tmp.right;
tmp.right = node;
return tmp;
}

AVL 트리는 왼쪽 서브트리의 왼쪽 서브트리에 노드가 삽입되면 불균형해질 수 있습니다. 그러면 나무가 오른쪽으로 회전해야 합니다.

자바스크립트의 AVL 회전

그림과 같이 불균형 노드는 오른쪽 회전을 수행하여 왼쪽 자식의 오른쪽 자식이 됩니다. 이것을 RR 회전이라고도 합니다. 코드에서 어떻게 보이는지 봅시다 -

function rotationRR(node) {
let tmp = node.right;
node.right = tmp.left;
tmp.left = node;
return tmp;
}

이중 회전은 이미 설명한 회전 버전의 약간 복잡한 버전입니다. 그것들을 더 잘 이해하려면 회전하는 동안 수행되는 각 작업을 기록해야 합니다. 먼저 좌-우 회전을 수행하는 방법을 확인합시다. 왼쪽-오른쪽 회전은 왼쪽 회전과 오른쪽 회전의 조합입니다.

상태	액션
	왼쪽 하위 트리의 오른쪽 하위 트리에 노드가 삽입되었습니다. 이렇게 하면 C 불균형 노드. 이러한 시나리오로 인해 AVL 트리가 왼쪽에서 오른쪽으로 회전합니다.
	우선 C의 왼쪽 하위 트리에서 왼쪽 회전을 수행합니다. 이렇게 하면 A , B의 왼쪽 하위 트리 .
	노드 C 여전히 불균형하지만 지금은 왼쪽 하위 트리의 왼쪽 하위 트리 때문입니다.
	이제 나무를 오른쪽으로 회전시켜 B 이 하위 트리의 새 루트 노드입니다. ㄷ 이제 자신의 왼쪽 하위 트리의 오른쪽 하위 트리가 됩니다.
	나무가 이제 균형을 잡았습니다.

이것은 우리가 먼저 왼쪽 회전을 수행한 다음 오른쪽 회전을 수행하기 때문에 LR 회전이라고도 합니다. 이것은 다음과 같이 앞의 두 가지 방법을 사용하여 구현할 수 있습니다. -

function rotationLR(node) {
node.left = rotationRR(node.left);
return rotationLL(node);
}

이중 회전의 두 번째 유형은 오른쪽-왼쪽 회전입니다. 오른쪽 회전과 왼쪽 회전의 조합입니다.

상태	액션
	오른쪽 하위 트리의 왼쪽 하위 트리에 노드가 삽입되었습니다. 이렇게 하면 A, 균형 계수가 2인 불균형 노드.
	먼저, C를 따라 오른쪽 회전을 수행합니다. 노드, C 만들기 자신의 왼쪽 하위 트리 B의 오른쪽 하위 트리 . 이제 B A의 오른쪽 하위 트리가 됩니다. .
	노드 A 오른쪽 하위 트리의 오른쪽 하위 트리로 인해 여전히 불균형하고 왼쪽 회전이 필요합니다.
	왼쪽 회전은 B 하위 트리의 새 루트 노드. A 오른쪽 하위 트리 B의 왼쪽 하위 트리가 됩니다. .
	나무가 이제 균형을 잡았습니다.

이것은 우리가 먼저 오른쪽 회전을 수행한 다음 왼쪽 회전을 수행하기 때문에 RL 회전이라고도 합니다. 이것은 다음과 같이 앞의 두 가지 방법을 사용하여 구현할 수 있습니다. -

function rotationRL(node) {
node.right = rotationLL(node.right);
return rotationRR(node);
}