4. AVL 트리의 Rebalance 함수

앞에서 균형 인수는 다음과 같이 정의한다고 했다.

'균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리 높이'

그리고 트리에서 트리의 높이를 구하는 함수 또한 만들었다.

 

1. 균형 인수를 구하는 함수

 

 

2. 트리의 균형 여부를 판단하고, 트리를 균형 트리로 만드는 함수

그리고, 트리가 비 균형 상태일 때, 균형 상태로 만들어주는 함수를 Rebalance 라 하고 이를 만들어 보자.

우선 트리가 균형 상태 인지 아닌지를 먼저 확인을 한다.

비 균형 상태이면, 균형 상태로 만들면 된다.

앞에서 말했듯이, 균형이 깨지는 경우는 4가지의 경우가 있다고 했다.

각 경우를 파악하고, 각 경우 맞게 회전시키면 된다.

그리고 앞에서, 균형을 이룬 이진 탐색 트리에서 균형 상태가 깨지는 이유는

노드의 삽입과 삭제 연산 때문에 이루어진다.

삽입 연산은 삽입되는 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있다.

따라서, 새로운 노드의 삽입 후에 불균형 상태로 변한 가장 가까운 조상 노드, 즉,  균형 인수가

+2 혹은 -2가 된 가장 가까운 조상 노드의 서브 트리들에 대하여 다시 균형을 잡아야 한다.

그외의 다른 노드들은 일체 변경할 필요가 없다.

 

그러면, 위의 Rebalance 함수는 노드의 삽입과 삭제 함수에서 호출해서 

비 균형 상태가 되면, 균형 상태로 다시 만들어 주도록 하자.

 

3. 노드 삽입 함수에서 Rebalance함수를 호출

 

4. 삭제 함수에서 Rebalance함수를 호출

삭제 함수는 내용이 너무 많아서, Rebalance가 호출되는 부분만을 캡쳐.

BSTRemove함수의 맨 마지막 라인에서, 노드 삭제 후 호출한다.

 

5. 메인 함수

 

6. 프로그램 실행 결과

 

위의 AVL 트리는 아래의 모양과 같다.

 

                                                     7

                                                3         8

                                             2     5          9

                                          1     4     6

 

 

아래는 헤더 파일 및 소스 파일

AVLTree.c

0.00MB

AVLTree.h

0.00MB

BinarySearchTree.c

0.00MB

BinarySearchTree.h

0.00MB

BinaryTree.c

0.00MB

BinaryTree.h

0.00MB

common.h

0.00MB

main.c

0.00MB