Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- struct node{
- int key;
- int bf; // balance factor
- struct node * parent;
- struct node * left;
- struct node * right;
- };
- void add(struct node * head, int key)
- {
- if(!head)return;
- if(key < head->key)
- {
- if(head->left)add(head->left, key);
- else
- {
- struct node * n = (struct node *)malloc(sizeof(struct node));
- n->key = key;
- n->parent = head;
- n->left = n->right = NULL;
- head->left = n;
- struct node * tmp = n;
- while(tmp->parent)tmp=tmp->parent;
- update_bf(tmp);
- //balance_tree(tmp);
- }
- } else if(head->key < key) {
- if(head->right)add(head->right, key);
- else
- {
- struct node * n = (struct node *)malloc(sizeof(struct node));
- n->key = key;
- n->parent = head;
- n->left = n->right = NULL;
- head->right = n;
- struct node * tmp = n;
- while(tmp->parent)tmp=tmp->parent;
- update_bf(tmp);
- //balance_tree(tmp);
- }
- }
- }
- struct node * delete_node(struct node * head, int key)
- {
- struct node * tmp = head;
- short change_root = 0;
- while(1)
- {
- if(tmp->key == key)
- {
- if(tmp->parent == NULL)
- change_root = 1;
- if(tmp->left == NULL && tmp->right == NULL)
- {
- if(!tmp->parent)
- {
- free(tmp);
- return NULL;
- } else {
- if(tmp->parent->key > key)
- tmp->parent->left = NULL;
- else
- tmp->parent->right = NULL;
- free(tmp);
- return head;
- }
- } else if (tmp->right != NULL) {
- tmp->right->parent = tmp->parent;
- if(tmp->parent && tmp->parent->key > key)
- tmp->parent->left = tmp->right;
- else if(tmp->parent && tmp->parent->key < key)
- tmp->parent->right = tmp->right;
- struct node * last_left = tmp->right;
- while(last_left->left) last_left = last_left->left;
- last_left->left = tmp->left;
- if(tmp->left)tmp->left->parent = last_left;
- struct node * new_tmp = tmp->right;
- free(tmp);
- if(change_root)
- return new_tmp;
- else
- return head;
- } else {
- tmp->left->parent = tmp->parent;
- if(tmp->parent && tmp->parent->key > key)
- tmp->parent->left = tmp->left;
- else if(tmp->parent && tmp->parent->key < key)
- tmp->parent->right = tmp->left;
- tmp = tmp->left;
- free(tmp->parent);
- if(change_root)
- return tmp;
- else
- return head;
- }
- } else if(tmp->key > key) {
- if(tmp->left)
- tmp = tmp->left;
- else
- {
- printf("W drzewie nie znaleziono wartosci %d.", key);
- return head;
- }
- } else if(tmp->key < key) {
- if(tmp->right)
- tmp = tmp->right;
- else
- {
- printf("W drzewie nie znaleziono wartosci %d.", key);
- return head;
- }
- }
- }
- }
- int update_bf(struct node * head)
- {
- // returns tree height and updates balance factor of all nodes
- if(head)
- {
- //printf("%d, %d, %d, %d -> ", head->key,head->left,head->right,head->parent);
- int lh = 1 + update_bf(head->left);
- int rh = 1 + update_bf(head->right);
- head->bf = lh - rh;
- return lh > rh ? lh : rh;
- }
- }
- void LL_rotation(struct node * head)
- {
- if(head->parent == NULL)return;
- struct node * parent = head->parent;
- struct node * right = head->right;
- if(parent->key > head->key)
- parent->left = head->right;
- else
- parent->right = head->right;
- head->parent = right;
- head->right = right->left;
- right->parent = parent;
- if(right->left)right->left->parent = head;
- right->left = head;
- struct node * tmp = parent;
- while(tmp->parent)tmp = tmp->parent;
- update_bf(tmp);
- }
- void RR_rotation(struct node * head)
- {
- if(head->parent == NULL)return;
- struct node * parent = head->parent;
- struct node * left = head->left;
- if(parent->key > head->key)
- parent->left = head->left;
- else
- parent->right = head->left;
- head->parent = left;
- head->left = left->right;
- left->parent = parent;
- if(left->right)left->right->parent = head;
- left->right = head;
- struct node * tmp = parent;
- while(tmp->parent)tmp = tmp->parent;
- update_bf(tmp);
- }
- void balance_tree(struct node * head)
- {
- if(head)
- {
- balance_tree(head->left);
- balance_tree(head->right);
- if(head->bf <= -2 && head->right->bf < 0)
- LL_rotation(head);
- else if(head->bf >= 2 && head->left->bf > 0)
- RR_rotation(head);
- }
- }
- void print_pre(struct node * head)
- {
- // print binary tree(pre-order)
- if(head)
- {
- printf("%d, bf: %d\n", head->key, head->bf);
- print_pre(head->left);
- print_pre(head->right);
- }
- }
- int get_tree_height(struct node * head)
- {
- if(head)
- {
- int lh = 1 + get_tree_height(head->left);
- int rh = 1 + get_tree_height(head->right);
- return lh > rh ? lh : rh;
- }
- }
- int main()
- {
- printf("AVL BINARY TREE\n\n");
- struct node * head = (struct node *)malloc(sizeof(struct node));
- head->parent = head->left = head->right = NULL;
- head->key = 7;
- head->bf = 0;
- add(head, 10);
- add(head, 8);
- add(head, 5);
- add(head, 4);
- add(head, 6);
- add(head, 15);
- add(head, 14);
- add(head, 17);
- add(head, 18);
- add(head, 3);
- add(head, 2);
- add(head, 1);
- int height = get_tree_height(head);
- printf("PREORDER:\n");
- print_pre(head);
- printf("Tree height: %d\n", height);
- balance_tree(head);
- printf("\n\nBALANCED:\n");
- print_pre(head);
- height = get_tree_height(head);
- printf("Tree height: %d\n", height);
- head = delete_node(head, 5);
- head = delete_node(head, 6);
- //head = delete_node(head, 3);
- struct node * t = head->left->left;
- printf("\n\n%d - %d - %d\n\n", t->key, t->left, t->right);
- //head = delete_node(head, 2);
- //head = delete_node(head, 5);
- //head = delete_node(head, 6);
- update_bf(head);
- print_pre(head);
- balance_tree(head);
- printf("---\n");
- print_pre(head);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment