Chapter 12. 탐색(Search) 2

12-1. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해

이번 Chapter에서는 Chapter 11에서 배운 이진 탐색 트리의 단점을 개선한 또 다른 이진 탐색 트리에 대해 배우려한다.

이진 탐색 트리의 단점과 AVL 트리

이진 탐색 트리의 탐색 연산은 $O(log_2n)$의 시간 복잡도를 가진다.
트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하므로, 이진 탐색 트리의 빅-오는 별도의 계산을 거치지 않고서 쉽게 판단이 가능하다.
그런데 이러한 이진 탐색 트리는 균형이 맞지 않을수록 $O(n)$에 가까운 시간 복잡도를 보인다.

위 그림은 1부터 5까지의 정수가 순서대로 저장되었을 때 이진 탐색 트리를 보여준다.
이 트리는 이진 탐색 트리의 조건을 만족하는데 그럼에도 불구하고 노드의 수에 가까운 높이를 형성한다.
반면 1부터 5까지의 정수를 순서대로 저장하되 3을 제일 먼저 저장하면 결과는 다음과 같아진다.

저장 순서만 조금 바꿨더니 루트 노드를 기준으로 어느 정도 균형이 잡혔고 트리의 높이도 반으로 줄었다.
이렇듯 앞서 구현한 이진 탐색 트리는 저장 순서에 따라 탐색의 성능에 큰 차이를 보인다.
이것이 바로 이진 탐색 트리의 단점이다.

이러한 이진 탐색 트리의 단점을 해결한 트리를 가리켜 '균형 잡힌 이진 트리'라 하고,
그 종류는 대략 다음과 같다.

• AVL 트리
• 2-3 트리
• 2-3-4 트리
• Red-Black 트리
• B 트리

이 중에서 하나를 선택하여 우리가 구현한 '이진 탐색 트리'가 자동으로 균형 잡을 수 있도록 개선하고자 한다.
그럼 이제부터 AVL 트리를 구현해보자~!

AVL 트리와 균형 인수 (Balance Factor)

AVL 트리는 G.M.Adelson-Velskii와 E.M.Landis에 의해 1960년대에 고안되었다.
그래서 트리의 이름도 이들의 이름을 따서 정해졌다.
AVL 트리는 노드가 추가될 때, 그리고 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 변경해 균형을 잡는 트리다.
AVL 트리에서의 균형의 정도를 표현하기 위해 '균형 인수(Balance Factor)'라는 것을 사용하는데 이는 균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이로 계산된다.
다음 두 개의 예시 이진 트리의 각 노드 별 균형 인수를 확인해보자.

노드 위에 적힌 숫자가 '균형 인수'다.
트리의 균형을 잡기 위해 구조를 재조정하는 것을 가리켜 리밸런싱(rebalancing)이라고 하는데, AVL 트리의 리밸런싱 시기를 짐작해보자.
균형 인수의 절댓값이 크면 클수록 그만큼 트리의 균형이 무너진 상태다.
따라서 AVL 트리는 균형 인수의 절댓값이 2 이상인 경우에 균형을 잡기 위한 트리의 재조정을 진행한다.

리밸런싱이 필요

AVL 트리의 균형이 무너지는 상태는 4가지로 정리가 된다.
그리고 각 상태 별 리밸런싱 방법에도 차이가 있다.

1) 첫 번째 상태와 LL회전

리밸런싱이 필요한 첫 번째 상태로 위 그림의 왼편을 보면 루트 노드의 균형 인수가 +2다.
이렇듯 균형 인수 +2가 연출된 상황을 "5가 저장된 노드의 왼쪽에 3이 저장된 자식 노드가 하나 존재하고, 그 자식 노드의 왼쪽에 1이 저장된 자식 노드가 또 하나 존재한다."라고 표현할 수 있다.
이 표현을 다시 잘 살펴보면 말의 핵심은 자식 노드 두 개가 왼쪽으로 연이어 연결되어 균형 인수 +2가 연출되었다는 것이다.
따라서 균형 인수 +2가 연출된 이 상태를 가리켜 "Left Left 상태". 즉, "LL상태"라 한다.
그리고 이러한 "LL상태"에서 발생한 불균형의 해소를 위해 등장한 리밸런싱 방법을 가리켜 'LL회전'이라 한다.
'LL회전'이란 'LL상태'에서 균형을 잡기 위해 필요한 회전을 의미한다.

따라서 위 그림에서 LL회전의 방법과 그 결과를 오른쪽에서 보여준다.
LL회전의 핵심은 균형 인수가 +2인 노드를 균형 인수가 +1인 노드의 오른쪽 자식 노드가 되게 하는데 있다.

따라서 위 그림처럼 pNode와 cNode가 각각 균형 인수가 +2인 노드와 그 자식 노드를 가리킨다고 가정하면, Chapter 11에서 완성한 BinaryTree3.c에 정의된 함수를 도구로 하여 ChangeRightSubTree(cNode, pNode); 문장으로 LL회전을 완성할 수 있다.

LL회전을 일반화한 그림은 다음과 같다.
그리고 사실 저 한문장으로 LL회전을 일반화하여 구현할 수는 없다.

T1, T2, T3, T4를 높이가 동일한 서브 트리라고 생각해보자.
이들은 5가 저장된 노드와 3이 저장된 노드의 균형 인수에 영향을 미치지 않는다.
때문에 이 그림의 구조 역시 LL상태에 해당한다.
그리고 T1, T2, T3, T4를 NULL로 치환하면 앞서 보인 LL상태가 된다.

이 그림에서 LL회전을 위해 추가로 고민해야 할 것은 무엇일까? T3이다.
T3의 부모 노드는 루트 노드가 될 것이기 때문에 T3의 자리를 다른 노드에게 양보해야한다.
예시 그림으로 치면 5가 저장된 노드에게 양보해야하고 이 후 T3는 어디로 가야할까?
5가 저장된 노드의 왼쪽 자식 노드의 위치이다.

따라서 위 그림의 오른쪽과 같이 cNode가 가리키는 노드의 오른쪽 서브 트리를 pNode가 가리키는 노드의 왼쪽 서브 트리로 옮기기 위해 ChangeLeftSubTree(pNode, GetRightSubTree(cNode)); 문장을 실행해야 한다.
따라서 일반화한 LL회전을 구현하려면 다음 문장을 순서대로 실행해야 한다.

ChangeLeftSubTree(pNode, GetRightSubTree(cNode));
ChangeRightSubTree(cNode, pNode);

2) 두 번째 상태와 RR회전

이번에는 리밸런싱이 필요한 두 번째 상태로 RR상태이자 RR회전이다.
RR상태와 LL상태의 차이점은 RR회전과 LL회전으로 방향이 유일한 차이이다.
따라서 위 그림과 같이 회전하면 된다.
5가 저장된 노드가 7이 저장된 노드의 왼쪽 자식 노드가 되고, T3은 5가 저장된 노드의 오른쪽 서브 트리가 된다.
코드로 나타내면 다음과 같다.

ChangeRightSubTree(pNode, GetLeftSubTree(cNode));
ChangeLeftSubTree(cNode, pNode);

LL회전과 RR회전에서 서브트리를 먼저 옮겨주는 것은 먼저 옮기지 않으면 이 서브 트리의 주소 값을 잃기 때문이다.

3) 세 번째 상태와 LR회전

리밸런싱이 필요한 세번째 상태로는 LR상태이자 LR회전이다.
LR회전은 LL상태나 RR상태보다 균형을 잡기 복잡하다.
한번의 회전으로 균형을 잡을 수 없기 때문이다.
따라서 LR상태를 한 번의 회전으로 균형이 잡히는 LL상태나 RR상태로 바꾼 다음 LL회전이나 RR회전으로 리밸런싱을 진행한다.
LR상태는 RR회전을 통해 LL상태가 될 수 있게 된다.
이는 RR회전의 부수적인 효과를 이용한 것으로 볼 수 있는데, 자세히 이 과정을 살펴보자.

No.	Pic.	Expl.
0		이것이 일반적인 RR회전이다.
1		여기서 9가 저장된 노드를 NULL로 치환한다.
2		그리고 RR회전을 진행하면 부모자식이 바뀌는 효과를 얻게 된다.

이 부수적인 효과를 이용해서 LR상태를 RR회전을 통해 LL상태로 만들 것이다.

위 그림과 같이 LR상태를 LL상태로 바꾸고

바뀐 부분을 LL회전을 통해 리밸런싱해 정리한다.

4) 네 번째 상태와 RL회전

마지막으로 리밸런싱이 필요한 상태로는 RL상태이자 RL회전이다.
위에서 이미 조금 복잡한 과정이었던 LR상태를 배웠다.
동일하게 RL상태를 LL회전을 통해 RR상태로 바꿔서 RR회전을 통해 리밸런싱을 한다.

RL상태에서 LL회전을 통해 RR상태로 만들고

마지막으로 RR회전을 통해 리밸런싱을 마무리한다.

---

12-2. 균형 잡힌 이진 탐색 트리: AVL 트리의 구현

AVL 트리의 '이론적 설명'과 '구현'을 구분한 이유는 AVL 트리의 이론적인 이해만으로도 의미가 있기 때문이다.

AVL 트리 구현 방법

AVL 트리도 이진 탐색 트리이므로, 이진 탐색 트리의 구현결과인 다음 파일들을 확장하여 AVL 트리를 구현하고자 한다.

• BinaryTree3.h : 이진 트리의 헤더파일
• BinaryTree3.c : 이진 트리를 구성하는데 필요한 도구들의 모임 (소스파일)
• BinarySearchTree2.h : 이진 탐색 트리의 헤더파일
• BinarySearchTree2.c : 이진 탐색 트리의 구현 (소스파일)

위 파일들은 Chapter 11에서 공부했던 내용으로 지난 게시물에서도 파일 내용을 확인할 수 있다.
위 파일들 중 BinarySearchTree2.c는 이진 탐색 트리의 구현 결과에 해당하는데 이 파일에서도 이진 트리의 구성을 위해서 BinaryTree3.c에 정의된 함수들을 호출한다.

그럼 AVL 트리의 구현을 위해서 BinaryTree3.c와 BinarySearchTree2.c를 변경해야할까?
BinaryTree3.c에 담긴 것은 이진 트리를 구성하는 도구들이기 때문에 이미 그 기능이 충분해서 변경하지 않고 BinarySearchTree2.c에 담겨있는 이진 탐색 트리에 리밸런싱 기능을 추가하면 AVL 트리가 된다.
따라서 BinarySearchTree2.c에 리밸런싱 기능을 추가하여 파일 이름을 BinarySearchTree3.c로 파일명을 변경할 것이다.
리밸런싱 기능은 리밸런싱에 필요한 함수를 추가로 정의하는 것이 아닌 노드의 추가 및 삭제 시 자동으로 리밸런싱이 진행되도록 그 기능을 확장할 것이다.

마지막으로 다음 두 파일을 추가로 생성하여 리밸런싱을 진행하는데 필요한 도구들을 선언하고 정의할 것이다.

• AVLRebalance.h : 리밸런싱 관련 함수들의 선언
• AVLRebalance.c : 리밸런싱 관련 함수들의 정의

위 파일들에서 정의된 리밸런싱 도구를 이용해 BinarySearchTree3.c에 담긴 AVL 트리 리밸런싱이 진행된다.

BinarySearchTree2.c의 확장 포인트(BinarySearchTree3.c)

루트 노드를 기준으로 왼쪽과 오른쪽의 균형이 잘 잡혀있는 이진 탐색 트리가 있다.
이 트리의 균형이 깨지는 (루트 노드의 균형 인수의 절댓값이 1을 넘어가는) 상황은 언제 발생할까?
노드의 삽입과 삭제의 과정에서 발생한다.
따라서 BinarySearchTree2.c의 이진 탐색 트리를 AVL 트리가 되게 하기 위해서 확장해야 하는 함수는 다음 두 가지다.

• BSTInsert 함수 : 트리에 노드를 추가
• BSTRemove 함수 : 트리에서 노드를 제거

따라서 트리의 균형을 재조정하는 함수의 이름을 Rebalance라 했을 때, 위에서 언급한 두 함수는 대략 다음과 같은 방식으로 확장될 것이다.

void BSTInsert(BTreeNode ** pRoot, BSTData data)
{
	....
    Rebalance(pRoot);	// 노드 추가 후 리밸런싱
}

BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target)
{
	....
    Rebalance(pRoot);	// 노드 제거 후 리밸런싱
    return dNode;
}

Rebalance 함수 호출문을 보면 인자로 루트 노드의 정보를 전달하고 있다.
이는 트리의 불균형 여부를 루트 노드를 기준으로 확인해야 하기 때문이다.

리밸런싱에 필요한 도구들의 정의

리밸런싱에 필요한 도구들을 살펴보기 위해서는 다음 두 질문에 답을 해야한다.

1. 이 트리는 리밸런싱이 필요한 불균형 상태인가?
2. 왼쪽 서브 트리의 높이는 어떻게 되며, 오른쪽 서브 트리의 높이는 어떻게 되는가?

불균형의 여부는 루트 노드 기준으로 판단하고, 루트 노드의 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이를 확인해서 그 차를 계산해 각 서브 트리의 높이와 불균형 여부를 확인할 수 있다.

1) 균형을 이루고 있는가?

리밸런싱에 필요한 첫 번째 도구로 다음 함수를 정의한다.

