Skip to content

Instantly share code, notes, and snippets.

@tiger1710 tiger1710/avl.c
Created Dec 4, 2018

Embed
What would you like to do?
//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);
}
@YongHoonJJo

This comment has been minimized.

Copy link

commented Dec 5, 2018

퍼펙트 덕환

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.