It's huge, isn't it?
#include <stdio.h> #include <stdlib.h> #include "bst.struct.h" void show(ELEM *curr) { if (curr!=NULL && curr->left!=NULL) { printf("%d [%d,%d]\t--L-> %d [%d,%d]\n",curr->val,curr->a,curr->b,curr->left->val,curr->left->a,curr->left->b); show(curr->left); } if (curr!=NULL && curr->right!=NULL) { printf("%d [%d,%d]\t--R-> %d [%d,%d]\n",curr->val,curr->a,curr->b,curr->right->val,curr->right->a,curr->right->b); show(curr->right); } } void fix_my_ab(ELEM *curr) { if (curr!=NULL) { if (curr->right!=NULL) curr->b=((curr->right->a>curr->right->b)?curr->right->a:curr->right->b)+1; else curr->b=0; if (curr->left!=NULL) curr->a=((curr->left->a>curr->left->b)?curr->left->a:curr->left->b)+1; else curr->a=0; fix_my_ab(curr->parent); } } ELEM *check_tree_from(ELEM *root, ELEM *curr, int *wywazen) { //printf("wywolane dla %d, roznica: %d\n",curr->val,curr->b-curr->a); if (curr->b-curr->a==2) { *wywazen=*wywazen+1; if (curr->right->b-curr->right->a==1 || curr->right->b-curr->right->a==0) //metoda 1 { //printf("metoda 1\n"); ELEM *a=curr->right; curr->right=a->left; if (a->left!=NULL) a->left->parent=curr; a->parent=curr->parent; if (curr->parent!=NULL && curr->parent->left==curr) curr->parent->left=a; else if (curr->parent!=NULL && curr->parent->right==curr) curr->parent->right=a; a->left=curr; curr->parent=a; if (curr->right!=NULL) fix_my_ab(curr->right); else if (curr->left!=NULL) fix_my_ab(curr->left); else fix_my_ab(curr); if (a->parent==NULL) root=a; } else if (curr->right->b-curr->right->a==-1) //metoda 4 { //printf("metoda 4\n"); ELEM *a=curr->right; ELEM *b=a->left; b->parent=curr->parent; if (curr->parent!=NULL && curr->parent->left==curr) curr->parent->left=b; else if (curr->parent!=NULL && curr->parent->right==curr) curr->parent->right=b; curr->right=b->left; if (b->left!=NULL) b->left->parent=curr; b->left=curr; curr->parent=b; a->left=b->right; if (b->right!=NULL) b->right->parent=a; b->right=a; a->parent=b; if (a->right!=NULL) fix_my_ab(a->right); else if (a->left!=NULL) fix_my_ab(a->left); else fix_my_ab(a); if (curr->right!=NULL) fix_my_ab(curr->right); else if (curr->left!=NULL) fix_my_ab(curr->left); else fix_my_ab(curr); if (b->parent==NULL) root=b; } } else if (curr->b-curr->a==-2) { *wywazen=*wywazen+1; if (curr->left->b-curr->left->a==-1 || curr->left->b-curr->left->a==0) //metoda 2 { //printf("metoda 2\n"); ELEM *a=curr->left; curr->left=a->right; if (a->right!=NULL) a->right->parent=curr; a->parent=curr->parent; if (curr->parent!=NULL && curr->parent->left==curr) curr->parent->left=a; else if (curr->parent!=NULL && curr->parent->right==curr) curr->parent->right=a; a->right=curr; curr->parent=a; if (curr->right!=NULL) fix_my_ab(curr->right); else if (curr->left!=NULL) fix_my_ab(curr->left); else fix_my_ab(curr); if (a->parent==NULL) root=a; } else if (curr->left->b-curr->left->a==-1) //metoda 3 { //printf("metoda 3\n"); ELEM *a=curr->left; ELEM *b=a->right; b->parent=curr->parent; if (curr->parent!=NULL && curr->parent->left==curr) curr->parent->left=b; else if (curr->parent!=NULL && curr->parent->right==curr) curr->parent->right=b; curr->left=b->right; if (b->right!=NULL) b->right->parent=curr; b->right=curr; curr->parent=b; a->right=b->left; if (b->left!=NULL) b->left->parent=a; b->left=a; a->parent=b; if (a->right!=NULL) fix_my_ab(a->right); else if (a->left!=NULL) fix_my_ab(a->left); else fix_my_ab(a); if (curr->right!=NULL) fix_my_ab(curr->right); else if (curr->left!=NULL) fix_my_ab(curr->left); else fix_my_ab(curr); if (b->parent==NULL) root=b; } } else if (curr->parent!=NULL) root=check_tree_from(root, curr->parent, wywazen); return root; } ELEM *find(ELEM *root, int liczba) { if (root==NULL) //gdy 0 elementow return NULL; else //szukanie miejsca { ELEM *curr=root; while (1) { if (liczba==curr->val) return curr; else if (liczba > curr->val && curr->right!=NULL) //szukamy wiekszej, czyli na prawo curr=curr->right; else if (liczba < curr->val && curr->left!=NULL) //szuakamy mniejszej, czyli lewo curr=curr->left; else //liczby nie ma return NULL; } } } ELEM *usun(ELEM *root, int liczba, int *wywazen, int *operacji) { ELEM *del=find(root, liczba);; if (del!=NULL) { *operacji=*operacji+1; if (del->right==NULL && del->left==NULL) //element jest liściem { //printf("met 1\n"); if (del->parent!=NULL && del->parent->left==del) { del->parent->left=NULL; del->parent->a=0; fix_my_ab(del->parent); root=check_tree_from(root, del->parent, wywazen); } else if (del->parent!=NULL && del->parent->right==del) { del->parent->right=NULL; del->parent->b=0; fix_my_ab(del->parent); root=check_tree_from(root, del->parent, wywazen); } free(del); } else if (del->right==NULL) //element ma tylko lewego potomka { //printf("met 2\n"); if (del->parent!=NULL && del->parent->left==del) { del->parent->left=del->left; del->left->parent=del->parent; fix_my_ab(del->left); root=check_tree_from(root, del->left, wywazen); } else if (del->parent!=NULL && del->parent->right==del) { del->parent->right=del->left; del->left->parent=del->parent; fix_my_ab(del->left); root=check_tree_from(root, del->left, wywazen); } free(del); } else if (del->left==NULL) //element ma tylko prawego potomka { //printf("met 3\n"); if (del->parent!=NULL && del->parent->left==del) { del->parent->left=del->right; del->right->parent=del->parent; fix_my_ab(del->right); root=check_tree_from(root, del->right, wywazen); } else if (del->parent!=NULL && del->parent->right==del) { del->parent->right=del->right; del->right->parent=del->parent; fix_my_ab(del->right); root=check_tree_from(root, del->right, wywazen); } free(del); } else if (del->b >= del->a && del->right->left==NULL) //jedno zejście w prawo { //printf("met 4\n"); if (del->parent!=NULL && del->parent->left==del) { del->parent->left=del->right; del->right->parent=del->parent; } else if (del->parent!=NULL && del->parent->right==del) { del->parent->right=del->right; del->right->parent=del->parent; } del->right->left=del->left; if (del->left!=NULL) del->left->parent=del->right; if (del->right->parent==NULL) root=del->right; fix_my_ab(del->right); root=check_tree_from(root, del->right, wywazen); free(del); } else if (del->b >= del->a && del->left->right==NULL) //jedno zejście w lewo { //printf("met 5\n"); if (del->parent!=NULL && del->parent->left==del) { del->parent->left=del->left; del->left->parent=del->parent; } else if (del->parent!=NULL && del->parent->right==del) { del->parent->right=del->left; del->left->parent=del->parent; } del->left->right=del->right; if (del->right!=NULL) del->right->parent=del->left; if (del->left->parent==NULL) root=del->left; fix_my_ab(del->left); root=check_tree_from(root, del->left, wywazen); free(del); } else if (del->b >= del->a && del->right->left!=NULL) //raz w prawo, max w lewo { //printf("met 6\n"); ELEM *tmp=del->right; while (tmp->left->left!=NULL) tmp=tmp->left; ELEM *newroot=tmp->left; newroot->parent=del->parent; if (del->parent!=NULL && del->parent->left==del) del->parent->left=newroot; else if (del->parent!=NULL && del->parent->right==del) del->parent->right=newroot; tmp->left=newroot->right; if (newroot->right!=NULL) newroot->right->parent=tmp; newroot->left=del->left; if (del->left!=NULL) del->left->parent=newroot; newroot->right=del->right; del->right->parent=newroot; fix_my_ab(tmp); root=check_tree_from(root, tmp, wywazen); free(del); if (newroot->parent==NULL) root=newroot; } else if (del->b < del->a && del->left->right!=NULL) //raz w lewo, max w prawo { //printf("met 7\n"); ELEM *tmp=del->left; while (tmp->right->right!=NULL) tmp=tmp->right; ELEM *newroot=tmp->right; newroot->parent=del->parent; if (del->parent!=NULL && del->parent->left==del) del->parent->left=newroot; else if (del->parent!=NULL && del->parent->right==del) del->parent->right=newroot; tmp->right=newroot->left; if (newroot->left!=NULL) newroot->left->parent=tmp; newroot->right=del->right; if (del->right!=NULL) del->right->parent=newroot; newroot->left=del->left; del->left->parent=newroot; fix_my_ab(tmp); root=check_tree_from(root, tmp, wywazen); free(del); if (newroot->parent==NULL) root=newroot; } } return root; } ELEM *dodaj(ELEM *root, int liczba, int *wywazen, int *operacji) { //printf("dodaje %d\n",liczba); //printf("wyw: %d\t",wywazen); if (root==NULL) //gdy jeszcze 0 elementow { root = (ELEM *) malloc(sizeof(ELEM)); root->parent=NULL; root->left=NULL; root->right=NULL; root->val=liczba; root->a=0; root->b=0; *operacji=*operacji+1; } else //szukanie miejsca { ELEM *new; new = (ELEM *) malloc(sizeof(ELEM)); new->val=liczba; new->a=0; new->b=0; new->left=NULL; new->right=NULL; new->parent=NULL; ELEM *curr=root; while (1) { if (curr->val > new->val && curr->left==NULL) //wstawiamy na lewo { curr->left=new; new->parent=curr; curr->a=1; *operacji=*operacji+1; fix_my_ab(curr->parent); root=check_tree_from(root, new, wywazen); break; } else if (curr->val > new->val) //przechodzimy w lewo curr=curr->left; else if (curr->val < new->val && curr->right==NULL) //wstawiamy na prawo { curr->right=new; new->parent=curr; curr->b=1; *operacji=*operacji+1; fix_my_ab(curr->parent); root=check_tree_from(root, new, wywazen); break; } else if (curr->val < new->val) //przechodzimy w prawo curr=curr->right; else //element juz istnieje break; } } return root; } void wywal(ELEM *curr) { if (curr!=NULL && curr->left!=NULL) wywal(curr->left); if (curr!=NULL && curr->right!=NULL) wywal(curr->right); if (curr!=NULL) free(curr); }