// 트리의 높이를 계산하여 반환
int GetHeight(BTreeNode * bst)
{
	int leftH;		// left height
    int rightH;		// right height
    
    if(bst == NULL)
    	return 0;
    
    leftH = GetHeight(GetLeftSubTree(bst));		// 왼쪽 서브 트리의 높이 계산
    rightH = GetHeight(GetRightSubTree(bst));	// 오른쪽 서브 트리의 높이 계산
    
    // 큰 값의 높이를 반환
    if(leftH > rightH)
    	return leftH + 1;
    else
    	return rightH + 1;
}

트리는 단말 노드의 수만큼 경로가 나뉘기 때문에, 그리고 트리의 높이는 그 중에서 가장 깊이 뻗은 경로를 기준으로 결정되기 때문에 위와 같이 재귀적인 형태로 정의해야 한다.
위 함수는 GetHeight 함수가 호출될 때마다 높이를 1씩 더해가는 구조로 정의되어 있다.
그리고 동일한 레벨에서의 왼쪽 서브 트리와 오른쪽 서브 트리의 높이를 비교하여 큰 값이 반환되도록 정의되어 있다.
따라서 트리의 모든 경로 중에서 가장 깊이 뻗은 경로의 높이를 반환하게 된다.

이 트리 높이를 계산하는 도구를 이용해서 균형 인수를 계산해주는 함수를 만든다.

// 두 서브 트리의 '높이의 차(균형 인수)'를 반환
int GetHeightDiff(BTreeNode * bst)
{
	int lsh;	// left sub tree height
    int rsh;	// right sub tree height
    
    if(bst == NULL)
    	return 0;
    
    lsh = GetHeight(GetLeftSubTree(bst));	// 왼쪽 서브 트리의 높이
    rsh = GetHeight(GetRightSubTree(bst));	// 오른쪽 서브 트리의 높이
    return lsh - rsh;	// 균형 인수 계산 결과 반환
}

왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이를 구하고 그 차를 반환하는 매우 간단한 함수다.
그럼에도 불구하고 매우 유용하게 사용할 수 있다.
이로써 불균형의 여부를 판단하는데 필요한 도구를 모두 마련했다.

2) LL회전, RR회전

리밸런싱에 필요한 도구로 회전관련 함수를 추가해보자.
앞서 배운 이론적 설명을 근거로 구현하면 된다.

먼저, LL회전을 담당하는 함수부터 살펴보자.

// LL회전을 담당하는 함수
BTreeNode * RotateLL(BTreeNode * bst)
{
	BTreeNode * pNode;		// parent node
    BTreeNode * cNode;		// child node
    
    // pNode와 cNode가 LL회전을 위해 적절한 위치 가리키기
    pNode = bst;
    cNode = GetLeftSubTree(pNode);
    
    // 실제 LL회전을 담당하는 부분
    ChangeLeftSubTree(pNode, GetRightSubTree(cNode));
    ChangeRightSubTree(cNode, pNode);
    
    // LL회전으로 인해 변경된 루트 노드의 주소 값 반환
    return cNode;
}

위 함수는 다음 그림과 같은 LL상태에서 호출된다.

호출될 때 5가 저장된 노드의 주소 값이 인자로 전달된다.
LL회전이 완료되고 나면 (함수의 마지막 부분에서) 루트 노드가 바뀌게 된다.
따라서 변경된 루트 노드의 정보를 반환해야 한다.
그래서 cNode에 저장된 값을 반환하는 것이다.

다음으로, RR회전을 담당하는 함수를 살펴보자.

// RR회전을 담당하는 함수
BTreeNode * RotateRR(BTreeNode * bst)
{
	BTreeNode * pNode;		// parent node
    BTreeNode * cNode;		// child node
    
    // pNode와 cNode가 RR회전을 위해 적절한 위치를 가리키기
    pNode = bst;
    cNode = GetRightSubTree(pNode);
    
    // 실제 RR회전을 담당하는 부분
    ChangeRightSubTree(pNode, GetLeftSubTree(cNode));
    ChangeLeftSubTree(cNode, pNode);
    
    // RR회전으로 인해 변경된 루트 노드의 주소 값 반환
    return cNode;
}

구현된 코드를 살펴보면 RotateLL함수와 방향 말고는 차이가 없다.

2) LR회전, RL회전

앞서 LR회전과 RL회전에 대해 이론적 설명을 통해 이해했다.
코드로 어떻게 표현되어야 하는지 다시 한번 정리하면 다음과 같다.

• LR회전 : 부분적 RR회전에 이어서 LL회전 진행
• RL회전 : 부분적 LL회전에 이어서 RR회전 진행

그럼 먼저 LR회전을 담당하는 함수의 구현을 살펴보자.

// LR회전을 담당하는 함수
BTreeNode * RotateLR(BTreeNode * bst)
{
	BTreeNode * pNode;		// parent node
    BTreeNode * cNode;		// child node
    
    // pNode와 cNode가 LR회전을 위해 적잘한 위치를 가리키기
    pNode = bst;
    cNode = GetLeftSubTree(pNode);
    
    // 실제 LR회전을 담당하는 부분
    ChangeLeftSubTree(pNode, RotateRR(cNode));	// 부분적 RR회전
    return RotateLL(pNode);						// LL회전
}

실제 LR회전을 담당하는 부분 코드에서 ChangeLeftSubTree(pNode, RotateRR(cNode));를 살펴보자.
우선 RotateRR 함수를 호출하면서 cNode를 전달한다.
cNode가 가리키는 위치는 다음 그림과 같다.

RotateRR 함수 호출을 통해서 1이 저장된 노드 즉, 5가 저장된 루트 노드의 왼쪽 자식 노드를 중심으로 RR회전을 진행한다.
이렇듯 일부를 떼어서 회전을 진행한다는 것은 루트 노드가 아닌 1이 저장된 노드의 주소 값을 인자로 RotateRR 함수를 호출함을 의미한다.

RotateRR 함수 호출이 완료되면 아래 그림에서 3이 저장된 노드의 주소 값이 반환된다.

그리고 이 주소 값을 두 번째 인자로 하여 ChangeLeftSubTree 함수를 호출하여 LL 상태가 되게 한다.
위 그림에서 '다시 붙인다'는 말은 ChangeLeftSubTree 함수를 호출하면서 RotateRR 함수의 반환 값을 두 번째 인자로 전달한다는 것을 의마한다.

LR회전의 첫 번째 단계인 부분적 RR회전이 완료된 후 그 다음 문장인 return RotateLL(pNode); 부분이 실행되고 이것이 LL회전이다.
RotateLR 함수의 반환 값으로 RotateLL 함수의 반환 값ㅇ르 반환하는 이유는 LR회전의 결과로 바뀌게 된 루트 노드의 주소 값을 반환하기 위함이다.

마지막으로 RL회전을 담당하는 함수의 구현을 보자.

// RL회전을 담당하는 함수
BTreeNode * RotateRL(BTreeNode * bst)
{
	BTreeNode * pNode;		// parent node
    BTreeNode * cNode;		// child node
    
    // pNode와 cNode가 RL회전을 위해 적절한 위치를 가리키기
    pNode = bst;
    cNode = GetRightSubTree(pNode);
    
    // 실제 RL회전을 담당하는 부분
    ChangeRightSubTree(pNode, RotateLL(cNode));	// 부분적 LL회전
    return RotateRR(pNode);						// RR회전
}

