본문 바로가기
C/알고리즘

[C] AVL TREE

by 덤더리덤떰 2023. 12. 10.

1. AVL Tree

: 자세한 설명은 아래 글 참조 

2023.12.07 - [C++/자료구조] - [C++]AVL Tree

 

[C++]AVL Tree

1. 균형이진탐색트리 (Adelson-Velskii&Landis) : 균형인수(Balance Factor:BF)를 이용하여 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태를 유지하도록 하는 트리 : 평균, 최선, 최악 시

growingupis.tistory.com

 

2. 구현

2-1. AVL 트리 노드 삭제

(1) 이때 trim 함수에서 루트노드가 바로 삭제노드인 예외 케이스를 고려하여 아래 조건문 추가

if (((*node)->data == item) && *node == avl->root) {
	BST_Delete(*node, item);
	*node = rebalance(node);
	return;
}

→ BST delete 함수를 통해 루트노드 삭제를 하고 난 후 rebalancing 과정을 거치고 더이상 재귀문을 돌 필요가 없기에 바로 return

 

(2) BST_Delete 함수에서 루트노드가 삭제노드인 경우를 고려하여 매개변수를 TREE_NODE ** (이중포인터)로 설정

→ 이때 trim 함수는 항상 어떤 노드의 자식노드가 삭제노드라 인자가 그 어떤 노드인 경우에 대해 BST_Delete 함수 실행

→ 루트노드를 삭제하는 경우인지 판별하기위해 preNode를 NULL로 설정

→ BST_Delete 함수는 그 어떤 노드부터 탐색을 시작하므로 BST_Delete 내 while문을 돌고 난 후의 preNode는 NULL이 아님

→ 하지만 예외로 루트노드가 삭제노드인 경우 preNode는 NULL

void BST_Delete(TREE_NODE** node, int item)
{
	TREE_NODE* curNode = *node;
	TREE_NODE* preNode = NULL;

	while (curNode != NULL) {
		if (curNode->data == item) {
			break;
		}
		preNode = curNode;
		if (curNode->data < item) {
			curNode = curNode->right;
		}
		else if (curNode->data > item) {
			curNode = curNode->left;
		}
	}
	//이때, trim함수는 항상 어떤 노드의 자식노드가 item이라 삭제하는 경우라서 어떤 노드부터 탐색을 시작하므로 preNode는 무조건 NULL이 아님
	//단, 예외 : 루트노드가 삭제노드인 경우 preNode는 NULL

	if (curNode->left == NULL && curNode->right == NULL) {
		if (preNode->right == curNode) {
			preNode->right = NULL;
		}
		else if (preNode->left == curNode) {
			preNode->left = NULL;
		}
		free(curNode);
		curNode = NULL;
		
	}
	else if (curNode->left != NULL && curNode->right != NULL) {
		TREE_NODE* succ = curNode;
		TREE_NODE* pre_succ = curNode;
		succ = succ->left;
		while (succ->right != NULL) {
			succ = succ->right;
		}
		curNode->data = succ->data;
		if (pre_succ->left == succ) {
			pre_succ->left = succ->left;
		}
		else {
			pre_succ->right = succ->left;
		}
		free(succ);
		succ = NULL;
	}
	else {
		TREE_NODE* child = NULL;
		if (curNode->left) {
			child = curNode->left;
		}
		else if (curNode->right) {
			child = curNode->right;
		}
		if (preNode == NULL) {
			*node = child;
		}
		else {
			if (preNode->left == curNode) {
				preNode->left = child;
			}
			else {
				preNode->right = child;
			}
		}
		free(curNode);
		curNode = NULL;

	}

}

 

 

2-2. 전체 소스 코드 

Tree.h
#pragma once
#include <stdbool.h>

typedef struct _TREE_NODE_ {
	int data;
	struct _NODE_* left;
	struct _NODE_* right;
}TREE_NODE;

typedef struct _AVL_TREE_ {
	TREE_NODE* root;
}AVL_TREE;

int getHeight(TREE_NODE* node);
int getBF(TREE_NODE* node);
AVL_TREE* Make_AVL_TREE();
TREE_NODE* grow(TREE_NODE ** node, int item,AVL_TREE * avl);
void BST_Delete(TREE_NODE** node, int item);
bool trim(TREE_NODE** node, int item, AVL_TREE* avl);
TREE_NODE* rebalance(TREE_NODE ** node);
TREE_NODE * type_LL(TREE_NODE * node);
TREE_NODE* type_RR(TREE_NODE* node);
TREE_NODE* type_LR(TREE_NODE* node);
TREE_NODE* type_RL(TREE_NODE* node);
void traverse(TREE_NODE* node);

