들어가기 전에

AVL 트리 규칙을 만족하는지 확인하는 균형 확인 메소드에 대해 알아보도록 하겠습니다.

학습 목표

AVL 트리의 균형 확인 메소드를 이해할 수 있습니다.

핵심 단어

• AVL 트리
  
• 균형 확인 메소드

강의 듣기

균형 확인 메소드

AVL 트리에서는 왼쪽과 오른쪽의 높이 차이가 항상 1보다 작거나 같아야 합니다. 따라서, 노드를 추가하였을 때 높이의 차이가 1보다 커지면 회전을 하여 트리의 균형을 맞춰주어야 합니다.

트리의 높이 차이를 확인하고 균형을 맞추는 checkBalance 코드는 다음과 같습니다.

public void checkBalance(Node<E> node){
	// 높이 차이가 1 초과 혹은 -1 미만 (AVL 트리 규칙 위반)
	if ((height(node.left) - height(node.right)>1) || (height(node.left) - height(node.right)<-1)){
		rebalance(node);
	// 부모 노드를 계속 확인해서 루트까지 갑니다.
	if (node.parent == null)
		return;
	checkBalance(node.parent);
}

생각해보기

1) checkBalance 메소드에서 새로 추가한 노드뿐만 아니라 모든 부모 노드를 확인해야 하는 이유는 무엇인가요?