avl.c

//avl트리 책에 있는 소스 수정

#include <stdio.h>
#include <stdlib.h>

 typedef struct avl_node   {
    struct avl_node *left_child, *right_child;  /* Subtrees. */
    int data;                   /* Pointer to data. */
}avl_node;


int max(int x,int y)
{
	if(x>=y) return x;
	else return y;
}
// 왼쪽 회전 함수
avl_node *rotate_left( avl_node *parent)
{
    avl_node *child = parent->left_child;
	parent->left_child = child->right_child;
	child->right_child = parent;
	return child;
}
// 오른쪽 회전 함수
avl_node *rotate_right( avl_node *parent)
{
    avl_node *child = parent->right_child;
	parent->right_child = child->left_child;
	child->left_child = parent;
	return child;
}
// 오른쪽-왼쪽 회전 함수
avl_node *rotate_right_left( avl_node *parent)
{
    avl_node *child = parent->right_child;
	parent->right_child = rotate_left(child);
	return rotate_right(parent);
}
// 왼쪽-오른쪽 회전 함수
avl_node *rotate_left_right( avl_node *parent)
{
    avl_node *child = parent->left_child;
	parent->left_child = rotate_right(child);
	return rotate_left(parent);
}
// 트리의 높이를 반환
int get_height( avl_node *node)
{
	int height=0;
	if( node != NULL )
		height = 1 + max(get_height(node->left_child), 
						get_height(node->right_child));
	return height;
}

// 노드의 균형인수를 반환
int get_height_diff( avl_node *node) 
{
	if( node == NULL ) return 0;
	return get_height(node->left_child) - get_height(node->right_child);
} 

avl_node *rebalance( avl_node *node)
{
	int height_diff = get_height_diff(node);
	if( height_diff > 1 ){
		if( get_height_diff(node->left_child )> 0 )
			node = rotate_left(node);
		
		else
			node = rotate_left_right(node);
		
	}
	else if ( height_diff < -1 ){
		if( get_height_diff((node)->right_child) < 0 )
			node = rotate_right(node);
		
		else
			node = rotate_right_left(node);
		
	}
	return node;
}


// AVL 트리의 삽입 연산
 /*
 avl_node  *avl_add( avl_node **root, int new_key)
{
	if( *root == NULL ){
		*root = ( avl_node *)
			malloc(sizeof(struct avl_node));//new avl_node;
		if( *root == NULL ){
			fprintf(stderr, "메모리 할당 에러\n");
			exit(1);
		}
		(*root)->data = new_key;
		(*root)->left_child = (*root)->right_child = NULL;
	}
	else if( new_key < (*root)->data ){
 (*root)->left_child=avl_add(&((*root)->left_child), 
				new_key);
		*root = rebalance(root);
	}
	else if( new_key > (*root)->data ){
(*root)->right_child=avl_add(&((*root)->right_child), 	new_key);
		(*root) = rebalance(root);
	}
	else{
		fprintf(stderr, "중복된 키 에러\n");
		exit(1);
	}
	return *root;
}

*/


 avl_node  *avl_add( avl_node *root, int new_key)
{

	
	if( root == NULL ){
		root = ( avl_node *)
			malloc(sizeof(struct avl_node));//new avl_node;
		if( root == NULL ){
			fprintf(stderr, "메모리 할당 에러\n");
			exit(1);
		}
		(root)->data = new_key;
		(root)->left_child = (root)->right_child = NULL;
	}
	else if( new_key < (root)->data ){
        (root)->left_child=avl_add(root->left_child, 
				new_key);
		root = rebalance(root);
	}
	else if( new_key > (root)->data ){
        (root)->right_child=avl_add((root)->right_child, 	new_key);
		(root) = rebalance(root);
	}
	else{
		fprintf(stderr, "중복된 키 에러\n");
		exit(1);
	}
	return root;
}


// AVL 트리의 탐색함수
avl_node *avl_search( avl_node *node, int key) 
{ 
	if( node == NULL ) return NULL; 
  //	printf("%d ", node->data);
	if( key == node->data ) return node; 
	else if( key < node->data ) 
	   	return avl_search(node->left_child, key); 
	else 
		return avl_search(node->right_child, key); 
} 

void inorder( avl_node *node)
{
	if(node==NULL) return;
	inorder(node->left_child);
	printf("< %d> ",node->data);
	inorder(node->right_child);
}

void main()
{
	//8,9,10,2,1,5,3,6,4,7,11,12
	avl_node *root=NULL;
	root=avl_add(root, 8);
	root=avl_add(root, 9);
	root=avl_add(root, 10);
	
	root=avl_add(root, 2);
	root=avl_add(root, 1);
	root=avl_add(root, 5);
	
	root=avl_add(root, 3);
	root=avl_add(root, 6);
	root=avl_add(root, 4);
	root=avl_add(root, 7);
	root=avl_add(root, 11);
	root=avl_add(root, 12);
	
	inorder(root);
	printf("\n");
	avl_node *node=avl_search(root, 12);
	
	if(node) printf("%d is found\n", node->data);
}

퍼펙트 덕환