Scrieti programul C care permite crearea si vizualizarea sub forma naturala a unui arbore AVL, precum si suprimarea unui nod dat.

Scrieti programul C care permite crearea si vizualizarea sub forma naturala a unui arbore AVL, precum si suprimarea unui nod dat.

Analiza:

Operatia de suprimare se cere a se efectua astfel incat si dupa suprimare arborele sa ramana tot binar ordonat si echilibrat dupa inaltime.

Suprimarea unui nod se va face dupa aceleasi principii ca si suprimarea unui nod dintr-un arbore binar ordonat (vezi lab. 1), cu atentia suplimentara la reechilibrarea arborelui atunci cand se impune.

Cel mai simplu caz pe care il distingem este cel in care nodul de suprimat are cel mult un fiu, situatie ce se rezolva modificand pointerul care indica adresa nodului de suprimat astfel incat sa indice unicul fiu al nodului de suprimat (sau NULL daca nodul e nod frunza).

Daca nodul are doi fii atunci inlocuim nodul pe care vrem sa-l suprimam cu predecesorul sau in inordine (adica cel mai din dreapta nod al subarborelui sau stang), dupa care vom suprima acest nod (predecesorul sau in inordine).

Obs: Daca nodul are 2 fii, in loc sa inlocuim nodul pe care dorim sa-l stergem cu predecesorul acestuia in inordine putem sa-l inlocuim cu succesorul acestuia in inordine (adica cel mai din stanga nod al subarborelui sau drept).

Fie urmatorul arbore:

fig. 1

Din ac arbore vom suprima pe rand nodurile cu cheile: 7, 11, 9, 8, 4, 3, 10

In vederea suprimarii trebuie mai intai sa cautam nodul in arbore (traversam arborele incepand cu radacina, selectand fiul stang sau fiul drept al nodului curent, dupa cum cheia nodului de suprimat e mai mica, respectiv mai mare decat cheia nodului de suprimat). Daca nodul nu exista in arbore se va emite un mesaj de eroare, iar daca exista se va suprima.

In momentul in care am gasit nodul in arbore, suprimarea se va face conform celor doua situatii evidentiate la suprimarea unui nod in arborii binari ordonati:

nodul are cel mult un fiu

nodul are doi fii

Presupunem cunoscuta modalitatea de suprimare a unui nod dintr-un arbore binar ordonat (vezi lab. 1), si vom insista doar asupra reechilibrarii, cand si cum se impune dupa suprimare.

Suprimarea nodului cu cheia 7:

Fie p variabila pointer ce va contine adresa nodului parinte a nodului de suprimat. Deoarece nodul cu cheia 7 este nod frunza, suprimarea va presupune modificarea:

p->dr = NULL;

Inainte de suprimare factorii de echilibru erau:

fig. 2

Dupa suprimare se modifica factorul de echilibru al nodului cu cheia 6:

fig. 3

Deci se impune reechilibrarea.

Deoarece am sters un nod din subarborele drept, dezechilibrul s-a produs pe ramura stanga. Faptul ca suntem in cazul I sau II de reechilibrare ne spune factorul de echilibru al fiului stang al radacinii. Deoarece

p1 = p->st

p1->ech = -1

suntem in cazul I st de reechilibrare.

Reechilibrarea se va face astfel:

p->st = p1->dr;

p1->dr = p;

p = p1;

Dupa reechilibrare:

fig. 4

Dupa cum se poate observa din fig. 4, dupa reechilibrare factorii de echilibru nu s-au modificat, ci numai referintele, deci trebuie sa restabilim factorii de echilibru:

p->ech = 0;

p1->ech = 0;

fig. 5

Insa trebuie sa remarcam faptul ca odata cu reechilibrarea arborelui de radacina 6 a scazut inaltimea subarborelui stang al nodului cu cheia 8 ( a crescut echilibrul arborelui de radacina 8).

Obs: Acelasi caz de reechilibrare il avem si in situatia in care nodul cu cheia 4 are si subarbore drept:

