Lab07 AVL Tree 코드

 

전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))
/* (((X) > (Y)) ? (X) : (Y)) 이 아니라
   ((X) > (Y)) ? (X) : (Y) 가 되어버리면 매크로함수가 내 맘대로 잘 작동을 안한다.. 겉에 괄호 하나 더 씌워주는게 중요하네. */

struct AVLNode;
typedef struct AVLNode* Position;
typedef struct AVLNode* AVLTree;
typedef int ElementType;

typedef struct AVLNode {
	ElementType element;
	AVLTree left, right;
	int height;
}AVLNode;

AVLTree Insert(ElementType x, AVLTree T);
AVLTree Delete(ElementType x, AVLTree T);
Position SingleRotateWithLeft(Position node);
Position SingleRotateWithRight(Position node);
Position DoubleRotateWithLeft(Position node);
Position DoubleRotateWithRight(Position node);
void PrintInorder(AVLTree T);
void DeleteTree(AVLTree T);

/* 트리의 높이를 계산하는 함수 */
int HeightCalc(AVLTree T) {
	if (T == NULL)
		return -1;
	return T->height;
}

/* 값이 최소인 노드를 찾는 함수 */
AVLTree FindMin(AVLTree T) {
	if (T->left == NULL)
		return T;
	else
		return FindMin(T->left);
}

/* 값이 x인 노드가 있는지 찾는 함수 */
int FindNode(ElementType x, AVLTree T) {
	AVLTree tmp = T;

	while (tmp != NULL) {
		if (x == tmp->element)
			return 1;
		else if (x < tmp->element)
			tmp = tmp->left;
		else
			tmp = tmp->right;
	}

	return 0;
}

/* 트리의 균형을 재조정하는 함수 */
AVLTree Balancing(AVLTree T) {
	/* 트리의 균형이 왼쪽으로 2 이상 높을 경우 */
	if (HeightCalc(T->left) - HeightCalc(T->right) >= 2) {
		if (HeightCalc(T->left->left) - HeightCalc(T->left->right) >= 1)
			T = SingleRotateWithLeft(T); // LL회전
		else
			T = DoubleRotateWithLeft(T); // LR회전
	}

	/* 트리의 균형이 오른쪽으로 2 이상 높을 경우 */
	if (HeightCalc(T->right) - HeightCalc(T->left) >= 2) {
		if (HeightCalc(T->right->right) - HeightCalc(T->right->left) >= 1)
			T = SingleRotateWithRight(T); // RR회전
		else
			T = DoubleRotateWithRight(T); // RL회전
	}

	T->height = MAX(HeightCalc(T->left), HeightCalc(T->right)) + 1; // 트리의 균형을 잡은 후 T의 높이 재설정
	return T;
}

/* 값이 x인 노드를 트리에 추가하는 함수 */
AVLTree Insert(ElementType x, AVLTree T) {
	if (T == NULL) {
		T = (AVLTree)malloc(sizeof(AVLNode));

		if (T == NULL) {
			printf("Out of Space!\n");
			return -1;
		}

		T->element = x;
		T->left = T->right = NULL;
		T->height = 0;
	}
	else if (x < T->element) {
		T->left = Insert(x, T->left);
		T = Balancing(T);
	}
	else if (x > T->element) {
		T->right = Insert(x, T->right);
		T = Balancing(T);
	}

	T->height = MAX(HeightCalc(T->left), HeightCalc(T->right)) + 1;
	return T;
}

/* 값이 x인 노드를 트리에서 삭제하는 함수 */
AVLTree Delete(ElementType x, AVLTree T) {
	AVLTree tmp;

	if (x < T->element) {
		T->left = Delete(x, T->left);
		T = Balancing(T);
	}
	else if (x > T->element) {
		T->right = Delete(x, T->right);
		T = Balancing(T);
	}
	
	/* 삭제할 노드를 찾았을 때 밑의 else문 실행 */
	else {
		if (T->left == NULL && T->right == NULL) { // 삭제할 노드가 자식이 하나도 없을 경우
			tmp = T;
			T = NULL;
		}
		else if (T->left == NULL || T->right == NULL) { // 삭제할 노드가 자식이 하나 있을 경우
			if (T->left == NULL) {
				tmp = T->right;
				T->element = tmp->element;
				T->right = Delete(T->element, T->right);
			}
			else {
				tmp = T->left;
				T->element = tmp->element;
				T->left = Delete(T->element, T->left);
			}
		}
		else { // 삭제할 노드가 두 개의 자식이 있을 경우
			tmp = FindMin(T->right);
			T->element = tmp->element;
			T->right = Delete(T->element, T->right);
		}
		free(tmp);
	}

	if (T)
		T->height = MAX(HeightCalc(T->left), HeightCalc(T->right)) + 1;
		
	return T;
}

/* LL회전 담당 함수 */
Position SingleRotateWithLeft(Position node) {
	Position tmp;

	tmp = node->left;
	node->left = tmp->right;
	tmp->right = node;

	tmp->height = MAX(HeightCalc(tmp->left), HeightCalc(tmp->right)) + 1;
	node->height = MAX(HeightCalc(node->left), HeightCalc(node->right)) + 1;

	return tmp;
}

/* RR회전 담당 함수 */
Position SingleRotateWithRight(Position node) {
	Position tmp;

	tmp = node->right;
	node->right = tmp->left;
	tmp->left = node;

	tmp->height = MAX(HeightCalc(tmp->left), HeightCalc(tmp->right)) + 1;
	node->height = MAX(HeightCalc(node->left), HeightCalc(node->right)) + 1;

	return tmp;
}

/* LR회전 담당 함수 */
Position DoubleRotateWithLeft(Position node) {
	Position tmp;

	tmp = node->left;
	tmp = SingleRotateWithRight(tmp);
	node = SingleRotateWithLeft(node);

	return node;
}

/* RL회전 담당 함수 */
Position DoubleRotateWithRight(Position node) {
	Position tmp;

	tmp = node->right;
	tmp = SingleRotateWithLeft(tmp);
	node = SingleRotateWithRight(node);

	return node;
}

/* Inorder 형식으로 트리의 노드들을 출력하는 함수 */
void PrintInorder(AVLTree T) {
	if (T == NULL)
		return;

	PrintInorder(T->left);
	
	printf("%d", T->element);
	printf("(%d) ", T->height);

	PrintInorder(T->right);
}

/* 트리를 완전 삭제하는 함수 */
void DeleteTree(AVLTree T) {
	if (T == NULL)
		return;

	DeleteTree(T->left);
	DeleteTree(T->right);
	free(T);
}

int main(void) {
	AVLTree Tree = NULL;
	char cv;
	int key;

	while (1) {
		scanf("%c", &cv);
		switch (cv) {
		case 'i':
			scanf("%d", &key);

			if (FindNode(key, Tree)) {
				printf("insertion error : %d is already in the tree!\n", key);
				PrintInorder(Tree);
				printf("\n");
			}
			else {
				Tree = Insert(key, Tree);
				PrintInorder(Tree);
				printf("\n");
			}
			break;
		case 'd':
			scanf("%d", &key);

			if (!(FindNode(key, Tree))) {
				printf("deletion error : %d is not in the tree!\n", key);
				PrintInorder(Tree);
				printf("\n");
			}
			else {
				Tree = Delete(key, Tree);

				PrintInorder(Tree);
				printf("\n");
			}
			break;
		case 'q':
			return 0;
		}
	}

	DeleteTree(Tree);
	return 0;
}