Scrieti programul C care permite crearea si suprimarea unui nod dintr-un arbore AVL astfel incat dupa suprimare arborele sa ramana tot AVL
Descrierea algoritmului.
Consideram ca arborele are structura:
typedef struct nod
Tnod;
typedef Tnod * ref;
ref radacina;
Vom presupune un arbore
Vom presupune ca vom sterge pe rand nodurile: 7, 11, 9 , 8, 4.
Suprimarea unui nod dintr-un arbore AVL se face dupa acelas principiu ca si in cazul arborilor binari ordonati. In cazul in care nodul de suprimat are cel mult un fiu,suprimarea directa, in caz contrar nodul se va inlocui cu predecesorul sau in inordine.
Suprimarea nodului de cheie 7
Fie p variabila pointer care contine adresa radacinii pointerului din care se face suprimar 151c21b ea.
Nodul cu cheia 7 este nod frunza, factorul de echilibru al acestuia este -1. Nodul de cheie 7 fiind fiul drept al lui 6 cu factorul de echilibru -1 rezulta ca in urma suprimarii se dezechilibreaza arborele de radacina 6, deci trebuie sa efectuam reechilibrarea arborelui de radacina 6. Intrucat dezechilibrarea se produce pe ramura stanga a arborelui rezulta ca avem cazul de reechilibrare I stanga.
Cazul I stanga de reechilibrare
p->ech = -1;
p1 = p->st; caracteristicile cazului I stanga de reechilibrare
p1->ech <= 0
p->st =
p1->dr; reechilibrare
p1->dr = p;
Fie h o variabila care indica daca se transmite sau nu modificarea mai sus in arbore a factorului de echilibru.
If (p1->ech == 0)
else
p = p1;
Arborele dupa suprimarea nodului de cheie 7 si reechilibrare:
Suprimarea nodului de cheie 11
Consideram arborele din care suprimam nodul ca fiind arborele din figura 3. Nodul cu cheia 11 are 2 fii, dupa suprimare 11 se va inlocui cu cel mai din dreapta nod al subarborelui sau stang.
Arborele dupa suprimarea nodului de cheie 11:
Suprimarea nodului cu cheia 9
Avem cazul de reechilibrare I dreapta.
p1 =
p->dr; caracteristicile
cazului
p1->ech >= 0
Acest caz se va trata analog cu cazul I stanga prin simetrie inlocuind peste tot st<->dr si 1<->-1.
Arborele
dupa suprimarea nodului cu cheia 9 si reechilibrare: 
Figura 5
Suprimarea nodului cu cheia 8
Consideram arborele din figura 5. Dupa suprimare nodul cu cheia 8 se va inlocui cu cel mai din dreapta nod al subarborelui sau stang.
Arborele
dupa suprimarea nodului cu cheia 8 si reechilibrare:
Suprimarea nodului de cheie 4
Consideram
arborele din figura 6. Nodul de radacina 6 se
dezechilibreaza, rezulta cazul de reechilibrare II dreapta.
p1 = p->dr;
p1->ech = -1; caracteristicile cazului II dreapta
p2 = p1->st;
p2->ech = 1;
Arborele dupa suprimarea nodului de cheie 4 si reechilibrare:
Observatii:
Sa constatam ca in cazul suprimarii unui nod dintr-un arbore AVL intervin 4 situatii de rechilibrare: I stanga, II stanga, I dreapta, II dreapta, dar e suficient sa tratam 2 dintre ele(I, II stanga) celelate 2 cazuri fiind rezolvate prin simetrie.
Se constata ca reechilibrarea se impune doar atunci cand scade in inaltime subarborele nodului de radacina al carui factor de echilibru era 1 sau -1.
Reechilibrarea cand factorul de echilibru al lui p era 1 si se sterge un nod din ramura stanga vom avea cazul de reechilibrare dreapta I sau II.Esential este ca a scazut in inaltime ramura stanga. Functia care trateaza acest caz o vom numi echilibru1.
Daca factorul de echilibru era -1 si sterg un nod din subarborele drept al acestuia se produce dezechilibrarea pe ramura stanga si vom avea cazul de reechilibrare stanga I sau II. Vom numi functia care descrie acest caz echilibru2.
Programul C:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <conio.h>
#include <graphics.h>
#include <dos.h>
#define CALE 'c:BorlandcBGI'
#define raza 10
#define timp 500
#define spatiu 40
typedef struct nod
Tnod;
typedef Tnod *ref;
ref radacina, r, q;
int x, h,
culoare_fundal=15,/*culoarea de fundal a nodurilor arborelui*/
culoare_scris=1, /*culoarea cu care sunt scrise nodurile arborelui*/
afisare=0;/*pt. cautare*/
void creare(void)
while(x!=0)
}
}/*creare*/
void insertechil(int x, ref *p, int *h)
else
if(x<(*p)->cheie)
else
/* cazul 2*/
(*p)->ech=0;
*h=0;
break; /* reechilibrarea */
}/*switch */
}/* ramura stanga */
else if(x>(*p)->cheie)
else
/* cazul 2*/
(*p)->ech=0;
*h=0;
break; /* reechilibrarea */
}/*switch */
}/* ramura dreapta */
else
} /* insertechil */
void initializare_mod_grafic(void)
}/*initializare mod grafic*/
void inordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
}/*inordine*/
void tip(ref anod, int nivel, int x1, int x2, int c1, int c2, char *s)
else
setcolor(15);
line((x1+x2)/2, nivel*spatiu+raza, c1,c2+textheight('1')/2);
setfillstyle(SOLID_FILL, culoare_fundal);
fillellipse((x1+x2)/2, nivel*spatiu+raza, raza, raza);
setcolor(culoare_scris);/*albastru*/
sprintf(s, '%d', anod->cheie);
outtextxy((x1+x2)/2, nivel*spatiu+raza, s);
delay(timp);
}/*tiparire grafica*/
ref Loc(int x, ref t)
/*Loc*/
void echilibru2(ref *p, int *h)
else
*p = p1;
}
else /* cazul II stanga */
else if(p2->ech==0)
else /* p2->ech = 1 */
p2->ech = 0;
(*p) = p2;
}
break;
}/* switch */
} /* echilibru2 */
void echilibru1(ref *p, int *h)
else
*p = p1;
}
else /* cazul II stanga */
else if(p2->ech==0)
else /* p2->ech = -1 */
p2->ech = 0;
(*p) = p2;
}
break;
}/* switch */
} /* echilibru1 */
void suprfd(ref *r, int *h, ref *q)
else
}/*suprfd*/
void suprimaechil(int x, ref *p, int *h)
else if(x<(*p)->cheie)
else if(x>(*p)->cheie)
else /* am gasit, deci sterg *p */
else if(q->st==NULL)
else /* are 2 fii */
}
}/*suprimaechil*/
void main(void)
h = 0;
insertechil(x, &radacina, &h);
initializare_mod_grafic();
delay(2000);
settextjustify(1,1);
outtextxy(getmaxx()/2, 10, 'Inserarea unui nod in arbore');
setviewport(0,30,getmaxx(), getmaxy(), 1);
inordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza);
setcolor(WHITE);
outtextxy(getmaxx()/2, getmaxy()-40, 'Apasati o tasta pt. a termina');
fflush(stdin);getch();
closegraph();
break;
case 'S':
if(radacina==NULL)
printf('Introduceti cheia nodului de suprimat: ');
while(scanf('%d', &x)!=1)
h = 0;
suprimaechil(x, &radacina, &h);
printf('Nodul cu cheia %d a fost sters din arbore!n',x);
printf('Apasati o tasta pentru a continua!n'); getch();
break;
case 'F':
if(radacina==NULL)
afisare = 0;
printf('Introduceti cheia nodului de cautat: ');
while(scanf('%d', &x)==0)
r = Loc(x, radacina);
if(r == NULL)
else
break;
case 'A':
if(radacina==NULL)
else
break;
case 'E':
break;
default:
printf('nOptiune invalida !nApasati o tasta!n');
getch();
break;
}
}
while(op!='E');
}/*main*/
|