RotateLR 함수와 방향 및 회전의 순서에만 차이를 보인다.

3) Rebalance 함수

불균형 여부를 판단하는 도구와 상태에 따른 회전 도구를 만듦으로써 기본적인 도구는 모두 마련이 되었다.
마지막으로 이 도구들을 사용하기 편하도록 이 도구들의 사용순서 및 사용시기를 모두 담은 도구를 하나 만든다.

BTreeNode * Rebalance(BTreeNode ** pRoot)
{
	int hDiff = GetHeightDiff(*pRoot);		// 균형 인수 계산
    
    // 균형 인수가 +2 이상이면 LL상태 또는 LR상태
    if(hDiff > 1)	// 왼쪽 서브 트리 방향으로 높이가 2이상 크다면,
    {
    	if(GetHeightDiff(GetLeftSubTree(*pRoot)) > 0)
        	*pRoot = RotateLL(*pRoot);
        else
        	*pRoot = RotateLR(*pRoot);
    }
    
    // 균형 인수가 -2 이하면 RR상태 또는 RL상태
    if(hDiff < -1)	// 오른쪽 서브 트리 방향으로 높이가 2 이상 크다면,
    {
    	if(GetHeightDiff(GetRightSubTree(*pRoot)) < 0)
        	*pRoot = RotateRR(*pRoot);
        else
        	*pRoot = RotateRL(*pRoot);
    }
    
    return *pRoot;
}

루트 노드의 균형 인수가 +2 이상이면 LL상태 또는 LR상태이고,
-2 이하면 RR상태 또는 RL상태란 것은 알고 있을 것이다.
그럼 LL상태와 LR상태를 구분하는 방법에 대해 자세히 이해해보자.

GetHeightDiff(GetLeftSubTree(*pRoot))부분의 반환값을 살펴보면
LL상태라면 +1이므로 0보다 크게 되고, 따라서 RotateLL 함수가 호출된다.
LR상태라면 -1이므로 0보다 작게 되고, 따라서 RotateLR 함수가 호출된다.

RR상태와 RL상태를 구분하는 방법도 비슷하게 다음과 같다.

RR상태라면 -1이므로 0보다 작게 되고, 따라서 RotateRR 함수가 호출된다.
RL상태라면 +1이므로 0보다 크게 되고, 따라서 RotateRL 함수가 호출된다.

참고로 XX방향 회전관련 함수의 호출은 *pRoot = RotateXX(*pRoot); 와 같은 형태를 보이게 되고,
Rebalance 함수의 마지막 문장이 return *pRoot;로 루트 노드의 주소 값 정보를 반환한다.
반환하는 이유는 회전의 과정에서 루트 노드가 변경될 수 있기 때문이다.
따라서 Rebalance 함수를 호출할 때는 루트 노드의 변경을 대비해서 이 함수가 반환하는 값을 루트 노드를 가리키는 포인터 변수에 저장해야 한다.

4) 리밸런싱의 도구

리밸런싱 도구를 담고 있는 헤더파일과 소스파일을 정리하려한다.
설명은 앞에서 다 했으므로 자세한 설명은 생략하고 코드만 보여주려 한다.

- AVLRebalance.h

#ifndef __AVL_REBALANCE_H__
#define __AVL_REBALANCE_H__

#include "BinaryTree3.h"

// 트리의 균형 잡기 (Rebalnceing)
BTreeNode * Rebalance(BTreeNode ** pRoot);

#endif

- AVLRebalance.c

#include <stdio.h>
#include "BinaryTree3.h"

// LL회전
BTreeNode * RotateLL(BTreeNode * bst)
{
    BTreeNode * pNode;		// parent node
    BTreeNode * cNode;		// child node
    
    // pNode와 cNode가 LL회전을 위해 적절한 위치 가리키기
    pNode = bst;
    cNode = GetLeftSubTree(pNode);
    
    // 실제 LL회전을 담당하는 부분
    ChangeLeftSubTree(pNode, GetRightSubTree(cNode));
    ChangeRightSubTree(cNode, pNode);
    
    // LL회전으로 인해 변경된 루트 노드의 주소 값 반환
    return cNode;
}

// RR회전
BTreeNode * RotateRR(BTreeNode * bst)
{
	BTreeNode * pNode;		// parent node
    BTreeNode * cNode;		// child node
    
    // pNode와 cNode가 RR회전을 위해 적절한 위치를 가리키기
    pNode = bst;
    cNode = GetRightSubTree(pNode);
    
    // 실제 RR회전을 담당하는 부분
    ChangeRightSubTree(pNode, GetLeftSubTree(cNode));
    ChangeLeftSubTree(cNode, pNode);
    
    // RR회전으로 인해 변경된 루트 노드의 주소 값 반환
    return cNode;
}

// LR회전
BTreeNode * RotateLR(BTreeNode * bst)
{
	BTreeNode * pNode;		// parent node
    BTreeNode * cNode;		// child node
    
    // pNode와 cNode가 LR회전을 위해 적잘한 위치를 가리키기
    pNode = bst;
    cNode = GetLeftSubTree(pNode);
    
    // 실제 LR회전을 담당하는 부분
    ChangeLeftSubTree(pNode, RotateRR(cNode));	// 부분적 RR회전
    return RotateLL(pNode);						// LL회전
}

// RL회전
BTreeNode * RotateRL(BTreeNode * bst)
{
	BTreeNode * pNode;		// parent node
    BTreeNode * cNode;		// child node
    
    // pNode와 cNode가 RL회전을 위해 적절한 위치를 가리키기
    pNode = bst;
    cNode = GetRightSubTree(pNode);
    
    // 실제 RL회전을 담당하는 부분
    ChangeRightSubTree(pNode, RotateLL(cNode));	// 부분적 LL회전
    return RotateRR(pNode);						// RR회전
}

// 트리의 높이를 계산하여 반환
int GetHeight(BTreeNode * bst)
{
	int leftH;		// left height
    int rightH;		// right height
    
    if(bst == NULL)
    	return 0;
    
    leftH = GetHeight(GetLeftSubTree(bst));		// 왼쪽 서브 트리의 높이 계산
    rightH = GetHeight(GetRightSubTree(Bst));	// 오른쪽 서브 트리의 높이 계산
    
    // 큰 값의 높이를 반환
    if(leftH > rightH)
    	return leftH + 1;
    else
    	return rightH + 1;
}

// 두 서브 트리의 '높이의 차(균형 인수)'를 반환
int GetHeightDiff(BTreeNode * bst)
{
	int lsh;	// left sub tree height
    int rsh;	// right sub tree height
    
    if(bst == NULL)
    	return 0;
    
    lsh = GetHeight(GetLeftSubTree(bst));	// 왼쪽 서브 트리의 높이
    rsh = GetHeight(GetRightSubTree(bst));	// 오른쪽 서브 트리의 높이
    return lsh - rsh;	// 균형 인수 계산 결과 반환
}

