[C] AVL TREE (코드 보완)

1. AVL TREE 이전 게시물

2023.12.10 - [C/알고리즘] - [C] AVL TREE

[C] AVL TREE

1. AVL Tree : 자세한 설명은 아래 글 참조 2023.12.07 - [C++/자료구조] - [C++]AVL Tree [C++]AVL Tree 1. 균형이진탐색트리 (Adelson-Velskii&Landis) : 균형인수(Balance Factor:BF)를 이용하여 트리가 비균형 상태로 되면

growingupis.tistory.com

2. AVL TREE 코드보완

(1) bst delete node 함수

1) 공백 트리인 경우
: 그냥 return

if (*node == NULL) {
	printf("삭제할 노드가 존재하지 않습니다\n");
	return;
}

2) *node==NULL이 아닌 경우 TREENODE * cur= *node, TREENODE * pre = NULL;로 초기화한 후 , 해당 값을 찾을 때까지 두 노드포인터 순회시킨다

TREENODE* cur = *node;
TREENODE* pre=NULL;
while (cur->data != key) {
	pre = cur;
	if (cur->data < key) {
		cur = cur->right;
	}
	else {
		cur = cur->left;
	}
}

3) 이때, cur==NULL인 경우(해당 값이 존재하지 않는 경우)

: 그냥 return

if (cur == NULL) {
	printf("해당 노드는 존재하지 않습니다\n");
	return;
}

4) cur!=NULL인 경우 세 가지 케이스로 분류

⇒ 루트 노드의 주소를 바꾸어야하는 경우와 아닌 경우로 세부케이스를 또 나눈다

4-1) 삭제할 노드가 단말노드인 경우

pre!=NULL인 경우
pre==NULL인 경우(루트 노드의 주소를 바꾸어야 하는 경우)

if (cur->left == NULL && cur->right == NULL) {
	if (pre != NULL) {
		if (pre->right == cur) {
			pre->right = NULL;
		}
		else {
			pre->left = NULL;
		}
	}
	else {
		*node = NULL;
	}
	free(cur);
	cur = NULL;
}

4-2) 삭제할 노드의 자식노드가 2개인 경우

: 이 경우엔 삭제노드를 진짜 메모리상에서 삭제하는 것이 아닌 후계자의 노드의 데이터를 복사해주고 후계자의 노드를 삭제하는 것이기에 루트 노드의 주소를 바꾸어야 하는 경우는 존재하지 않는다

	else if (cur->left != NULL && cur->right!=NULL) {
		TREENODE* succ = cur;
		TREENODE* succ_parent = cur;
		succ = succ->right;
		while (succ->left != NULL) {
			succ_parent = succ;
			succ = succ->left;
		}
		if (succ_parent->right == succ) {
			cur->data = succ->data;
			succ_parent->right = succ->right;
			free(cur);
			cur = NULL;
		}
		else {
			cur->data = succ->data;
			succ_parent->left = succ->right;
			free(cur);
			cur = NULL;
		}
	}

4-3) 삭제할 노드의 자식노드가 1개인 경우

pre!=NULL인 경우
pre==NULL인 경우(루트 노드의 주소를 바꾸어야 하는 경우)

else {
	TREENODE* child;
	if (cur->left == NULL) {
		child = cur->right;
	}
	else {
		child = cur->left;
	}
	if (pre != NULL) {
		
		if (pre->left == NULL) {
			pre->right = child;
		}
		else {
			pre->left = child;
		}
	}
	else {
		*node = child;
	}
}

(2) avl delete node 함수

1) *root==NULL인 경우 ( 삭제할 노드가 존재하지않는 경우)

: 그냥 return

if (*root == NULL) {
	printf("삭제할 노드가 존재하지 않습니다\n");
	return;
}

2) *root!=NULL인 경우

2-1) (*root)->data== key인 경우 (삭제할 노드를 찾은 경우)

: bst delete node함수 수행

: 위의 함수를 수행하고 나면 삭제 노드에는 삭제 노드의 자식노드가 존재할 것 ( 없는 경우도 존재)

⇒ 그 노드부터 다시 rebalancing을 수행해야하기에 (*root)= rebalance(root); 함수 수행