Fie arborele:

fig. 6

din care dorim sa stergem nodul cu cheia 7:

fig. 7

Si in acest caz, deoarece am sters un nod din subarborele drept, vom avea caz de reechilibrare stanga. Deoarece

p->ech = -1

p1 = p->st

p1->ech = 0

suntem in cazul I st de reechilibrare.

Reechilibrarea se va face exact ca in cazul anterior:

p->st = p1->dr;

p1->dr = p;

p = p1;

Dupa reechilibrare arborele va fi:

fig. 8

Dupa cum se poate observa din fig. 8, dupa reechilibrare factorii de echilibru nu s-au modificat, ci numai referintele, deci trebuie sa restabilim factorii de echilibru:

p->ech = -1;

p1->ech = 1;

fig. 9

In acest caz modificarea NU se propaga mai sus.

Pentru a distinge cele doua cazuri folosim o variabila booleana care ne spune daca s-a modificat inaltimea arborelui in care s-a facut stergerea.

Se observa ca cele doua cazuri pot fi sintetizate intr-un singur caz:

Cazul I stanga de reechilibrare:

Caracterizarea cazului I st: p1 = p->st;

p->ech = -1;

p1->ech <= 0;

Reechilibrarea:    p->st = p1->dr;

p1->dr = p;

Modificarea factorilor de echilibru: if(p1->ech == 0)

else /* p1->ech = -1 */

p = p1;

Suprimarea nodului cu cheia 11:

Din arborele:

fig. 10

dorim sa suprimam nodul cu cheia 11. Cum acesta are doi fii, se va inlocui cu predecesorul sau in inordine, dupa care suprimam nodul cu cheia 10 ce are un singur fiu:

fig. 11

Se constata ca atunci cand factorul de echilibru a lui este 0, dupa suprimare nu e nevoie de reechilibrare si nu se propaga modificarea mai sus.

Suprimarea nodului cu cheia 9:

Din arborele:

fig. 12

dorim sa suprimam nodul cu cheia 9. Dupa suprimare:

fig. 13

In acest caz se impune reechilibrarea arborelui.

Caracteristicile acestui caz de reechilibrare sunt:

p->ech = 1;

p1 = p->dr;

p1->ech = 0;

ne aflam in cazul I dreapta de reechilibrare.

Cazul I dr se rezolva ca si cazul I st, doar ca peste tot referinta stanga se inlocuieste cu dreapta si 1 cu -1 (si invers).

Dupa reechilibrare si modificarea factorilor de echilibru arborele va fi:

fig. 14

Suprimarea nodului cu cheia 8:

Din arborele:

fig. 15

dorim sa suprimam nodul cu cheia 8. Cum nodul de cheie 8 are doi fii, suprimarea sa presupune inlocuirea sa cu nodul de cheie 6 (predecesorul sau in inordine = cel mai din dreapta nod al subarborelui sau stang), dupa care predecesorul sau in inordine se va sterge.

Dupa suprimare si modificarea factorilor de echilibru:

fig. 16

Observam ca nici in acest caz nu este necesara reechilibrarea.

Suprimarea nodului cu cheia 8:

Din arborele:

fig. 17

dorim sa suprimam nodul cu cheia 4. Dupa suprimare arborele devine:

fig. 18

Deoarece p->ech a fost 1, prin stergerea nodului cu cheia 4 reechilibra-re dreapta. Cum

p1 = p->dr;

p1->ech = -1;

rezulta ca suntem in cazul II dreapta de reechilibrare.

Reechilibrarea presupune efectuarea urmatoarelor operatii:

p2 = p1->st;

p1->st = p2->dr;

p->dr = p2->st;

p2->st = p;

p2->dr = p1;

In urma acestor operatii arborele devine:

fig. 19

Dupa cum se poate observa din fig. 19, dupa reechilibrare factorii de echilibru nu s-au modificat, ci numai referintele, deci trebuie sa restabilim factorii de echilibru:

