들어가기 전에

AVL 트리 규칙을 만족하도록 회전을 해주는 Rebalance 메소드에 대해 알아보도록 하겠습니다.

학습 목표

AVL 트리의 Rebalance 메소드를 이해할 수 있습니다.

핵심 단어

• AVL 트리
• 회전
• Rebalance 메소드

강의 듣기

Rebalance 메소드

Rebalance 메소드는 어느 쪽에서 균형이 깨졌는지 확인하고 회전을 하여 균형을 유지합니다.

public void rebalance(Node<E> node){
	// 왼쪽 자식 > 오른쪽 자식
	if (height(node.left) - height(node.right)>1) {
		if(height(node.left.left) > height(node.left.right)) // 왼쪽 서브 트리 > 오른쪽 서브 트리
			node = rightRotate(node); // 우측 회전
		else // 왼쪽 서브 트리 < 오른쪽 서브 트리
			node = leftRightRotate(node); // 좌측-우측 회전
	}
	// 왼쪽 자식 < 오른쪽 자식
	else{ 
		if(height(node.left.left) > height(node.left.right)) // 왼쪽 서브 트리 > 오른쪽 서브 트리
			node = rightLeftRotate(node); // 우측-좌측 회전
		else // 왼쪽 서브 트리 < 오른쪽 서브 트리
			node = leftRotate(node); // 좌측 회전	
	}
	// 루트로 올 때까지 반복합니다.
	if (node.parent == null)
		root=node;
}

생각해보기

1) checkBalance 메소드와 Rebalance 메소드의 차이점은 무엇인가요? 각각 어떤 역할을 하나요?