#include <stdio.h>
#include <stdlib.h>
typedef struct _bTreeNode{
int data;
struct _bTreeNode * left;
struct _bTreeNode * right;
} BTreeNode;
BTreeNode * Rebalance(BTreeNode ** pRoot);
////////////////////////// 이진트리 시작
BTreeNode * MakeBTreeNode(void)
{
BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));
nd->left = NULL;
nd->right = NULL;
return nd;
}
int GetData(BTreeNode * bt)
{
return bt->data;
}
void SetData(BTreeNode * bt, int data)
{
bt->data = data;
}
BTreeNode * GetLeftSubTree(BTreeNode * bt)
{
return bt->left;
}
BTreeNode * GetRightSubTree(BTreeNode * bt)
{
return bt->right;
}
void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
if(main->left != NULL)
free(main->left);
main->left = sub;
}
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
if(main->right != NULL)
free(main->right);
main->right = sub;
}
void PreorderTraverse(BTreeNode * bt)
{
if(bt == NULL)
return;
printf("%d ", bt->data);
PreorderTraverse(bt->left);
PreorderTraverse(bt->right);
}
void InorderTraverse(BTreeNode * bt)
{
if(bt == NULL)
return;
InorderTraverse(bt->left);
printf("%d ", bt->data);
InorderTraverse(bt->right);
}
void PostorderTraverse(BTreeNode * bt)
{
if(bt == NULL)
return;
PostorderTraverse(bt->left);
PostorderTraverse(bt->right);
printf("%d ", bt->data);
}
BTreeNode * RemoveLeftSubTree(BTreeNode * bt)
{
BTreeNode * delNode;
if(bt != NULL) {
delNode = bt->left;
bt->left = NULL;
}
return delNode;
}
BTreeNode * RemoveRightSubTree(BTreeNode * bt)
{
BTreeNode * delNode;
if(bt != NULL) {
delNode = bt->right;
bt->right = NULL;
}
return delNode;
}
void ChangeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
main->left = sub;
}
void ChangeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
main->right = sub;
}
////////////////////////// 이진트리 끝
////////////////////////// 이진 탐색 트리 시작
void BSTMakeAndInit(BTreeNode ** pRoot)
{
*pRoot = NULL;
}
int BSTGetNodeData(BTreeNode * bst)
{
return GetData(bst);
}
BTreeNode * BSTInsert(BTreeNode ** pRoot, int 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, int target)
{
BTreeNode * cNode = bst; // current node
int 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, int 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 = cNode; // 삭제 대상을 dNode가 가리키게 한다.
// 첫 번째 경우: 삭제할 노드가 단말 노드인 경우
if(GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL)
{
if(GetLeftSubTree(pNode) == dNode)
RemoveLeftSubTree(pNode);
else
RemoveRightSubTree(pNode);
}
// 두 번째 경우: 하나의 자식 노드를 갖는 경우
else if(GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL)
{
BTreeNode * dcNode; // delete node의 자식 노드
if(GetLeftSubTree(dNode) != NULL)
dcNode = GetLeftSubTree(dNode);
else
dcNode = GetRightSubTree(dNode);
if(GetLeftSubTree(pNode) == dNode)
ChangeLeftSubTree(pNode, dcNode);
else
ChangeRightSubTree(pNode, dcNode);
}
// 세 번째 경우: 두 개의 자식 노드를 모두 갖는 경우
else
{
BTreeNode * mNode = GetRightSubTree(dNode); // mininum node
BTreeNode * mpNode = dNode; // mininum node의 부모 노드
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);
*pRoot = Rebalance(pRoot); // 노드 제거 후 리밸런싱!
return dNode;
}
void ShowIntData(int data)
{
printf("%d ", data);
}
void BSTShowAll(BTreeNode * bst)
{
InorderTraverse(bst);
}
////////////////////////// 이진 탐색 트리 끝
////////////////////////// AVL 균형 잡기 시작
// LL 회전
BTreeNode * RotateLL(BTreeNode * bst)
{
BTreeNode * pNode;
BTreeNode * cNode;
pNode = bst;
cNode = GetLeftSubTree(pNode);
ChangeLeftSubTree(pNode, GetRightSubTree(cNode));
ChangeRightSubTree(cNode, pNode);
return cNode;
}
// RR 회전
BTreeNode * RotateRR(BTreeNode * bst)
{
BTreeNode * pNode;
BTreeNode * cNode;
pNode = bst;
cNode = GetRightSubTree(pNode);
ChangeRightSubTree(pNode, GetLeftSubTree(cNode));
ChangeLeftSubTree(cNode, pNode);
return cNode;
}
// RL 회전
BTreeNode * RotateRL(BTreeNode * bst)
{
BTreeNode * pNode;
BTreeNode * cNode;
pNode = bst;
cNode = GetRightSubTree(pNode);
ChangeRightSubTree(pNode, RotateLL(cNode)); // 부분적 LL 회전
return RotateRR(pNode); // RR 회전
}
// LR 회전
BTreeNode * RotateLR(BTreeNode * bst)
{
BTreeNode * pNode;
BTreeNode * cNode;
pNode = bst;
cNode = GetLeftSubTree(pNode);
ChangeLeftSubTree(pNode, RotateRR(cNode)); // 부분적 RR 회전
return RotateLL(pNode); // LL 회전
}
// 트리의 높이를 계산하여 반환
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;
}
// 트리의 균형을 잡는다.
BTreeNode * Rebalance(BTreeNode ** pRoot)
{
int hDiff = GetHeightDiff(*pRoot);
if(hDiff > 1) // 왼쪽 서브 트리 방향으로 높이가 2 이상 크다면
{
if(GetHeightDiff(GetLeftSubTree(*pRoot)) > 0)
*pRoot = RotateLL(*pRoot);
else
*pRoot = RotateLR(*pRoot);
}
if(hDiff < -1) // 오른쪽 서브 트리 방향으로 2 이상 크다면
{
if(GetHeightDiff(GetRightSubTree(*pRoot)) < 0)
*pRoot = RotateRR(*pRoot);
else
*pRoot = RotateRL(*pRoot);
}
return *pRoot;
}
////////////////////////// AVL 균형 잡기 끝
///////////////////////// 메인 함수 시작
int main(void)
{
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("루트 노드: %d \n", GetData(avlRoot)); //4
clNode = GetLeftSubTree(avlRoot); //2, 루트 4의 왼편
crNode = GetRightSubTree(avlRoot); //6, 루트 4의 오른편
printf("%d, %d \n", GetData(clNode), GetData(crNode));
clNode2 = GetLeftSubTree(clNode); //1, 2의 왼편
crNode2 = GetRightSubTree(clNode); //3, 2의 오른편
printf("%d, %d \n", GetData(clNode2), GetData(crNode2));
clNode2 = GetLeftSubTree(crNode); //5, 3의 왼편
crNode2 = GetRightSubTree(crNode); //8, 3의 오른편
printf("%d, %d \n", GetData(clNode2), GetData(crNode2));
clNode3 = GetLeftSubTree(crNode2); //7, 8의 왼편
crNode3 = GetRightSubTree(crNode2); //9, 8의 오른편
printf("%d, %d \n", GetData(clNode3), GetData(crNode3));
return 0;
}