fig. 20

Restabilirea factorilor de echilibru (pe caz general) este urmatoarea:

if(p2->ech == 1)

else if (p2->ech == 0)

else /* p2->ech = -1 */

p2->ech = 0;

p = p2;

Pentru ca am discutat cazul I stanga de reechilibrare, vom discuta cazul II stanga (nu cazul II dreapta, care e prezentat in exemplul anterior)

Cazul II stanga de reechilibrare:

Caracterizarea cazului II st: p->ech = -1;

p1 = p->st;

p1->ech = 1;

Reechilibrarea:    p2 = p1->dr;

p1->dr = p2->st;

p->st = p2->dr;

p2->st = p1;

p2->dr = p;

Modificarea factorilor de echilibru: if(p2->ech == -1)

else if(p2->ech == 0)

else /* p2->ech == 1 */

p2->ech = 0;

p = p2;

Pentru a putea descrie functia care realizeaza suprimarea unui nod al unui arbore binar ordonat AVL astfel incat si dupa suprimarea acelui nod arborele sa ramana binar ordonat si echilibrat (pe care o vom numi suprima_echil) avem nevoie mai intai de 2 functii numite echilibru1 (in cazul in care suprimarea se face in subarborele stang si deci reechilibrarea se impune pe ramura dreapta) si echilibru2 (in cazul in care suprimarea se face in subarborele drept si deci reechilibrarea se impune pe ramura stanga), si de functia suprfd (suprima fiu drept) deoarece nodul de suprimat se va inlocui cu predecesorul sau in inordine (cel mai din dreapta nod al subarborelui sau stang) si apoi avem nevoie sa stergem acest nod (care va avea cel mult un fiu - cel stang).

Functia echilibru2 este urmatoarea:

void echilibru2(ref *p,int *h)

else /* p1->ech = -1 */

(*p)=p1;

}

else /* cazul II st */

else

if(p2->ech==0)

else /* p2->ech = 1 */

p2->ech=0;

(*p)=p2;

} /* cazul II st */

break;

} /*switch*/

} /*echilibru2*/

Functia echilibru1 se va redacta prin simetrie cu functia echilibru2 schimband st cu dr, 1 cu -1 si < cu > (si invers)

Functia suprfd este urmatoarea:

void suprfd (ref *r, int *h, ref *q)

else

} /*suprfd*/

Avand aceste trei functii definite, putem descrie si functia suprima_echil:

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 2 fii */

free(q);

}

} /*suprima_echil*/

Acum este usor sa extindem programul din laboratorul trecut astfel:

Programul:

#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>

#include <conio.h>

#include <graphics.h>

#include <dos.h>

#define CALE 'C:BORLANDCBGI'

#define culoare MAGENTA

#define raza 20

typedef struct nod

Tnod;

typedef Tnod *ref;

ref radacina, r, q;

int x, h, timp=0,

valoare_contor, /* pt a determina daca s-a inserat un nod nou in arbore */

afisare=0, /*pt. cautare*/

er=0; /*pt a determina daca s-a sters un nod din arbore*/

void initializare_mod_grafic(void)

} /*initializare_mod_grafic*/

void creare(void)

h = 0;

insertechil(x, &radacina, &h);

cleardevice();

postordine(radacina, 0, 10, getmaxx(), getmaxx()/2, raza);

gotoxy(1, 25);

if(valoare_contor > 1)

printf('nNodul cu cheia %d era in arbore. Acum valoarea contorului sau este %d', x, valoare_contor);

printf('nMai doriti sa introduceti inca un nod? (D/N): ');

fflush(stdin); scanf('%c', &c); c=toupper(c);

}

printf('Apasati o tastan');

} /* 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 inordine(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*/

void Tip(ref anod, int nivel, int x1, int x2, int c1, int c2, char *s)

setfillstyle(SOLID_FILL, WHITE);

setcolor(BLACK);

sprintf(s, '%d', anod->cheie);