// Rebalance 함수
BTreeNode * Rebalance(BTreeNode ** pRoot)
{
	int hDiff = GetHeightDiff(*pRoot);		// 균형 인수 계산
    
    // 균형 인수가 +2 이상이면 LL상태 또는 LR상태
    if(hDiff > 1)	// 왼쪽 서브 트리 방향으로 높이가 2이상 크다면,
    {
    	if(GetHeightDiff(GetLeftSubTree(*pRoot)) > 0)
        	*pRoot = RotateLL(*pRoot);
        else
        	*pRoot = RotateLR(*pRoot);
    }
    
    // 균형 인수가 -2 이하면 RR상태 또는 RL상태
    if(hDiff < -1)	// 오른쪽 서브 트리 방향으로 높이가 2 이상 크다면,
    {
    	if(GetHeightDiff(GetRightSubTree(*pRoot)) < 0)
        	*pRoot = RotateRR(*pRoot);
        else
        	*pRoot = RotateRL(*pRoot);
    }
    
    return *pRoot;
}

AVL 트리를 담고 있는 파일

앞에서 BSTInsert 함수와 BSTRemove 함수를 소개하면서 Rebalance 함수의 호출시기를 언급했었는데 이 부분에 대해서 루트 노드가 변경되는 것을 대비해서 함수의 호출 문장을 수정해야 한다.

void BSTInsert(BTreeNode ** pRoot, BSTData data)
{
	....
    *pRoot = Rebalance(pRoot);	// 노드 추가 후 리밸런싱
}

BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target)
{
	....
    *pRoot = Rebalance(pRoot);	// 노드 제거 후 리밸런싱
    return dNode;
}

여기서 주의해야할 점은 노드를 추가할 때 삽입 과정에서 불균형 여부ㄹ의 확인 대상을 루트 노드만으로 하는 경우 모든 불균형 상황을 감지하지 못하기 때문에 경우를 나누어 리밸런싱을 진행해야 한다.

그 과정은 다음과 같다.

1. 루트 노드를 대상으로 데이터의 저장을 시도 (함수 호출 시작)
2. 루트 노드에 저장된 데이터와 새 데이터 비교
   3-1. 비교하여 새 데이터의 값이 작으면 왼쪽 자식 노드를 루트 노드로 하여 데이터의 저장을 시도
   3-2. 비교하여 새 데이터의 값이 크면 오른쪽 자식 노드를 루트 노드로 하여 데이터의 저장을 시도
3. 저장이 완료되면 해당 루트 노드를 기준으로 리밸런싱 진행

그림으로 이 과정에 대한 이해를 더 잘해보자.

이와 같은 이진 트리가 있고 이는 균형 잡혀 있는 상태다.
여기서 6이 저장된 노드를 추가하려 한다.

그럼 위와 같이 균형이 잡히지 않는 상태가 된다.
이러한 형태로 균형이 무너지게 되면 루트 노드를 기준으로 어떤 회전을 하더라도 균형이 잡히지 않는다.
사실 4가 저장된 노드에서부터 균형이 무너진 상태가 되는데 따라서 4를 중심으로 리밸런싱을 진행해야 한다.

4가 저장된 노드를 중심으로 리밸런싱을 진행하면 위 그림과 같이 균형이 맞게 된다.

이와 같이 새로 저장된 노드의 부모 노드들을 모두 살펴야 한다.
위 그림에서는 3, 4, 5가 저장된 노드를 기준으로 불균형 여부를 검사해야 한다.
6이 저장된 이 후에도 불균형 여부 검사를 해야한다.

따라서 BSTInsert 함수는 다음과 같이 수정되어야 한다.

void * BSTInsert(BTreeNode ** pRoot, BSTData data)
{
	if(*pRoot == NULL)
    {
    	*pRoot = MakeBTreeNode();
        SetData(*pRoot, data);
    }
    else if(data < GetData(*pRoot))
    {
    	BSTInsert(&((*pRoot)->left),data);
        *pRoot = Rebalance(pRoot);
    }
    else if(data > GetData(*pRoot))
    {
    	BSTInsert(&((*pRoot)->right),data);
        *pRoot = Rebalance(pRoot);
    }
    else
    	return NULL;	// 키의 중복을 허용하지 않음
    
    return *pRoot;
}

헤더파일을 포함한 #include문의 변화를 제외하고는 Rebalance 함수의 호출문 추가가 BinarySearchTree3.c에서의 유일한 변화다.
BinarySearchTree3.h에서의 변화는 없다.
각 파일의 내용은 아래에 정리해두었다.

1) BinarySearchTree3.h

#ifndef __BINARY_SEARCH_TREE3_H__
#define __BINARY_SEARCH_TREE3_H__

#include "BinaryTree3.h"

typedef BTData BSTData;

// BST의 생성 및 초기화
void BSTMakeAndInit(BTreeNode ** pRoot);

// 노드에 저장된 데이터 반환
BSTData BSTGetNodeData(BTreeNode * bst);

// BST를 대상으로 데이터 저장(노드의 생성과정 포함)
void BSTInsert(BTreeNode ** pRoot, BSTData data);

// BST를 대상으로 데이터 탐색
BTreeNode * BSTSearch(BTreeNode * bst, BSTData target);

// 트리에서 노드를 제거하고 제거된 노드의 주소 값 반환
BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target);

// 이진 탐색 트리에 저장된 모든 노드의 데이터 출력
void BSTShowAll(BTreeNode * bst);

#endif

2) BinarySearchTree3.c

#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree3.h"
#include "BinarySearchTree3.h"
#include "AVLRebalance.h"

void BSTMakeAndInit(BTreeNode ** pRoot)
{
    *pRoot = NULL;
}

BSTData BSTGetNodeData(BTreeNode * bst)
{
    return GetData(bst);
}

void * BSTInsert(BTreeNode ** pRoot, BSTData data)
{
	if(*pRoot == NULL)
    {
    	*pRoot = MakeBTreeNode();
        SetData(*pRoot, data);
    }
    else if(data < GetData(*pRoot))
    {
    	BSTInsert(&((*pRoot)->left),data);
        *pRoot = Rebalance(pRoot);
    }
    else if(data > GetData(*pRoot))
    {
    	BSTInsert(&((*pRoot)->right),data);
        *pRoot = Rebalance(pRoot);
    }
    else
    	return NULL;	// 키의 중복을 허용하지 않음
    
    return *pRoot;
}

BTreeNode * BSTSearch(BTreeNode * bst, BSTData target)
{
    BTreeNode * cNode = bst;        // current node
    BSTData cd;                     // current data

    while(cNode != NULL)
    {
        cd = GetData(cNode);

        if(target == cd)
            return cNode;
        else if(target < cd)
            cNode = GetLeftSubTree(cNode);
        else
            cNode = GetRightSubTree(cNode);
    }

    return NULL;    // 탐색대상이 저장되어 있지 않음.
}

BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target)
{
    // 삭제 대상이 루트 노드인 경우 별도로 고려
    BTreeNode * pVRoot = MakeBTreeNode();   // 가상의 루트 노드
    BTreeNode * pNode = pVRoot;             // parent node
    BTreeNode * cNode = *pRoot;             // current node
    BTreeNode * dNode;                      // delete node

    // 루트 노드를 pVRoot가 가리키는 노드의 오른쪽 자식 노드가 되게
    ChangeRightSubTree(pVRoot, *pRoot);

    // 삭제 대상인 노드를 탐색
    while(cNode != NULL && GetData(cNode) != target)
    {
        pNode = cNode;

        if(target < GetData(cNode))
            cNode = GetLeftSubTree(cNode);
        else
            cNode = GetRightSubTree(cNode);
    }
    // 삭제 대상이 존재하지 않다면
    if(cNode == NULL)
        return NULL;
    
    // 삭제 대상 dNode 가리키게
    dNode = cNode;

    // 경우 1) 삭제 대상이 단말 노드
    if(GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL)
    {
        if(GetLeftSubTree(pNode) == dNode)
            RemoveLeftSubTree(pNode);
        else
            RemoveRightSubTree(pNode);
    }

    // 경우 2) 삭제 대상이 하나의 자식 노드
    else if(GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL)
    {
        // 삭제 대상의 자식 노드
        BTreeNode * dcNode;

        if(GetLeftSubTree(dNode) != NULL)
            dcNode = GetLeftSubTree(dNode);
        else
            dcNode = GetRightSubTree(dNode);
        
        if(GetLeftSubTree(pNode) == dNode)
            ChangeLeftSubTree(pNode, dcNode);
        else
            ChangeRightSubTree(pNode, dcNode);
    }

    // 경우 3) 삭제 대상이 두 개의 자식 노드
    else
    {
        // 대체 노드 가리킴
        BTreeNode * mNode = GetRightSubTree(dNode);
        // 대체 노드의 부모 노드
        BTreeNode * mpNode = dNode;
        int delData;

        // 삭제 대상의 대체 노드 찾기
        while(GetLeftSubTree(mNode) != NULL)
        {
            mpNode = mNode;
            mNode = GetLeftSubTree(mNode);
        }

        // 대체 노드에 저장된 값을 삭제 노드에 대입
        delData = GetData(dNode);
        SetData(dNode, GetData(mNode));

        // 대체 노드의 부모 노드와 자식 노드 연결
        if(GetLeftSubTree(mpNode) == mNode)
            ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
        else
            ChangeRightSubTree(mpNode, GetRightSubTree(mNode));
        
        dNode = mNode;
        SetData(dNode, delData);
    }

    // 삭제된 노드가 루트 노드인 경우
    if(GetRightSubTree(pVRoot) != *pRoot)
        *pRoot = GetRightSubTree(pVRoot);   // 루트 노드의 변경 반영
    
    free(pVRoot);   // 가상 루트 노드 소멸

    // Rebalancing 추가
    *pRoot = Rebalance(pRoot);
    return dNode;   // 삭제된 노드 반환
}

void ShowIntData(int data)
{
    printf("%d ", data);
}

void BSTShowAll(BTreeNode * bst)
{   
    // 중위 순회
    InorderTraverse(bst, ShowIntData);
    printf("\n");
}

3) AVLTreeMain.c

이제 마지막으로 AVL 트리가 리밸런싱을 제대로 하는지 확인해보자.

#include <stdio.h>
#include "BinaryTree3.h"
#include "BinarySearchTree3.h"

int main()
{
    BTreeNode * avlRoot;
    BTreeNode * clNode;         // current left node
    BTreeNode * crNode;         // current right node
    BSTMakeAndInit(&avlRoot);

    BSTInsert(&avlRoot, 1);
    BSTInsert(&avlRoot, 2);
    BSTInsert(&avlRoot, 3);
    BSTInsert(&avlRoot, 4);
    BSTInsert(&avlRoot, 5);
    BSTInsert(&avlRoot, 6);
    BSTInsert(&avlRoot, 7);
    BSTInsert(&avlRoot, 8);
    BSTInsert(&avlRoot, 9);

    printf("Root Node: %d \n", GetData(avlRoot));

    clNode = GetLeftSubTree(avlRoot);
    crNode = GetRightSubTree(avlRoot);
    printf("Left 1: %d, Right 1: %d \n", GetData(clNode), GetData(crNode));

    clNode = GetLeftSubTree(clNode);
    crNode = GetRightSubTree(crNode);
    printf("Left 2: %d, Right 2: %d \n", GetData(clNode), GetData(crNode));

    clNode = GetLeftSubTree(clNode);
    crNode = GetRightSubTree(crNode);
    printf("Left 3: %d, Right 3: %d \n", GetData(clNode), GetData(crNode));

    clNode = GetLeftSubTree(clNode);
    crNode = GetRightSubTree(crNode);
    printf("Left 4: %d, Right 4: %d \n", GetData(clNode), GetData(crNode));

    return 0;
}

> gcc .\AVLRebalance.c .\AVLTreeMain.c .\BinarySearchTree3.c .\BinaryTree3.c
> .\a.exe
> 출력
Root Node: 4 
Left 1: 2, Right 1: 6 
Left 2: 1, Right 2: 8
Left 3: 6422400, Right 3: 1528349827
Left 4: 6422400, Right 4: 1528349827

> 올바른 출력
Root Node: 5
Left 1: 4, Right 1: 6
Left 2: 3, Right 2: 7
Left 3: 2, Right 3: 8
Left 4: 1, Right 4: 9

왜 안될까,,,,

수정

방법을 알아냈다.

마지막에 넣는 자식 노드의 이름들을 잘못 넣었다.
예를 들면 지금 노드 변수가 3쌍(clNode-crNode, clNode2-crNode2, clNode3-crNode3)이 있는데
루트 노드용(avlRoot), 루트 노드의 첫 번째 자식들 노드용(clNode-crNode), 루트 노드의 두 번째 자식들 노드용(clNode2-crNode2), 루트 노드의 세 번째 자식들 노드용(clNode3-crNode3)이다.

