반응형
2003 Fall / 화일처리 / 이석호 교수님
/**
AVL Tree
zzun
hello82@unitel.co.kr
http://zzun.net
**/
#include <stdio.h>
struct node // AVL tree node
{
int data; // data type is integer
struct node * left; // left subtree
struct node * right; // right subtree
int height; // height of the tree
};
struct node * root = NULL; // root node, initially NULL
void print_tree_level_order(struct node* tree, int length) // print tree in level order
{
struct node** queue; // queue for printing
struct node* current; // current printing node
int front = 0; // front pointer of queue
int back = 0; // back pointer of queue
queue = (struct node**)malloc(sizeof(void *)*length); // queue initailization
queue[0] = tree; // enqueue root node
while (queue[front] != NULL) // until queue is empty
{
current = queue[front];
printf("%d-", current->data); // print current node
if (current->left != NULL) // if left node is exist, then enqueue it
{
back = (back+1) % length;
queue[back] = current->left;
}
if (current->right != NULL) // if right node is exist, then enquee it
{
back = (back+1) % length;
queue[back] = current->right;
}
queue[front] = NULL; // dequeue printed element
front = (front+1) % length; // move front pointer to the next
}
if (length==0)
printf("Empty Tree!\n");
else
printf("\n");
free(queue);
}
int max(int x, int y)
{
return x > y ? x : y;
}
int height_of(struct node* tree)
{
return tree == NULL ? -1 : tree->height; // if the tree is NULL, its height is -1
}
void reset_height(struct node* tree) // after rotation, reset tree's height
{
if (tree != NULL)
tree->height = max(height_of(tree->left), height_of(tree->right)) + 1;
}
struct node* rotate_left(struct node* t) // rotate left for balancing
{
struct node* new_node = t->left;
t->left = new_node->right;
new_node->right = t;
reset_height(t);
reset_height(new_node); // reset nodes' height
return new_node;
}
struct node* rotate_right(struct node* t) // right
{
struct node* new_node = t->right;
t->right = new_node->left;
new_node->left = t;
reset_height(t);
reset_height(new_node);
return new_node;
}
struct node* double_rotate_left(struct node* t) // in some cases, need to rotate twice
{
t->left = rotate_right(t->left);
return rotate_left(t);
}
struct node* double_rotate_right(struct node* t) // symmetric
{
t->right = rotate_left(t->right);
return rotate_right(t);
}
struct node* insert(int insert_data, struct node* tree) // node insert
{
if (tree == NULL) // if null, make new node
{
tree = (struct node *)malloc(sizeof(struct node));
tree->data = insert_data;
tree->left = NULL;
tree->right = NULL;
tree->height = 0;
}
else if (insert_data < tree->data) // insert data in left subtree
{
tree->left = insert(insert_data, tree->left);
if (height_of(tree->left) - height_of(tree->right) == 2)
{
if (insert_data < tree->left->data)
tree = rotate_left(tree);
else
tree = double_rotate_left(tree);
}
}
else if (insert_data > tree->data)
{
tree->right = insert(insert_data, tree->right);
if (height_of(tree->right) - height_of(tree->left) == 2)
{
if (insert_data > tree->right->data)
tree = rotate_right(tree);
else
tree = double_rotate_right(tree);
}
}
else
printf("Insert Error : item duplicated!\n"); // when the item already exists
reset_height(tree); // reset tree's height
return tree;
}
struct node* delete_min(struct node* tree) // delete minimum-valued node
{
struct node* temp = tree;
if (tree == NULL)
printf("Delete Minimum Error : null tree!\n");
else if (tree->left != NULL)
{
tree->left = delete_min(tree->left); // traverse to left and left again
if (height_of(tree->right) - height_of(tree->left) == 2)
{
if (height_of(tree->right->left) > height_of(tree->right->right))
tree = double_rotate_right(tree);
else
tree = rotate_right(tree);
}
}
else
{
tree = tree->right; // attach right subtree(or NULL) to parent
free(temp); // and deletee the old parent
}
reset_height(tree);
return tree;
}
struct node* deletee(int delete_data, struct node* tree) // delete node
{
struct node* temp = tree;
if (tree == NULL)
printf("Delete Error : item not found!\n");
else if (delete_data < tree->data) // delete data in left subtree
{
tree->left = deletee(delete_data, tree->left);
if (height_of(tree->right) - height_of(tree->left) == 2)
{
if (height_of(tree->right->left) > height_of(tree->right->right))
tree = double_rotate_right(tree);
else
tree = rotate_right(tree);
}
}
else if (delete_data > tree->data)
{
tree->right = deletee(delete_data, tree->right);
if (height_of(tree->left) - height_of(tree->right) == 2)
{
if (height_of(tree->left->right) > height_of(tree->left->left))
tree = double_rotate_left(tree);
else
tree = rotate_left(tree);
}
}
else if (tree->left != NULL && tree->right != NULL)
{
temp = temp->right;
while (temp->left != NULL)
temp = temp->left; // find the minimum data of right subtree
tree->data = temp->data; // and set it to the parent
tree->right = delete_min(tree->right); // and deletee it in right subtree
}
else
{
tree = (tree->left != NULL) ? tree->left : tree->right;
free(temp); // free the old parent
}
reset_height(tree);
return tree;
}
int main()
{
FILE* fp;
char buffer[11];
int count = 0; // # of elements
fp = fopen("index.txt", "r");
while (fgets(buffer, 10, fp) != NULL) // read one line from index.txt
{
printf("insert %d : ", atoi(buffer));
root = insert(atoi(buffer), root); // insert it
count++;
print_tree_level_order(root, count); // and print tree in level order
}
fclose(fp);
fp = fopen("index.txt", "r"); // close and reopen
while (fgets(buffer, 10, fp) != NULL)
{
printf("delete %d : ", atoi(buffer));
root = deletee(atoi(buffer), root); // delete a node
count--;
print_tree_level_order(root, count); // and print
}
fclose(fp);
return 0;
}
/**
AVL Tree
zzun
hello82@unitel.co.kr
http://zzun.net
**/
#include <stdio.h>
struct node // AVL tree node
{
int data; // data type is integer
struct node * left; // left subtree
struct node * right; // right subtree
int height; // height of the tree
};
struct node * root = NULL; // root node, initially NULL
void print_tree_level_order(struct node* tree, int length) // print tree in level order
{
struct node** queue; // queue for printing
struct node* current; // current printing node
int front = 0; // front pointer of queue
int back = 0; // back pointer of queue
queue = (struct node**)malloc(sizeof(void *)*length); // queue initailization
queue[0] = tree; // enqueue root node
while (queue[front] != NULL) // until queue is empty
{
current = queue[front];
printf("%d-", current->data); // print current node
if (current->left != NULL) // if left node is exist, then enqueue it
{
back = (back+1) % length;
queue[back] = current->left;
}
if (current->right != NULL) // if right node is exist, then enquee it
{
back = (back+1) % length;
queue[back] = current->right;
}
queue[front] = NULL; // dequeue printed element
front = (front+1) % length; // move front pointer to the next
}
if (length==0)
printf("Empty Tree!\n");
else
printf("\n");
free(queue);
}
int max(int x, int y)
{
return x > y ? x : y;
}
int height_of(struct node* tree)
{
return tree == NULL ? -1 : tree->height; // if the tree is NULL, its height is -1
}
void reset_height(struct node* tree) // after rotation, reset tree's height
{
if (tree != NULL)
tree->height = max(height_of(tree->left), height_of(tree->right)) + 1;
}
struct node* rotate_left(struct node* t) // rotate left for balancing
{
struct node* new_node = t->left;
t->left = new_node->right;
new_node->right = t;
reset_height(t);
reset_height(new_node); // reset nodes' height
return new_node;
}
struct node* rotate_right(struct node* t) // right
{
struct node* new_node = t->right;
t->right = new_node->left;
new_node->left = t;
reset_height(t);
reset_height(new_node);
return new_node;
}
struct node* double_rotate_left(struct node* t) // in some cases, need to rotate twice
{
t->left = rotate_right(t->left);
return rotate_left(t);
}
struct node* double_rotate_right(struct node* t) // symmetric
{
t->right = rotate_left(t->right);
return rotate_right(t);
}
struct node* insert(int insert_data, struct node* tree) // node insert
{
if (tree == NULL) // if null, make new node
{
tree = (struct node *)malloc(sizeof(struct node));
tree->data = insert_data;
tree->left = NULL;
tree->right = NULL;
tree->height = 0;
}
else if (insert_data < tree->data) // insert data in left subtree
{
tree->left = insert(insert_data, tree->left);
if (height_of(tree->left) - height_of(tree->right) == 2)
{
if (insert_data < tree->left->data)
tree = rotate_left(tree);
else
tree = double_rotate_left(tree);
}
}
else if (insert_data > tree->data)
{
tree->right = insert(insert_data, tree->right);
if (height_of(tree->right) - height_of(tree->left) == 2)
{
if (insert_data > tree->right->data)
tree = rotate_right(tree);
else
tree = double_rotate_right(tree);
}
}
else
printf("Insert Error : item duplicated!\n"); // when the item already exists
reset_height(tree); // reset tree's height
return tree;
}
struct node* delete_min(struct node* tree) // delete minimum-valued node
{
struct node* temp = tree;
if (tree == NULL)
printf("Delete Minimum Error : null tree!\n");
else if (tree->left != NULL)
{
tree->left = delete_min(tree->left); // traverse to left and left again
if (height_of(tree->right) - height_of(tree->left) == 2)
{
if (height_of(tree->right->left) > height_of(tree->right->right))
tree = double_rotate_right(tree);
else
tree = rotate_right(tree);
}
}
else
{
tree = tree->right; // attach right subtree(or NULL) to parent
free(temp); // and deletee the old parent
}
reset_height(tree);
return tree;
}
struct node* deletee(int delete_data, struct node* tree) // delete node
{
struct node* temp = tree;
if (tree == NULL)
printf("Delete Error : item not found!\n");
else if (delete_data < tree->data) // delete data in left subtree
{
tree->left = deletee(delete_data, tree->left);
if (height_of(tree->right) - height_of(tree->left) == 2)
{
if (height_of(tree->right->left) > height_of(tree->right->right))
tree = double_rotate_right(tree);
else
tree = rotate_right(tree);
}
}
else if (delete_data > tree->data)
{
tree->right = deletee(delete_data, tree->right);
if (height_of(tree->left) - height_of(tree->right) == 2)
{
if (height_of(tree->left->right) > height_of(tree->left->left))
tree = double_rotate_left(tree);
else
tree = rotate_left(tree);
}
}
else if (tree->left != NULL && tree->right != NULL)
{
temp = temp->right;
while (temp->left != NULL)
temp = temp->left; // find the minimum data of right subtree
tree->data = temp->data; // and set it to the parent
tree->right = delete_min(tree->right); // and deletee it in right subtree
}
else
{
tree = (tree->left != NULL) ? tree->left : tree->right;
free(temp); // free the old parent
}
reset_height(tree);
return tree;
}
int main()
{
FILE* fp;
char buffer[11];
int count = 0; // # of elements
fp = fopen("index.txt", "r");
while (fgets(buffer, 10, fp) != NULL) // read one line from index.txt
{
printf("insert %d : ", atoi(buffer));
root = insert(atoi(buffer), root); // insert it
count++;
print_tree_level_order(root, count); // and print tree in level order
}
fclose(fp);
fp = fopen("index.txt", "r"); // close and reopen
while (fgets(buffer, 10, fp) != NULL)
{
printf("delete %d : ", atoi(buffer));
root = deletee(atoi(buffer), root); // delete a node
count--;
print_tree_level_order(root, count); // and print
}
fclose(fp);
return 0;
}
반응형