Uncategories C Program FEATURES FOR DISPOSAL OF ELEMENT WITH TREES

C Program FEATURES FOR DISPOSAL OF ELEMENT WITH TREES

C Program FEATURES FOR DISPOSAL OF ELEMENT WITH TREES

/* FUNKCJE DO USUWANIA ELEMENTU Z DRZEWA*/

struct drzewo *tree_minimum(struct drzewo *element){
while(element->lewy!=NULL && element->lewy!=nil)
element=element->lewy;
return element;
}

struct drzewo *tree_successor(struct drzewo *element){
struct drzewo *y=(struct drzewo *)malloc(sizeof(struct drzewo));
if(element->prawy!=nil && element->prawy!=NULL)
return tree_minimum(element->prawy);
y=element->p;
while(y!=nil && y!=NULL && y->lewy!=element){
element=y;
y=y->p;
}
return y;
}


void rb_delete_fixup(struct drzewo *x){
struct drzewo *w=NULL;
while(x!=korzen && x->kolor==czarny){
if(x==x->p->lewy){
w=x->p->prawy;
if(w->kolor==czerwony){
w->kolor=czarny;
x->p->kolor=czerwony;
left_rotate(x->p);
w=x->p->prawy;
}
if(w->lewy->kolor==czarny && w->prawy->kolor==czarny){
w->kolor=czerwony;
x=x->p;
}
else{
if(w->prawy->kolor==czarny){
w->lewy->kolor=czarny;
w->kolor=czerwony;
right_rotate(w);
w=x->p->prawy;
}
w->kolor=x->p->kolor;
x->p->kolor=czarny;
w->prawy->kolor=czarny;
left_rotate(x->p);
x=korzen;
   }
}
else{
w=x->p->lewy;
if(w->kolor==czerwony){
w->kolor=czarny;
x->p->kolor=czerwony;
right_rotate(x->p);
w=x->p->lewy;
}
if(w->prawy->kolor==czarny && w->lewy->kolor==czarny){
w->kolor=czerwony;
x=x->p;
}
else{
if(w->lewy->kolor==czarny){
w->prawy->kolor=czarny;
w->kolor=czerwony;
left_rotate(w);
w=x->p->lewy;
}
w->kolor=x->p->kolor;
x->p->kolor=czarny;
w->lewy->kolor=czarny;
right_rotate(x->p);
x=korzen;
}
}
}
x->kolor=czarny;

}


void rb_delete(struct drzewo *z){
struct drzewo *y=NULL;
struct drzewo *x=NULL;
if(z->lewy==nil || z->prawy==nil) y=z;
else y=tree_successor(z);

if(y->lewy!=nil) x=y->lewy;
else x=y->prawy;

x->p=y->p;

if(y->p==nil) korzen=x;
else if(y==y->p->lewy) y->p->lewy=x;
else y->p->prawy=x;

if(y!=z) z->klucz=y->klucz; /*inne pola tez skopiowac, gdy istnieja?*/

if(y->kolor==czarny) rb_delete_fixup(x);

free(y); /*zwolnij pamiec po elemencie*/

}


struct drzewo *szukaj(struct drzewo *element, int el){
while(element!=NULL && element!=nil && element->klucz!=el){
if(el<element->klucz) element=element->lewy;
else element=element->prawy;
}

return element;
}


void usun(){ /*analogicznie do wstaw*/
int a, el;
struct drzewo *element=(struct drzewo *)malloc(sizeof(struct drzewo));
while(scanf("%d", &a)!=1) scanf("%d", &el);
element=szukaj(korzen,a);

if(element!=NULL && element!=nil) rb_delete(element);
else printf("Liczby %d nie ma w drzewie\n", a);

}

/*GLEBOKOSC DRZEWA RBT */


int max(int a, int b){
if(a>b) return a;
else return b;
}

int wysokosc_rbt(struct drzewo *x){
int wys;
if(x==NULL || x==nil) return -1;
else {
wys=max(wysokosc_rbt(x->lewy), wysokosc_rbt(x->prawy)) + 1;
return wys;
}
}


Learn More :