IT/소스코드

[C] AVL Tree

zzun 2003. 10. 16. 19:00
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;
}