*p=v; v->bal=0; } } /* konec switche */ } /* konec vyvaz1 */ void vyvaz2(uzel **p,int *h) { /* h=1 - pravá větev se zmenšila */ uzel *u,*v; short int b1,b2; switch ((*p)->bal) { case 1: (*p)->bal=0; break; case 0: (*p)->bal=-1; *h=0; break; case -1: /* znovuvyvážení */ u=(*p)->levy; b1=u->bal; if (b1<=0) { /* jednoduchá LL rotace */ printf ("jednoducha LL rotace\n"); (*p)->levy=u->pravy; u->pravy=*p; if (b1==0) {(*p)->bal=-1; u->bal=1; *h=0;} else {(*p)->bal=0; u->bal=0;} (*p)=u; } else { /* dvojitá LR rotace */ printf("dvojita LR rotace\n"); v=u->pravy; b2=v->bal; u->pravy=v->levy; v->levy=u; (*p)->levy=v->pravy; v->pravy=(*p); (*p)->bal=(b2==-1)?1:0; u->bal=(b2==1)?-1:0; *p=v; v->bal=0; } } /* konec switche */ } /* konec vyvaz2 */ void smaz(uzel **r,int *h) { if((*r)->pravy!=NULL) { smaz(&((*r)->pravy),h); if(*h) vyvaz2(r,h); } else {
98 Algoritmy v jazyku C a C++
Ukázka elektronické knihy, UID: KOS209711
q->klic=(*r)->klic; q->pocet=(*r)->pocet; *r=(*r)->levy; *h=1; } } int zrus(int x, uzel **p, int *h) { if ((*p)==NULL) { printf("klic neni ve stromu\n"); *h=0; } else if(x<(*p)->klic) { zrus(x,&((*p)->levy),h); if (*h) vyvaz1(p,h); } else if(x>(*p)->klic) { zrus(x,&((*p)->pravy),h); if(*h) vyvaz2(p,h); } else /* ted ruším x=(*p)->klic */ { q=(*p); if(q->pravy==NULL) { (*p)=q->levy; *h=1; } else if (q->levy==NULL) { (*p)=q->pravy; *h=1; } else { smaz(&(q->levy),h); if (*h)vyvaz1(p,h); } } return 0; } int pridej(int x, uzel **p, int *h) /* h=true - zvětšení větve */ { uzel *q,*u; if (*p==NULL) { *p=(uzel*)malloc(sizeof(uzel)); if (*p==NULL) return 1; *h=1; (*p)->levy=NULL; (*p)->pravy=NULL; (*p)->klic=x; (*p)->pocet=1; (*p)->bal=0;
Vyhledávací algoritmy 99
Ukázka elektronické knihy, UID: KOS209711
return 0; } else { if ((*p)->klic == x) { (*p)->pocet++; *h=0; return 0; } else { if((*p)->klic>x) { pridej(x,&((*p)->levy),h); if (*h) /* zvětšila se levá větev */ { switch ((*p)->bal) { case 1: (*p)->bal=0; *h=0; break; case 0: (*p)->bal=-1; break; case -1: u=(*p)->levy; if(u->bal==-1) { /* jednoduchá LL rotace */ printf ("jednoducha LL rotace\n"); (*p)->levy=u->pravy; u->pravy=*p; (*p)->bal=0; *p=u; } else { /* dvojitá LR rotace */ q=u->pravy; printf("dvojita LR rotace\n"); u->pravy=q->levy; q->levy=u; (*p)->levy=q->pravy; q->pravy=*p; (*p)->bal=(q->bal==-1)?1:0; u->bal=(q->bal==1)?-1:0; *p=q; } (*p)->bal=0; *h=0; } } } else /* p->klic<x */ { pridej(x,&((*p)->pravy),h); if (*h) /* zvětšila se pravá větev */ {
100 Algoritmy v jazyku C a C++
Ukázka elektronické knihy, UID: KOS209711