[TIL] 자료구조 - 균형 확인 메소드

※ 균형 확인 메소드

- AVL 트리에서 좌측과 우측의 높이 차가 항상 1보다 작거나 같아야 한다. 따라서, 노드를 추가했을 때 높이 차이가 1보다 커지면 회전을 해 트리의 균형을 맞춰주어야 한다.

 

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

 

public void checkBalance(Node<E> node){
	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);
}