if ((*root)->data == key) {
	BST_DELETE_NODE(root, key);
	(*root) = rebalance(root);
}

2-2) (*root)->data < key인 경우

: 해당 노드의 오른쪽 노드를 전달하며 avl delete node함수 수행

else if ((*root)->data < key) {
	AVL_DELETE_NODE(&((*root)->right), key);
	(*root) = rebalance(root);
}

2-3) (*root)->data > key인 경우

: 해당 노드의 왼쪽 노드를 전달하며 avl delete node함수 수행

else if ((*root)->data > key) {
	AVL_DELETE_NODE(&((*root)->left), key);
	(*root) = rebalance(root);
}

⇒ 이때, 2-2) 2-3) 수행을 통해 삭제 노드를 삭제하고 나면 삭제노드부터 루트노드까지 다시 거슬러 올라가며 rebalancing과정이 필요하기 때문에 해당 노드에 대해 (*root)= rebalance(root); 함수 수행

avl.h

#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <memory.h>
#include <stdbool.h>
#define TRUE 1
#define FALSE 0
#define ONLY_REBALNACING true //리밸런싱만 해라
#define DELETE false 

typedef int NodeData;
#define MAX(a,b) a>b?a:b

typedef struct _NODEMAP_ {
	int flag;
	NodeData data;
}NODEMAP;

typedef struct _TREE_NODE_ {
	NodeData data;
	struct _TREE_NODE_* left;
	struct _TREE_NODE_* right;
}TREENODE;


int getMax(int a, int b) {
	return ((a > b) ? a : b);
}

int getHeight(TREENODE* root) {
	if (root == NULL) {
		return 0;
	}
	else {
		return 1 +max(getHeight(root->left), getHeight(root->right));
	}
}

int getBF(TREENODE* root) {
	if (root != NULL) {
		return getHeight(root->left) - getHeight(root->right);
	}
}

TREENODE* RR_TYPE(TREENODE* root) {
	TREENODE* child = root->right;
	root->right = child->left;
	child->left = root;

	return child;
}


TREENODE* LL_TYPE(TREENODE* root) {
	TREENODE* child = root->left;
	root->left = child->right;
	child->right = root;

	return child;
}

TREENODE* LR_TYPE(TREENODE* root) {
	TREENODE* child = root->left;
	root->left = RR_TYPE(child);
	return LL_TYPE(root);
}

TREENODE* RL_TYPE(TREENODE* root) {
	TREENODE* child = root->right;
	root->right = LL_TYPE(child);
	return RR_TYPE(root);
}

TREENODE* rebalance(TREENODE** root) {
	int BF = getBF(*root);
	if (BF == 2) {
		if (getBF((*root)->left) >= 0) {
			//LL유형
			*root = LL_TYPE(*root);
		}
		else {
			*root = LR_TYPE(*root);
		}
	}
	else if (BF == -2) {
		if (getBF((*root)->right)<=0) {
			//RR유형
			*root = RR_TYPE(*root);
		}
		else {
			*root = RL_TYPE(*root);
		}
	}

	return *root;
}



TREENODE* AVL_INSERT_NODE(TREENODE** root, int key) {
	
	if (*root == NULL) {
		*root = (TREENODE*)calloc(1, sizeof(TREENODE));
		assert(*root != NULL);
		(*root)->data = key;
		return *root;
	}
	else if ((*root)->data < key) {
		(*root)->right = AVL_INSERT_NODE(&((*root)->right), key);
		*root = rebalance(root);
	}
	else if ((*root)->data > key) {
		(*root)->left = AVL_INSERT_NODE(&((*root)->left), key);
		*root = rebalance(root);
	}
	else if ((*root)->data == key) {
		printf("\n해당 키는 이미 존재하기에 삽입할 수 없습니다\n");
		return;
	}

	return *root;
}

int countNode(TREENODE* node) {
	if (node == NULL) return 0;
	return 1 + countNode(node->left) + countNode(node->right);
}
void printGivenLevel(TREENODE* root, int level, NODEMAP* map, int pos)
{
	if (root == NULL)
	{
		return;
	}
	if (level == 1) {
		map[pos].data = root->data;
		map[pos].flag = TRUE;
	}
	else if (level > 1)
	{
		printGivenLevel(root->left, level - 1, map, pos * 2);
		printGivenLevel(root->right, level - 1, map, pos * 2 + 1);
	}
}