이 이름들을 잘 기억하고 있어야한다...
이를 아래와 같이 작성해서 실행해야 한다.

	// 변수 추가
    BTreeNode * clNode2;
    BTreeNode * crNode2;

    BTreeNode * clNode3;
    BTreeNode * crNode3;
    
    // 첫 번째 printf 이후 수정
    clNode = GetLeftSubTree(avlRoot);
    crNode = GetRightSubTree(avlRoot);
    printf("Left 1: %d, Right 1: %d \n", GetData(clNode), GetData(crNode));

    clNode2 = GetLeftSubTree(clNode);	// l 2개 주의
    crNode2 = GetRightSubTree(clNode);	// l 2개 주의
    printf("Left 2: %d, Right 2: %d \n", GetData(clNode2), GetData(crNode2));

    clNode2 = GetLeftSubTree(crNode);	// r 2개 주의
    crNode2 = GetRightSubTree(crNode);	// r 2개 주의
    printf("Left 3: %d, Right 3: %d \n", GetData(clNode2), GetData(crNode2));

    clNode3 = GetLeftSubTree(crNode2);	// r 2개 주의
    crNode3 = GetRightSubTree(crNode2);	// r 2개 주의
    printf("Left 4: %d, Right 4: %d \n", GetData(clNode3), GetData(crNode3));

파일들을 다 정리하면 아래와 같다.

1) BinarySearchTree3.h

#ifndef __BINARY_SEARCH_TREE3_H__
#define __BINARY_SEARCH_TREE3_H__

#include "BinaryTree3.h"

typedef BTData BSTData;

// BST의 생성 및 초기화
void BSTMakeAndInit(BTreeNode ** pRoot);

// 노드에 저장된 데이터 반환
BSTData BSTGetNodeData(BTreeNode * bst);

// BST를 대상으로 데이터 저장(노드의 생성과정 포함)
BTreeNode * BSTInsert(BTreeNode ** pRoot, BSTData data);

// BST를 대상으로 데이터 탐색
BTreeNode * BSTSearch(BTreeNode * bst, BSTData target);

// 트리에서 노드를 제거하고 제거된 노드의 주소 값 반환
BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target);

// 이진 탐색 트리에 저장된 모든 노드의 데이터 출력
void BSTShowAll(BTreeNode * bst);

#endif

2) BinarySearchTree3.c

#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree3.h"
#include "BinarySearchTree3.h"
#include "AVLRebalance.h"

void BSTMakeAndInit(BTreeNode ** pRoot)
{
    *pRoot = NULL;
}

BSTData BSTGetNodeData(BTreeNode * bst)
{
    return GetData(bst);
}

BTreeNode * BSTInsert(BTreeNode ** pRoot, BSTData data)
{
	if(*pRoot == NULL)
    {
    	*pRoot = MakeBTreeNode();
        SetData(*pRoot, data);
    }
    else if(data < GetData(*pRoot))
    {
    	BSTInsert(&((*pRoot)->left),data);
        *pRoot = Rebalance(pRoot);
    }
    else if(data > GetData(*pRoot))
    {
    	BSTInsert(&((*pRoot)->right),data);
        *pRoot = Rebalance(pRoot);
    }
    else
    {
    	return NULL;	// 키의 중복을 허용하지 않음
    }

    return *pRoot;
}

BTreeNode * BSTSearch(BTreeNode * bst, BSTData target)
{
    BTreeNode * cNode = bst;        // current node
    BSTData cd;                     // current data

    while(cNode != NULL)
    {
        cd = GetData(cNode);

        if(target == cd)
            return cNode;
        else if(target < cd)
            cNode = GetLeftSubTree(cNode);
        else
            cNode = GetRightSubTree(cNode);
    }

    return NULL;    // 탐색대상이 저장되어 있지 않음.
}

BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target)
{
    // 삭제 대상이 루트 노드인 경우 별도로 고려
    BTreeNode * pVRoot = MakeBTreeNode();   // 가상의 루트 노드
    BTreeNode * pNode = pVRoot;             // parent node
    BTreeNode * cNode = *pRoot;             // current node
    BTreeNode * dNode;                      // delete node

    // 루트 노드를 pVRoot가 가리키는 노드의 오른쪽 자식 노드가 되게
    ChangeRightSubTree(pVRoot, *pRoot);

    // 삭제 대상인 노드를 탐색
    while(cNode != NULL && GetData(cNode) != target)
    {
        pNode = cNode;

        if(target < GetData(cNode))
            cNode = GetLeftSubTree(cNode);
        else
            cNode = GetRightSubTree(cNode);
    }
    // 삭제 대상이 존재하지 않다면
    if(cNode == NULL)
        return NULL;
    
    // 삭제 대상 dNode 가리키게
    dNode = cNode;

    // 경우 1) 삭제 대상이 단말 노드
    if(GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL)
    {
        if(GetLeftSubTree(pNode) == dNode)
            RemoveLeftSubTree(pNode);
        else
            RemoveRightSubTree(pNode);
    }

    // 경우 2) 삭제 대상이 하나의 자식 노드
    else if(GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL)
    {
        // 삭제 대상의 자식 노드
        BTreeNode * dcNode;

        if(GetLeftSubTree(dNode) != NULL)
            dcNode = GetLeftSubTree(dNode);
        else
            dcNode = GetRightSubTree(dNode);
        
        if(GetLeftSubTree(pNode) == dNode)
            ChangeLeftSubTree(pNode, dcNode);
        else
            ChangeRightSubTree(pNode, dcNode);
    }

    // 경우 3) 삭제 대상이 두 개의 자식 노드
    else
    {
        // 대체 노드 가리킴
        BTreeNode * mNode = GetRightSubTree(dNode);
        // 대체 노드의 부모 노드
        BTreeNode * mpNode = dNode;
        int delData;

        // 삭제 대상의 대체 노드 찾기
        while(GetLeftSubTree(mNode) != NULL)
        {
            mpNode = mNode;
            mNode = GetLeftSubTree(mNode);
        }

        // 대체 노드에 저장된 값을 삭제 노드에 대입
        delData = GetData(dNode);
        SetData(dNode, GetData(mNode));

        // 대체 노드의 부모 노드와 자식 노드 연결
        if(GetLeftSubTree(mpNode) == mNode)
            ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
        else
            ChangeRightSubTree(mpNode, GetRightSubTree(mNode));
        
        dNode = mNode;
        SetData(dNode, delData);
    }

    // 삭제된 노드가 루트 노드인 경우
    if(GetRightSubTree(pVRoot) != *pRoot)
        *pRoot = GetRightSubTree(pVRoot);   // 루트 노드의 변경 반영
    
    free(pVRoot);   // 가상 루트 노드 소멸

    // Rebalancing 추가
    *pRoot = Rebalance(pRoot);
    return dNode;   // 삭제된 노드 반환
}

void ShowIntData(int data)
{
    printf("%d ", data);
}

void BSTShowAll(BTreeNode * bst)
{   
    // 중위 순회
    InorderTraverse(bst, ShowIntData);
    printf("\n");
}

3) AVLTreeMain.c

#include <stdio.h>
#include "BinaryTree3.h"
#include "BinarySearchTree3.h"

