비선형 데이터구조, AVL Tree #2 AVL 트리 checkBalance & rebalance 메서드

이전글

https://yonghwankim-dev.tistory.com/199

비선형 데이터구조, AVL Tree #1 AVL 트리 소개 및 add 메서드

 

개요

이전글에서는 AVL 트리의 add 메서드를 구현하였습니다. 이번글에서는 트리가 균형을 맞추고 있는지 검사하는 checkBalance 메서드와 트리를 균형있게 맞추는 기능인 rebalance 메서드를 구현하겠습니다.

 

1. checkBalance 메서드

checkBalance 메서드의 역할은 매개변수로 받은 노드를 기준으로 서브트리의 균형을 검사합니다. AVL 트리에서는 왼쪽과 오른쪽의 높이의 차이가 항상 1보다 작거나 같아야 합니다. 따라서, 노드를 추가하였을 때 높이의 차이가 1보다 커지면 회전을 하여 트리의 균형을 맞추어야 합니다.

 

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

	private void checkBalance(Node<T> 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);
	}

	private int height(Node<T> node)
	{
		if(node==null)
		{
			return 0;
		}
		else
		{
			return Math.max(height(node.left), height(node.right))+1;
		}	
	}

 

2. rebalance 메서드

rebalance 메서드의 역할은 어느 쪽에서 균형이 깨졌는지 확인하고 회전을 하여 균형을 유지합니다.

	private void rebalance(Node<T> 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.right.left) > height(node.right.right))	// 왼쪽 서브 트리 > 오른쪽 서브 트리
			{
				node = rightLeftRotate(node);	// 우측-좌측 회전
			}
			else	// 왼쪽 서브 트리 < 오른쪽 서브 트리
			{
				node = leftRotate(node);	// 좌측 회전
			}
		}
		
		// 루트로 올때까지 반복
		if(node.parent==null)
		{
			root = node;
		}
	}

 

3. add 메서드 테스트

AVL 트리에 정수형 타입 데이터를 추가하여 균형을 유지하고 있는지 테스트합니다.

class AVLTreeTest {

	@Test
	void addTest() {
		AVLTree<Integer> avlTree = new AVLTree<Integer>();
		int[] inputs = {43,18,22,9,21,6,8,20,63,50,62,51};
		
		for(int i=0; i<inputs.length;i++)
		{
			System.out.print(inputs[i] + " add after : ");
			avlTree.add(inputs[i]);
			avlTree.inorderTraversal();
		}	
	}

}

output
43 add after : 43 
18 add after : 18 43 
22 add after : 18 22 43 
9 add after : 9 18 22 43 
21 add after : 9 18 21 22 43 
6 add after : 6 9 18 21 22 43 
8 add after : 6 8 9 18 21 22 43 
20 add after : 6 8 9 18 20 21 22 43 
63 add after : 6 8 9 18 20 21 22 43 63 
50 add after : 6 8 9 18 20 21 22 43 50 63 
62 add after : 6 8 9 18 20 21 22 43 50 62 63 
51 add after : 6 8 9 18 20 21 22 43 50 51 62 63

 

References

source code : https://github.com/yonghwankim-dev/DataStruct/tree/main/Tree/avltree
[부스트코스] 자바로 구현하고 배우는 자료구조