TREE_NODE* insert(TREE_NODE** node, int item); //BST연산​
Tree.c
#include "Tree.h"
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#define MAX(a,b) (((a)>(b))?(a):(b))

int getHeight(TREE_NODE* node)
{
	if (node == NULL) {
		return 0;
	}
	else {
		return MAX(getHeight(node->left), getHeight(node->right)) + 1;
	}
}

int getBF(TREE_NODE* node)
{
	return getHeight(node->left) - getHeight(node->right);
}

AVL_TREE* Make_AVL_TREE() {
	AVL_TREE* avl = (AVL_TREE*)calloc(1, sizeof(AVL_TREE));
	assert(avl != NULL);

	return avl;
}

TREE_NODE* grow(TREE_NODE** node, int item, AVL_TREE * avl)
{
	if ( avl->root==NULL) {
		TREE_NODE* newNode = (TREE_NODE*)calloc(1, sizeof(TREE_NODE));
		assert(newNode != NULL);
		newNode->data = item;
		avl->root = newNode;
		return;
	}
	if (*node == NULL) {
		TREE_NODE* newNode = (TREE_NODE*)calloc(1, sizeof(TREE_NODE));
		assert(newNode != NULL);
		newNode->data = item;
		return newNode;
	}
	if ((*node)->data < item) {
		(*node)->right = grow(&((*node)->right), item,avl);
		*node = rebalance(node);
	}
	else if ((*node)->data > item) {
		(*node)->left = grow(&((*node)->left), item,avl);
		*node = rebalance(node);
	}

	return *node;

}

void BST_Delete(TREE_NODE** node, int item)
{
	TREE_NODE* curNode = *node;
	TREE_NODE* preNode = NULL;

	while (curNode != NULL) {
		if (curNode->data == item) {
			break;
		}
		preNode = curNode;
		if (curNode->data < item) {
			curNode = curNode->right;
		}
		else if (curNode->data > item) {
			curNode = curNode->left;
		}
	}
	//이때, trim함수는 항상 어떤 노드의 자식노드가 item이라 삭제하는 경우라서 어떤 노드부터 탐색을 시작하므로 preNode는 무조건 NULL이 아님
	//단, 예외 : 루트노드가 삭제노드인 경우 preNode는 NULL

	if (curNode->left == NULL && curNode->right == NULL) {
		if (preNode->right == curNode) {
			preNode->right = NULL;
		}
		else if (preNode->left == curNode) {
			preNode->left = NULL;
		}
		free(curNode);
		curNode = NULL;
		
	}
	else if (curNode->left != NULL && curNode->right != NULL) {
		TREE_NODE* succ = curNode;
		TREE_NODE* pre_succ = curNode;
		succ = succ->left;
		while (succ->right != NULL) {
			succ = succ->right;
		}
		curNode->data = succ->data;
		if (pre_succ->left == succ) {
			pre_succ->left = succ->left;
		}
		else {
			pre_succ->right = succ->left;
		}
		free(succ);
		succ = NULL;
	}
	else {
		TREE_NODE* child = NULL;
		if (curNode->left) {
			child = curNode->left;
		}
		else if (curNode->right) {
			child = curNode->right;
		}
		if (preNode == NULL) {
			*node = child;
		}
		else {
			if (preNode->left == curNode) {
				preNode->left = child;
			}
			else {
				preNode->right = child;
			}
		}
		free(curNode);
		curNode = NULL;

	}

}

bool trim(TREE_NODE** node, int item,AVL_TREE * avl)
{	//루트노드를 삭제하는 경우
	if (((*node)->data == item) && *node == avl->root) {
		BST_Delete(*node, item);
		*node = rebalance(node);
		return;
	}
	if ((*node)->data == item) {
		return true;
	}
	if ((*node)->data < item) {
		if(trim(&((*node)->right), item, avl)==true){
			BST_Delete(node, item);
		}
	}
	else if ((*node)->data > item) {
		if (trim(&((*node)->left), item,avl) == true) {
			BST_Delete(node, item);
		}
	}

	*node = rebalance(node);

	return false;
}

TREE_NODE* rebalance(TREE_NODE** node)
{
	TREE_NODE* this = *node;
	int BF = getBF(this);
	if (BF == 2) {
		//LL유형
		if (getBF(this->left)>=0) {
			*node = type_LL(*node);
		}
		//LR유형
		else {
			*node = type_LR(*node);
		}
	}
	else if (BF == -2) {
		//RR유형
		if (getBF(this->right) <= 0) {
			*node = type_RR(*node);
		}
		//RL유형
		else {
			*node = type_RL(*node);
		}
	}

	return *node;
	
}