void showTree(TREENODE* node)
{
	int height = 0;
	int numOfNodes = 0;
	NODEMAP* treeArray = NULL;
	char** square = NULL;
	static int pos = 0;
	int cnt_i;
	int cnt_j;
	int position;
	int start, term, index;

	height = getHeight(node);
	if (height != 0) {
		numOfNodes = (1 << height);
	}
	treeArray = (NODEMAP*)calloc(numOfNodes, sizeof(NODEMAP));
	assert(treeArray != NULL);

	square = (char**)calloc(height, sizeof(char*));
	for (cnt_i = 0; cnt_i < height; cnt_i++)
	{
		square[cnt_i] = (char*)calloc(numOfNodes, sizeof(char));
		memset(square[cnt_i], '.', numOfNodes);
	}


	pos = 1;
	for (cnt_i = 1; cnt_i <= height; cnt_i++) {
		printGivenLevel(node, cnt_i, treeArray, pos);
	}


	for (cnt_i = 1; cnt_i <= numOfNodes; cnt_i++)
	{
		treeArray[cnt_i - 1] = treeArray[cnt_i];
	}

	pos = 0;
	start = (1 << (height - 1)) - 1;
	term = (1 << (height));
	index = (1 << (height - 2));
	for (cnt_i = 0; cnt_i < height; cnt_i++)
	{
		for (cnt_j = start; cnt_j < numOfNodes; cnt_j += term)
		{
			if (treeArray[pos].flag == TRUE) {
				if (treeArray[pos].data >= 0 && treeArray[pos].data <= 9) {
					square[cnt_i][cnt_j] = (treeArray[pos].data + '0');
				}
				else {
					square[cnt_i][cnt_j] = (treeArray[pos].data);
				}
			}
			else {
				square[cnt_i][cnt_j] = '.';
			}
			pos += 1;
		}
		term >>= 1;
		start -= index;
		index >>= 1;
	}

	printf("\n");
	for (cnt_i = 0; cnt_i < height; cnt_i++)
	{
		for (cnt_j = 0; cnt_j < numOfNodes; cnt_j++)
		{
			printf("%c", square[cnt_i][cnt_j]);
		}
		printf("\n");
	}

	if (treeArray != NULL) {
		free(treeArray);
	}
	if (square != NULL)
	{
		for (cnt_i = 0; cnt_i < height; cnt_i++)
		{
			if (square[cnt_i] != NULL)
			{
				free(square[cnt_i]);
			}
		}
		free(square);
	}
}


void displayInorder(TREENODE* root) {
	if (root != NULL) {
		displayInorder(root->left);
		printf("%d ", root->data);
		displayInorder(root->right);
	}
}

void BST_DELETE_NODE(TREENODE** node, int key) {
	if (*node == NULL) {
		printf("삭제할 노드가 존재하지 않습니다\n");
		return;
	}
	else {
		TREENODE* cur = *node;
		TREENODE* pre=NULL;
		while (cur->data != key) {
			pre = cur;
			if (cur->data < key) {
				cur = cur->right;
			}
			else {
				cur = cur->left;
			}
		}
		if (cur == NULL) {
			printf("해당 노드는 존재하지 않습니다\n");
			return;
		}
		else {
			if (cur->left == NULL && cur->right == NULL) {
				if (pre != NULL) {
					if (pre->right == cur) {
						pre->right = NULL;
					}
					else {
						pre->left = NULL;
					}
				}
				else {
					*node = NULL;
				}
				free(cur);
				cur = NULL;
			}
			else if (cur->left != NULL && cur->right!=NULL) {
				TREENODE* succ = cur;
				TREENODE* succ_parent = cur;
				succ = succ->right;
				while (succ->left != NULL) {
					succ_parent = succ;
					succ = succ->left;
				}
				if (succ_parent->right == succ) {
					cur->data = succ->data;
					succ_parent->right = succ->right;
					free(cur);
					cur = NULL;
				}
				else {
					cur->data = succ->data;
					succ_parent->left = succ->right;
					free(cur);
					cur = NULL;
				}
			}
			else {
				TREENODE* child;
				if (cur->left == NULL) {
					child = cur->right;
				}
				else {
					child = cur->left;
				}
				if (pre != NULL) {
					
					if (pre->left == NULL) {
						pre->right = child;
					}
					else {
						pre->left = child;
					}
				}
				else {
					*node = child;
				}
			}
		}
	}
}

