Tree 02. AVL Tree(Adel'son-Vel'skii & Landis, AVL 트리)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef AVL_H
# define AVL_H

#include <stdio.h>
#include <stdlib.h>
#define	MAX(x,y) (((x) < (y)) ? (y):(x))

#define ABS(x) (((x) < 0) ? (-(x)) : (x))

typedef	struct	s_avl{
	int key;
	int height;
	struct s_avl *parent;
	struct s_avl *left;
	struct s_avl *right;
}				t_avl;

void	addHeight(t_avl **avl, t_avl *nil);
t_avl	*makeAVL(t_avl **avl, t_avl *NIL);

#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include "avl.h"

void	initNode(t_avl *newnode,t_avl *nil, int key)
{
	newnode->parent = nil;
	newnode->left = nil;
	newnode->right = nil;
	newnode->key = key;
	newnode->height = 0;
}

void	inOrdertoPrint(t_avl *avl, t_avl *nil)
{
	if (avl != nil)
	{
		inOrdertoPrint(avl->left, nil);
		printf("height:%d, ", avl->height);
		printf("key: %d\n", avl->key);
		inOrdertoPrint(avl->right, nil);
	}
}

void	addHeight(t_avl **avl, t_avl *nil)
{
	if (*avl != nil)
	{
	addHeight(&(*avl)->left, nil);
	addHeight(&(*avl)->right, nil);	
	(*avl)->height = MAX((*avl)->left->height, (*avl)->right->height) + 1;
	}
}

void	insertNode(t_avl **root, t_avl *nil, int key)
{
	t_avl *y;
	t_avl *x;
	t_avl *newnode;

	newnode = (t_avl*)malloc(sizeof(t_avl));
	initNode(newnode, nil, key);
	y = nil;
	x = *root;
	while (x != nil)
	{
		y = x;
		if (key < x->key)
			x = x->left;
		else x = x->right;
	}
	newnode->parent = y;
	if (y == nil)
		*root = newnode;
	else if (newnode->key < y->key)
		y->left = newnode;
	else y->right = newnode;
}

void	postOrdertoFree(t_avl *avl, t_avl *nil)
{
	if (avl != nil)	
	{	
		postOrdertoFree(avl->left, nil);
		postOrdertoFree(avl->right, nil);
		free(avl);
	}
}

t_avl	*makeNil(t_avl *nil)
{
	nil->parent = NULL;
	nil->left = NULL;
	nil->right = NULL;
	nil->key = 0;
	nil->height = -1;
	return (nil);
}

int main()
{
	t_avl **root;
	t_avl *nil;
	int i;
	int j = 0;

	nil = (t_avl*)malloc(sizeof(t_avl));
	nil = makeNil(nil); //setting nil
	root = (t_avl**)malloc(sizeof(t_avl*));
	*root = nil;
	srand(42);
	while (j < 50) // 1 ~ 100 까지 수 중에서 50개를 트리에 삽입
	{
		i = rand() % 100 + 1;
		printf("%d번째 입력 : %d, ",j, i);
		insertNode(root, nil, i);
		j++;
	}
	addHeight(root, nil);
	*root = makeAVL(root, nil);
	inOrdertoPrint(*root, nil);
	postOrdertoFree(*root, nil); //free 하기 위한 후위 순회
	free(root);
	printf("\n");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include "avl.h"

void	leftRotate(t_avl **avl, t_avl *nil)
{
	t_avl *y;
	t_avl *x;
	
	x = *avl;
	y = x->right;
	x->right = y->left;
	if (y->left != nil) //nil이면 parent를 설정하지 않음
		y->left->parent = x;
	if (x->parent == nil) //x의 parent의 자식을 y로 바꾸는 과정
		y->parent = nil;
	else if (x == x->parent->left)
		x->parent->left = y;
	else 
		x->parent->right = y;
	y->parent = x->parent; // y의 parent을 x의 parent로 변경
	y->left = x; 
	x->parent = y; // 서로 연결
	x->height = MAX(x->left->height, x->right->height) + 1;
	y->height = MAX(y->left->height, y->right->height) + 1;
}

void	rightRotate(t_avl **avl, t_avl *nil)
{
	t_avl *x;
	t_avl *y;

	x = *avl;
	y = x->left;
	x->left = y->right;
	if (y->right != nil)
		y->right->parent = x;
	if (x->parent == nil)
		y->parent == nil;
	else if (x == x->parent->left)
		x->parent->left = y;
	else
		x->parent->right = y;
	y->parent = x->parent;
	y->right = x;
	x->parent = y;
	x->height = MAX(x->left->height, x->right->height) + 1;
	y->height = MAX(y->left->height, y->right->height) + 1;
}

void	updateHeight(t_avl **avl, t_avl *nil)
{
	t_avl *x;

	x = *avl;
	while (x ->parent != nil)
	{
		x->parent->height = MAX(x->parent->left->height, x->parent->right->height) + 1;
		x = x->parent;
	}
}

void	buildAVL(t_avl **avl, t_avl *nil)
{
	if (*avl != nil)
	{
		buildAVL(&(*avl)->left, nil);
		buildAVL(&(*avl)->right, nil);
		if (ABS((*avl)->right->height - (*avl)->left->height) <= 1)
		{
			return ;
		}
		else if ((*avl)->right->height > (*avl)->left->height)
		{
			if ((*avl)->right->left->height > (*avl)->right->right->height)
			{
				rightRotate(&(*avl)->right, nil);
				leftRotate(avl, nil);
			}
			else
				leftRotate(avl, nil);
			updateHeight(avl, nil);
		}
		else 
		{
			if ((*avl)->left->right->height > (*avl)->left->left->height)
			{
				leftRotate(&(*avl)->left, nil);
				rightRotate(avl, nil);
			}
			else
				rightRotate(avl, nil);
			updateHeight(avl, nil);
		}
	}
}

t_avl	*makeAVL(t_avl **avl, t_avl *nil)
{
	t_avl *root;

	buildAVL(avl, nil);
	root = *avl;
	while (root->parent != nil)
		root = root->parent;
	return (root);
}