Java-자료구조 5주차 Tree 5 - 5 ~ 7

5주차. AVL Tree & RB Tree
5-5. 균형 확인 메소드

• 트리의 높이 차를 확인하는 메소드: checkBalance 메소드
  입력 인자-추가한 노드로 child, parent, grandparent, root 모두 해당될 수 있다
• 높이 차이가 1 초과 혹은 -1 미만시 AVL 트리 규칙 위반
  <코드>

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); // 루트에 갈 때까지 이동
}

균형은 유지하게 만드는 메소드: Rebalance메소드

5-6. Rebalance 메소드

• 추가 후, 균형이 깨진 부분 확인+회전하는 메소드:Rebalance 메소드
  회전 목적: 균형 유지
  <코드>

public void rebalance(Node<E> node){

	if (height(node.left) - height(node.right)>1) { // 높이 차: left > right
		if(height(node.left.left) > height(node.left.right)) // 왼쪽 서브 트리 > 오른쪽 서브 트리
			node = rightRotate(node); // 우측 회전
		else // 왼쪽 서브 트리 < 오른쪽 서브 트리
			node = leftRightRotate(node); // 좌측-우측 회전
	}
    
	else{ // 높이 차: left < right
		if(height(node.left.left) > height(node.left.right)) // 왼쪽 서브 트리 > 오른쪽 서브 트리
			node = rightLeftRotate(node); // 우측-좌측 회전
		else // 왼쪽 서브 트리 < 오른쪽 서브 트리
			node = leftRotate(node); // 좌측 회전	
	}
    
    // 균형을 맞춘 뒤 루트로 올 때까지 반복
	if (node.parent == null)
		root=node; 
}

균형을 맞추기 위해 회전하면서 루트에 도달할 때까지 반복한다. 그러면서 루트에 도달 시, 확인 후 마무리

5-7. adding data 예제
ex) AVL 트리에 add 메소드를 사용하여 43,18,22,9,21,6,8,20,63,50,62,51순으로 추가

과정)

결과)