TREE_NODE* type_LL(TREE_NODE* node)
{
	TREE_NODE* child = node->left;
	node->left = child->right;
	child->right = node;

	return child;
}

TREE_NODE* type_RR(TREE_NODE* node)
{
	TREE_NODE* child = node->right;
	node->right = child->left;
	child->left = node;

	return child;
}

TREE_NODE* type_LR(TREE_NODE* node)
{
	TREE_NODE* child = node->left;
	node->left = type_RR(child);

	return type_LL(node);
}

TREE_NODE* type_RL(TREE_NODE* node)
{
	TREE_NODE* child = node->right;
	node->right = type_LL(child);

	return type_RR(node);
}

void traverse(TREE_NODE* node) {
	if (node == NULL) {
		return;
	}

	printf("%d ", node->data);
	traverse(node->left);
	traverse(node->right);
}


TREE_NODE* insert(TREE_NODE** node, int item) {
	if (*node == NULL) {
		TREE_NODE* newNode = (TREE_NODE*)calloc(1, sizeof(TREE_NODE));
		assert(newNode != NULL);
		newNode->data = item;
		return newNode;
	}
	if ((*node)->data < item) {
		(*node)->right = insert(&((*node)->right), item);
	}
	else if ((*node)->data > item) {
		(*node)->left = insert(&((*node)->left), item);
	}

	return *node;
}​

 

main.c
#define _CRT_SECURE_NO_WARNINGS
#include "Tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>




int main() {
	TREE_NODE* BST_root = (TREE_NODE*)calloc(1, sizeof(TREE_NODE));
	assert(BST_root != NULL);
	BST_root->data = 50;
	insert(&BST_root, 20);
	insert(&BST_root, 60);
	insert(&BST_root, 10);
	insert(&BST_root, 8);
	insert(&BST_root, 15);
	insert(&BST_root, 32);
	insert(&BST_root, 46);
	insert(&BST_root, 11);
	insert(&BST_root, 48);
	
	///////////////////////////////////////////////////
	AVL_TREE* avl = Make_AVL_TREE();
	printf("         :\t\t\t\t\t  :\n");
	printf("         :\t\t\t\t\t  :\n");
	printf("AVL 트리 노드 삽입 중\t\t\t BST 트리 노드 삽입 중\n");
	printf("         :\t\t\t\t\t  :\n");
	printf("         :\t\t\t\t\t  :\n");
	grow(&(avl->root), 50,avl);
	grow(&(avl->root), 20, avl);
	grow(&(avl->root), 60, avl);
	grow(&(avl->root), 10, avl);
	grow(&(avl->root), 8, avl);
	grow(&(avl->root), 15, avl);
	grow(&(avl->root), 32, avl);
	grow(&(avl->root), 46, avl);
	grow(&(avl->root), 11, avl);
	grow(&(avl->root), 48, avl);

	printf("\n\n[AVL 트리 출력]\t\t\t\t [BST 트리 출력]\n");
	traverse(avl->root);
	printf("\t\t ");
	traverse(BST_root);

	printf("\n");

	printf("\n\n[AVL 트리 원소 중 60 삭제]\t\t [BST 트리 원소 중 60 삭제]\n");
	trim(&(avl->root), 60,avl);
	BST_Delete(&BST_root, 60);
	traverse(avl->root);
	printf("\t\t ");
	traverse(BST_root);


	printf("\n\n[AVL 트리 원소 중 32 삭제]\t\t [BST 트리 원소 중 32 삭제]\n");
	trim(&(avl->root), 32,avl);
	BST_Delete(&BST_root, 32);
	traverse(avl->root);
	printf("\t\t\t ");
	traverse(BST_root);


	getchar();
	return 0;
}​

 

##공부하면서 알게된 것

: 컴퓨터에서 함수는 stack 구조이다. 따라서 함수 미리 선언 안되어있는데 함수 정의보다 먼저 사용하면 오류 C2040 'function': 'TreeNode (TreeNode )'의 간접 참조 수준이 'int ()'과(와) 다릅니다.' 와 같은 오류가 뜬다.

: 정의도 되지 않은 함수는 컴파일러는 int()형을 반환했고, 나중에 정의를 하니 (원래 목적이였던)포인터 타입 반환형이랑 충돌해서 오류 발생 

'C > 알고리즘' 카테고리의 다른 글

[C] 이진 탐색 트리 (BST)  (0) 2024.02.08
[C] 이중 연결 리스트  (0) 2024.02.06
[C] Prim Alogrithm  (0) 2023.10.06
[C]수식 트리 - Evaluate Tree  (0) 2023.09.22
[C]트리 레벨 순회 - Level Order Traverse  (0) 2023.09.22

관련글

티스토리툴바