Scrieti programul C care va permite efectuarea tuturor operatiilor de baza asupra unui arbore AVL!
Descrierea algoritmului.
Fie x o cheie data. Problema consta in suprimarea din structura de arbore a nodului care are cheia egala cu a nodului cu cheia precizata de x. Suprimarea trebuie facuta a.i. si dupa suprimare arborele sa ramana binar si ordonat.
In prealabil se va cauta in arbore pentru a vedea daca exista un nod cu aceasta cheie. Daca nu exista suprimarea se termina si se va afisa un mesaj de eroare, iar daca nodul exista va fi suprimat.
Exista 2 situatii:
nodul de suprimat este un nod terminal sau are cel mult un fiu;
nodul are 2 fii.
Cazul 1. Nodul de suprimat are cel mult un fiu.
In acest caz suprimarea este directa(fig. 1).
Pentru a 858f56i putea descrie acest proces mai avem nevoie de o var auxiliara: ref q.
Secventa C care descrie acest proces este:
q = p;
if(q->dr==NULL)
p = q->st; /*nodul nu are fiu drept*/
else if(q->st==NULL)
p = q->dr; /*nodul nu are fiu stang*/
else /*nodul are 2 fii*/
Cazul 2. Nodul de suprimat are 2 fii(fig. 2).
Notam cu p – var. pointer din nodul parinte a lui x care contine adresa nodului x.
Suprimarea se va realiza astfel: se cauta predecesorul sau succesorul nodului x in inordine, fie acesta nodul y, se inlocuieste nodul x cu nodul y(in sensul ca toate campurile nodului y se vor asigna nodului x, cu exceptia campului stang si drept).
In acest moment nodul y intervine de 2 ori in structura de arbore. Vom suprima nodul y din pozitia initiala conform cazului 1), intrucat nodul y va avea cel mult un fiu fiind predecesorul(succesorul) sau in inordine.
Observatii:
Daca vom folosi pe postul lui y succesorul lui x in inordine el va fi cel mai din stanga nod al subarborelui sau drept.
Predecesorul in inordine va fi cel mai din dreapta nod al subarborelui sau stang.
Referitor la gasirea nodului y putem preciza urmatorele: se construieste o secventa de noduri incepand cu fiul stang al nodului x si pentru fiecare nod din secventa se va lua drept succesor fiul drept. Primul nod care nu va avea fiu drept va fi nodul y.
Functiile care descriu suprimarea unui nod in acest caz si care sunt valabile in cazul general sunt:
void Suprimafd(ref *r)
}/*Suprimafd*/
void Suprimare(int x, ref *p)
}/*Suprima*/
Consideram ca arborele are structura:
typedef struct nod
Tnod;
typedef Tnod * ref;
ref radacina;
Vom presupune arborele urmator:
Vom presupune ca vom sterge pe rand nodurile: 7, 11, 9 , 8, 4.
Suprimarea unui nod dintr-un arbore AVL se face dupa acelas pricipiu 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 var pointer care contine adresa radacini pointerului din care se face suprimarea.
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 dezechilibrare 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 inlocuid 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 ndul 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.
Rezolvare:
Scrieti programul C care permite efectuarea tuturor operatiilor asupra unui arbore AVL.
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <dos.h>
const int raza=20;
const int timp=100;
typedef struct nod
Tnod;
typedef Tnod *ref;
ref radacina,q;
int n,s,x,h;
char c;
void Insert_Echil(int x,ref *p,int *h)
else
if(x<(*p)->cheie)
else /*p1->ech=1, cazul II stanga*/
(*p)->ech=0;
(*h)=0;
break;
} /*sfarsitul switchului*/
}/*sfarsitul ramurii stangi*/
else if(x>(*p)->cheie)
else/*cazul II dreapta*/
(*p)->ech=0;
(*h)=0;
break;
}/*sfarsit switch*/
}/*sfarsit ramura dreapta*/
}
else/*nodul de inserat exista in arbore, se incrementeaza contorul*/
}/*Insert_Echil*/
void creare(void)
}/*creare*/
void Echilibru1(ref *p,int *h)
else
(*p)=p1;
}
else
else
if(p2->ech==0)
else
p2->ech=0;
(*p)=p2;
}
break;
}/*switch*/
}/*Echilibru1*/
void Echilibru2(ref *p,int *h)
else
(*p)=p1;
}
else
else
if(p2->ech==0)
else
p2->ech=0;
(*p)=p2;
}
}/*switch*/
}/*Echilibru2*/
void suprimafd(ref *r, int *h, ref *q)
else
}/*suprimafd*/
void Suprima_Echil(int x, ref *p, int *h)
else
if(x<(*p)->cheie)
else
if(x>(*p)->cheie)
else
else if(q->st==NULL)
else /*nodul are doi fii*/
free(q);
}
}/*Suprima_Echil*/
void Init_Mod_Grafic(void)
}/*Init_Mod_Grafic*/
void Tip(ref a,int nivel,int x1,int x2,int c1,int c2,char *s)
/*Tip*/
void Inordine(ref rad,int nivel,int x1,int x2,int c1,int c2)
}/*Inordine*/
void InordineS(ref rad,int nivel,int x1,int x2,int c1, int c2)
}/*Inordine*/
void Preordine(ref rad,int nivel,int x1,int x2,int c1,int c2)
}/*Preordine*/
void Postordine(ref rad, int nivel,int x1, int x2, int c1, int c2)
}/*Postordine*/
ref Loc(int x, ref t)
/*Loc*/
void main(void)
else outtextxy(0,0,'Arborele nu exista');
closegraph();
break;
case 'E':Init_Mod_Grafic();
delay(1000);
cleardevice();
settextstyle(2,0,5);
if(radacina!=NULL)
else outtextxy(0,0,'Arborele nu exista');
closegraph();
break;
case 'O':Init_Mod_Grafic();
delay(1000);
cleardevice();
settextstyle(2,0,5);
if(radacina!=NULL)
else outtextxy(0,0,'Arborele nu exista');
closegraph();
break;
case 'S':Init_Mod_Grafic();
delay(1000);
cleardevice();
settextstyle(2,0,5);
if(radacina!=NULL)
else outtextxy(0,0,'Arborele nu exista');
closegraph();
break;
case 'X':break;
}/*switch*/
printf('Tastati Enter!n');
getch();
}while(op!='X');
}/*functia principala*/
|
