zzun.net

[C] AVL Tree

IT/소스코드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;
}

'IT > 소스코드' 카테고리의 다른 글

[C++] Maximum Sum (upgrade)  (2) 2004.05.18
[C++] Maximum Sum  (0) 2004.05.10
[C] AVL Tree  (0) 2003.10.16
[C] fork(), exec(), and wait()  (0) 2003.10.16
[C] Binary Search Tree  (0) 2003.10.11
[MIT Scheme] Calculator  (0) 2003.07.10
C

Comment +0

2003 Fall / 컴퓨터 모델링 / 고건 교수님

/**

myshell

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include <stdio.h>

void fork_and_exec(char* path, int block_parent)
{
       int pid;
       pid = fork();

       if (pid == 0)
               execlp(path, path, (char *)0);
       else if (pid>0 && block_parent==1)
               waitpid(pid, NULL, 0);
}

int main()
{
       char buffer[5];

       printf("$$");
       while (scanf("%s", &buffer) != EOF)
       {
               if (!strcmp(buffer, "d"))
                       fork_and_exec("/bin/date", 1);
               else if (!strcmp(buffer, "d&"))
                       fork_and_exec("/bin/date", 0);
               else if (!strcmp(buffer, "n"))
                       fork_and_exec("./myscript", 1);
               else if (!strcmp(buffer, "n&"))
                       fork_and_exec("./myscript", 0);
               else
                       printf("myshell: %s: command not found\n", buffer);

               printf("$$");
       }
       return 0;
}

'IT > 소스코드' 카테고리의 다른 글

[C++] Maximum Sum  (0) 2004.05.10
[C] AVL Tree  (0) 2003.10.16
[C] fork(), exec(), and wait()  (0) 2003.10.16
[C] Binary Search Tree  (0) 2003.10.11
[MIT Scheme] Calculator  (0) 2003.07.10
[Java] Soma Cube  (0) 2003.07.10

Comment +0

2003 Fall / 화일처리 / 이석호 교수님

/**

Binary Search Tree

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include <stdio.h>

struct znode                        // binary search tree node
{
       int data;                        // data type is integer
       struct znode * left;                        // left subtree
       struct znode * right;                        // right subtree
};

struct znode * root = NULL;                        // root node, initially NULL

void print_tree_inorder(struct znode* tree)       // print tree in inorder (left -> parent -> right)
{
       if (tree == NULL)
               printf("Tree is empty!\n");
       else
       {
               if (tree->left != NULL)
                       print_tree_inorder(tree->left);
               printf("%d ", tree->data);
               if (tree->right != NULL)
                       print_tree_inorder(tree->right);
       }
}

struct znode* insert(int insert_data, struct znode* tree)                // node insert
{
       if (tree == NULL)                  // if null, make new node
       {
               tree = (struct znode *)malloc(sizeof(struct znode));
               tree->data = insert_data;
               tree->left = NULL;
               tree->right = NULL;
       }
       else if (insert_data < tree->data)                // insert data in left subtree
               tree->left = insert(insert_data, tree->left);
       else if (insert_data > tree->data)
               tree->right = insert(insert_data, tree->right);         // insert data in right subtree
       else
               printf("Insert Error : item duplicated!\n");        // when the item already exists

       return tree;
}

struct znode* zremove_min(struct znode* tree)          // delete minimum-valued node
{
       struct znode* temp = tree;

       if (tree == NULL)
               printf("remove Minimum Error : null tree!\n");
       else if (tree->left != NULL)
               tree->left = zremove_min(tree->left);              // traverse to left and left again
       else
       {
               tree = tree->right;                   // attach right subtree(or NULL) to parent
               free(temp);                               // and remove the old parent
       }

       return tree;
}

struct znode* zremove(int remove_data, struct znode* tree)           // delete node
{
       struct znode* temp = tree;

       if (tree == NULL)
               printf("remove Error : item not found!\n");
       else if (remove_data < tree->data)            // delete data in left subtree
               tree->left = zremove(remove_data, tree->left);
       else if (remove_data > tree->data)
               tree->right = zremove(remove_data, tree->right);   // delete data in right subtree
       else if (tree->left != NULL && tree->right != NULL)
                                // if this has both left and rihgt subtree
       {
               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 = zremove_min(tree->right);     // and remove it in right subtree
       }
       else
       {
               tree = (tree->left != NULL) ? tree->left : tree->right;
                         // attach one of two children to parent (tree or NULL)
               free(temp);                                // free the old parent
       }

       return tree;
}

int main()
{
       FILE* fp;
       char buffer[11];

       fp = fopen("index.txt", "r");
       while (fgets(buffer, 10, fp) != NULL)                  // read one line from index.txt
       {
               printf("\ninsert %d : ", atoi(buffer));
               root = insert(atoi(buffer), root);                  // insert it
               print_tree_inorder(root);                              // and print the current tree shape
       }
       fclose(fp);

       fp = fopen("index.txt", "r");                             // close and reopen
       while (fgets(buffer, 10, fp) != NULL)
       {
               printf("\ndelete %d : ", atoi(buffer));
               root = zremove(atoi(buffer), root);               // delete a node
               print_tree_inorder(root);                              // and print
       }
       fclose(fp);

       return 0;
}

/**

Binary Search Tree

zzun
hello82@unitel.co.kr
http://zzun.net

**/

'IT > 소스코드' 카테고리의 다른 글

[C] AVL Tree  (0) 2003.10.16
[C] fork(), exec(), and wait()  (0) 2003.10.16
[C] Binary Search Tree  (0) 2003.10.11
[MIT Scheme] Calculator  (0) 2003.07.10
[Java] Soma Cube  (0) 2003.07.10
[C++] 3-dimension 63-Puzzle  (1) 2003.07.10
C

Comment +0


티스토리 툴바