outtextxy((x1+x2)/2, 40*nivel+raza, s);

delay(timp);

} /*Tip*/

ref Loc(int x, ref t)

/* Loc */

void echilibru1(ref *p,int *h)

else

(*p)=p1;

}

else

else

if(p2->ech==0)

else

p2->ech=0;

(*p)=p2;

}

break;

}

} /*echilibru1*/

void echilibru2(ref *p,int *h)

else

(*p)=p1;

}

else

else

if(p2->ech==0)

else

p2->ech=0;

(*p)=p2;

}

break;

} /*switch*/

} /*echilibru2*/

void suprfd (ref *r,int *h, ref *q)

else

} /*suprfd*/

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

free(q);

}

} /*suprima_echil*/ void main(void)

}

creare();

break;

case 'N': cleardevice();

postordine(radacina, 0, 10, getmaxx(), getmaxx()/2, raza);

gotoxy(1, 25);

printf('Introduceti cheia nodului de inserat: ');

while(scanf('%d', &x)!=1)

h = 0;

insertechil(x, &radacina, &h);

cleardevice();

postordine(radacina, 0, 10, getmaxx(), getmaxx()/2, raza);

gotoxy(1, 25);

if(valoare_contor == 1)

printf('nNodul cu cheia %d a fost inserat in arbore', x);

else

printf('nApasati o tasta');

break;

case 'F': if(radacina==NULL)

cleardevice();

postordine(radacina, 0, 10, getmaxx(), getmaxx()/2, raza);

gotoxy(1, 25);

afisare = 0;

printf('Introduceti cheia nodului de cautat: ');

while(scanf('%d', &x) != 1)

r = Loc(x, radacina);

if(r == NULL)

printf('Nodul cu cheia %d nu exista in arbore!n', x);

else

break;

case 'D': if(radacina==NULL)

cleardevice();

postordine(radacina, 0, 10, getmaxx(), getmaxx()/2, raza);

gotoxy(1, 25);

printf('Introduceti cheia nodului pe care doriti sa-l stergeti: ');

while(scanf('%d', &x) != 1)

er=0;

h=0;

suprima_echil(x, &radacina, &h);

cleardevice();

postordine(radacina, 0, 10, getmaxx(), getmaxx()/2, raza);

gotoxy(1, 25);

if(er==1)

printf('Nodul cu cheia %d nu exista in arboren', x);

else

printf('Nodul cu cheia %d a fost sters din arboren', x);

printf('Apasati o tasta');

break;

case 'I': if(radacina==NULL)

printf('Arborele este vidn');

else

printf('Apasati o tasta');

break;

case 'R': if(radacina==NULL)

printf('Arborele este vidn');

else

printf('Apasati o tasta');

break;

case 'S': if(radacina==NULL)

printf('Arborele este vidn');

else

printf('Apasati o tasta');

break;

case 'E': cleardevice();

gotoxy(36,14);

printf('BYE - BYEn');

break;

default: printf('nOptiune invalida!n');

printf('Apasati o tastan');

break;

}

fflush(stdin); getch();

cleardevice();

setbkcolor(BLACK);

gotoxy(2, 1);

} while(op!='E');

closegraph();

} /*main*/

Observatii:

Structura programului nu este modificata fata de laboratorul anterior, deoarece acest program reprezinta de fapt programul din laboratorul anterior cu inca o facilitate adaugata (stergerea unui nod din arbore).

Inainte de a apela functiile de adaugare sau de stergere a unui nod in/din arbore trebuie sa avem grija sa punem pe 0 variabila (cea care ne spune daca s-a modificat inaltimea arborelui in/din care a avut loc inserarea/suprimarea), pentru a efectua corect operatia de reechilibrare a (sub)arborelui.

Pentru a determina in functia main daca s-a efectuat operatia de suprimare a unui nod (stabilirea existentei in arbore a nodului ce se doreste a fi suprimat se face in functia suprima_echil) am folosit un parametru global de eroare er.