int main()
{
    BTreeNode * avlRoot;
    BTreeNode * clNode;         // current left node
    BTreeNode * crNode;         // current right node

    BTreeNode * clNode2;
    BTreeNode * crNode2;

    BTreeNode * clNode3;
    BTreeNode * crNode3;

    BSTMakeAndInit(&avlRoot);

    BSTInsert(&avlRoot, 1);
    BSTInsert(&avlRoot, 2);
    BSTInsert(&avlRoot, 3);
    BSTInsert(&avlRoot, 4);
    BSTInsert(&avlRoot, 5);
    BSTInsert(&avlRoot, 6);
    BSTInsert(&avlRoot, 7);
    BSTInsert(&avlRoot, 8);
    BSTInsert(&avlRoot, 9);

    printf("Root Node: %d \n", GetData(avlRoot));

    clNode = GetLeftSubTree(avlRoot);
    crNode = GetRightSubTree(avlRoot);
    printf("Left 1: %d, Right 1: %d \n", GetData(clNode), GetData(crNode));

    clNode2 = GetLeftSubTree(clNode);
    crNode2 = GetRightSubTree(clNode);
    printf("Left 2: %d, Right 2: %d \n", GetData(clNode2), GetData(crNode2));

    clNode2 = GetLeftSubTree(crNode);
    crNode2 = GetRightSubTree(crNode);
    printf("Left 3: %d, Right 3: %d \n", GetData(clNode2), GetData(crNode2));

    clNode3 = GetLeftSubTree(crNode2);
    crNode3 = GetRightSubTree(crNode2);
    printf("Left 4: %d, Right 4: %d \n", GetData(clNode3), GetData(crNode3));

    return 0;
}

> gcc .\AVLRebalance.c .\AVLTreeMain.c .\BinarySearchTree3.c .\BinaryTree3.c
> .\a.exe
> 출력
Root Node: 4
Left 1: 2, Right 1: 6
Left 2: 1, Right 2: 3
Left 3: 5, Right 3: 8
Left 4: 7, Right 4: 9

따라서 위 코드대로 작성하면 루트 노드에 5가 저장되는 것이 아닌 4로 저장되어 잘 출력되는 것을 확인할 수 있다.
그림으로 그려보면 아래와 같이 이진 트리가 생성된 것을 알 수 있다.

(Draw by @hyunminmax)
(그림 그려주셔서 감사합니다. 현민님 ^^)

_다른 수정__

5가 루트 노드로 정렬하고 싶다면 아래와 같이 코드를 작성하면 된다.

1) BinarySearchTree3.h

#ifndef __BINARY_SEARCH_TREE3_H__
#define __BINARY_SEARCH_TREE3_H__

#include "BinaryTree3.h"

typedef BTData	BSTData;

void BSTMakeAndInit(BTreeNode ** pRoot);
BSTData BSTGetNodeData(BTreeNode * bst);
void BSTInsert(BTreeNode ** pRoot, BSTData data);
BTreeNode * BSTSearch(BTreeNode * bst, BSTData target); 
BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target);
void BSTShowAll(BTreeNode * bst);

#endif

2) BinarySearchTree3.c

#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree3.h"
#include "BinarySearchTree3.h"
#include "AVLRebalance.h"

// 동일

void BSTInsert(BTreeNode ** pRoot, BSTData data)
{
	BTreeNode * pNode = NULL;    // parent node
	BTreeNode * cNode = *pRoot;    // current node
	BTreeNode * nNode = NULL;    // new node

	while(cNode != NULL)
	{
		if(data == GetData(cNode))
			return;

		pNode = cNode;

		if(GetData(cNode) > data)
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}
	
	nNode = MakeBTreeNode();
	SetData(nNode, data);

	if(pNode != NULL)
	{
		if(data < GetData(pNode))
			MakeLeftSubTree(pNode, nNode);
		else
			MakeRightSubTree(pNode, nNode);
	}
	else
	{
		*pRoot = nNode;
	}
	
	*pRoot = Rebalance(pRoot);
}
// 이하 동일

3) AVLTreeMain.c

#include <stdio.h>
#include "BinaryTree3.h"
#include "BinarySearchTree3.h"

int main(void)
{
	BTreeNode * avlRoot;
	BTreeNode * clNode;		// current left node
	BTreeNode * crNode;		// current right node
	BSTMakeAndInit(&avlRoot);

	BSTInsert(&avlRoot, 1);
	BSTInsert(&avlRoot, 2);
	BSTInsert(&avlRoot, 3);
	BSTInsert(&avlRoot, 4);
	BSTInsert(&avlRoot, 5);
	BSTInsert(&avlRoot, 6);
	BSTInsert(&avlRoot, 7);
	BSTInsert(&avlRoot, 8);
	BSTInsert(&avlRoot, 9);

	printf("Root Node: %d \n", GetData(avlRoot));

	clNode = GetLeftSubTree(avlRoot);
	crNode = GetRightSubTree(avlRoot);
	printf("Left 1: %d, Right 1: %d \n", GetData(clNode), GetData(crNode));

	clNode = GetLeftSubTree(clNode);
	crNode = GetRightSubTree(crNode);
	printf("Left 2: %d, Right 2: %d \n", GetData(clNode), GetData(crNode));

	clNode = GetLeftSubTree(clNode);
	crNode = GetRightSubTree(crNode);
	printf("Left 3: %d, Right 3: %d \n", GetData(clNode), GetData(crNode));

	clNode = GetLeftSubTree(clNode);
	crNode = GetRightSubTree(crNode);
	printf("Left 4: %d, Right 4: %d \n", GetData(clNode), GetData(crNode));
	return 0;
}

---

<Review>

마지막에 구현이 잘 되었는지 확인하는 실행파일에서 오류가 계속 나서 애를 먹었다.

> gcc .\AVLRebalance.c .\AVLRebalanceMain.c .\BinarySearchTree3.c .\BinaryTree3.c
.\BinarySearchTree3.c: In function 'BSTInsert':
.\BinarySearchTree3.c:36:13: warning: 'return' with a value, in function returning void
             ^~~~
.\BinarySearchTree3.c:17:6: note: declared here
 void BSTInsert(BTreeNode ** pRoot, BSTData data)
      ^~~~~~~~~
.\BinarySearchTree3.c:39:12: warning: 'return' with a value, in function returning void
     return *pRoot;
            ^~~~~~
.\BinarySearchTree3.c:17:6: note: declared here
 void BSTInsert(BTreeNode ** pRoot, BSTData data)
      ^~~~~~~~~

void로 반환 되는 형을 정해놨기 때문에 *pRoot가 안된다는 것이다.

위에 정리처럼 스터디를 하면서 4명의 지성을 모아 문제를 해결했다...

다행히 내 오타로 끝까지 작동이 안한거였지만 답답했다...ㅎㅎ
GPT한테도 물어봤을 때 고치지 못했던 부분이었기 때문이다...
아무튼! 잘 해결되서 다행이다...!

(이 날_12/3 밤 11시에 윤대통령님께서 비상 계엄을 선포해서 경과를 지켜보느라 잠을 4시간 밖에 못잤다 아주 화가 난다.)