void AVL_DELETE_NODE(TREENODE** root, int key) {
	if (*root == NULL) {
		printf("삭제할 노드가 존재하지 않습니다\n");
		return;
	}
	
	if ((*root)->data == key) {
		BST_DELETE_NODE(root, key);
		(*root) = rebalance(root);
	}
	else if ((*root)->data < key) {
		AVL_DELETE_NODE(&((*root)->right), key);
		(*root) = rebalance(root);
	}
	else if ((*root)->data > key) {
		AVL_DELETE_NODE(&((*root)->left), key);
		(*root) = rebalance(root);
	}

}

void BST_INSERT_NODE(TREENODE** root, int key) {
	//공백 트리인 경우
	TREENODE* newNode = (TREENODE*)calloc(1, sizeof(TREENODE));
	assert(newNode != NULL);
	newNode->data = key;
	if (*root == NULL) {
		*root = newNode;
	}
	else {
		TREENODE* curNode = *root;
		TREENODE* preNode = NULL;
		while (curNode != NULL) {
			preNode = curNode;
			if (curNode->data < key) {
				curNode = curNode->right;
			}
			else if(curNode->data>key){
				curNode = curNode->left;
			}
			else if (curNode->data == key) {
				printf("\n해당 노드는 이미 존재하기때문에 삽입할 수 없습니다\n");
				return;
			}
		}
		if (preNode->right == NULL) {
			preNode->right = newNode;
		}
		else {
			preNode->left = newNode;
		}
	}
}

main.c

#include "avl.h"

int main() {

	int i;
	int data;
	TREENODE* root_AVL = NULL;
	TREENODE* root_BST = NULL;

	printf("\n*************AVL트리 삽입******************\n");
	for (i = 0; i < 8; i++) {
		AVL_INSERT_NODE(&root_AVL, i);
		printf("\nInsert %d\n", i);
		showTree(root_AVL);
		getchar();
	}
	printf("\n ************AVL트리 출력*****************\n\n");
	displayInorder(root_AVL);

	printf("\n *************AVL트리 삭제***************\n\n");
	for (i = 0; i < 8; i++) {



		AVL_DELETE_NODE(&root_AVL, i);
		printf("\nDelete %d\n", i);
		showTree(root_AVL);
		getchar();
	}
	printf("\n ************AVL트리 출력*****************\n\n");
	displayInorder(root_AVL);
	



	printf("\n **************BST트리 삽입 **************\n\n");
	for (i = 0; i < 8; i++) {
		BST_INSERT_NODE(&root_BST, i);
		printf("\nInsert %d\n", i);
		showTree(root_BST);
		getchar();
	}
	printf("\n ************BST트리 출력****************\n\n");
	displayInorder(root_BST);

	printf("\n *************BST트리 삭제***************\n\n");
	for (i = 0; i < 8; i++) {
		BST_DELETE_NODE(&root_BST, i);
		printf("\nDelete %d\n", i);
		showTree(root_BST);
		getchar();
	}
	printf("\n ************BST트리 출력*****************\n\n");
	displayInorder(root_BST);







	getchar();
	return 0;
}

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

[C] Prim Algorithm 코드 보완 (0)	2024.02.13
[C] 정렬 알고리즘 (0)	2024.02.12
[C] 이진 탐색 트리 (BST) (0)	2024.02.08
[C] 이중 연결 리스트 (0)	2024.02.06
[C] AVL TREE (0)	2023.12.10

이정표

[C] AVL TREE (코드 보완)

1. AVL TREE 이전 게시물

2. AVL TREE 코드보완

(1) bst delete node 함수

(2) avl delete node 함수

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

티스토리툴바

[C] AVL TREE (코드 보완)

1. AVL TREE 이전 게시물

2. AVL TREE 코드보완

(1) bst delete node 함수

(2) avl delete node 함수

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

관련글

티스토리툴바