Scrieti programul C care permite crearea si vizualizarea sub forma naturala a unui arbore AVL

ARBORI ECHILIBRATI AVL

Tema nr. 2:

Scrieti programul C care permite crearea si vizualizarea sub forma naturala a unui arbore AVL.

Analiza:

Intrucat algoritmii de inserare si suprimare intr-un arbore binar ordonat se complica in cazul in care am dori sa pastram si caracteristica de arbore perfect echilibrat, Adelson, Velskii si Landis au propus niste conditii mai simple, si anume ca arborele binar ordonat sa nu mai fie perfect echilibrat, ci numai echilibrat dupa inaltime.

Obs: Ar fi fost indicat sa se mentina caracteristica de arbore binar ordonat perfect echilibrat, deoarece pentru astfel de structuri de date cautarea unui nod de cheie data presupune un numar de cautari de ordinul lui .

Def Vom spune ca un arbore binar este echilibrat dupa inaltime (in continuare vom spune simplu ca este echilibrat) daca pentru fiecare nod al arborelui diferenta de inaltime intre cei doi subarbori ai sai este cel mult 1.

Din definitie rezulta ca orice subarbore al unui arbore echilibrat dupa inaltime este si el echilibrat dupa inaltime.

Din modul in care am definit arborii perfect echilibrati (vezi lab. 1) rezulta ca un arbore perfect echilibrat este si echilibrat dupa inaltime. (Reciproca nu este adevarata). Asadar arborii perfect echilibrati sunt cazuri particulare de arbori echilibrati.

Exemplu:

Sa consideram arborele din fig. 1. Acesta este perfect echilibrat si echilibrat dupa inaltime. In schimb arborele din fig. 2 este doar echilibrat dupa inaltime, dar nu este perfect echilibrat pentru ca nodul cu cheia 7 are in subarborele stang 6 noduri, iar in subarborele drept 4 noduri ( diferenta dintre numarul de noduri este mai mare decat 1), insa inaltimea subarborelui stang al nodului cu cheia 7 este 2 iar inaltimea subarborelui drept al acestuia este tot 2 ( diferenta este 0 este echilibrat dupa inaltime)

fig. 1

fig. 2

Def Un arbore binar echilibrat dupa inaltime se mai numeste si arbore AVL (dupa initialele numelor celor de i-au definit).

In continuare vom lucra cu arbori binari ordonati echilibrati (vom pastra structura de arbore binar ordonat pentru a folosi facilitatile oferite in cadrul procesului de cautare).

Adelson, Velskii si Landis au demonstra ca inaltimea unui arbore binar ordonat echilibrat cu noduri creste cu cel mult 45% fata de inaltimea unui arbore binar ordonat perfect echilibrat cu acelasi numar de noduri. Rezulta ca nu se modifica substantial lungimea drumului de cautare, iar ordinul de complexitate al cautarii este tot de ordinul .

Structura de date care va descrie un arbore binar ordonat echilibrat (AVL) este cea care reprezinta structura de arbore binar cu referinte multiple, descrisa in cursurile precedente (adica pentru fiecare nod al arborelui vom considera informatia si referintele spre subarborii st si dr), insa in acest caz stuctura unui nod mai trebuie sa scoata in evidenta si diferenta de inaltime intre cei doi subarbori:

typedef struct nod

Tnod;

typedef Tnod *ref;

ref radacina, r, q;

Inserarea unui nod intr-un arbore AVL:

Sa consideram arborele din fig. 3:

fig. 3

Acesta este un arbore AVL, iar daca vreau sa inserez in acesta nodul cu cheia 9 sau 11:

fig. 4 fig. 5

aceasta nu va modifica cu nimic atributul de arbore echilibrat al arborelui initial.

In schimb daca doresc sa inserez nodul cu cheia 1, 3, 5 sau 7:

   

fig. 6 fig. 7

   

fig. 8 fig. 9

astfel incat arborele sa ramana binar si ordonat, arborele de radacina 8 se dezechilibreaza pentru ca subarborele sau stang va avea inaltimea 2 iar subarborele sau drept are inaltimea 0 (deci diferenta intre inaltimile celor doi subarbori este mai mare decat 1) si in acest caz se impune reechilibrarea arborelui.

Pentru a stabili in program cand se impune reechilibrarea si in ce caz de reechilibrare suntem, vom introduce notiunea de factor de echilibru al unui nod, intelegand prin aceasta diferenta dintre inaltimea subarborelui drept si cea a subarborelui stang al nodului, dar nu si invers.

Vom nota cu variabila pointer ce indica radacina arborelui ce va trebui reechilibrat.

Daca notam cu radacina arborelui in care se va face inserarea, cu subarborele sau stang, si cu subarborele sau drept, si presupunem pentru inceput ca inserarea unui nou nod se va face in , cu indicatia ca (inaltimea subarborelui ) va creste cu 1, cazurile ce pot sa apara depind de cum erau si inainte de inserare:

In toate cele trei cazuri inserarea unui nod in se va face dupa aceleasi principii ca si la arborii binari ordonati, numai ca in cazul al treilea mai trebuie sa realizam reechilibrarea arborelui.

Pentru a stabili cazurile de reechilibrare, sa consideram arborele din fig. 3, precizand si factorii de echilibru ai nodurilor:

fig. 10

In acest arbore vom insera pe rand nodurile cu cheile 1, 3, 5 si 7 astfel incat sa se pastreze structura de arbore binar ordonat (cautam in arborele dat sa vedem daca nodul nu exista deja, adica traversam arborele incepand cu radacina si selectam fiul stang sau fiul drept al nodului curent, dupa cum cheia nodului cautat este mai mica, respectiv mai mare decat cheia nodului curent, determinandu-se astfel si locul de inserat, daca nodul cu cheia cautata nu exista in arbore), rezultand urmatoarele cazuri de reechilibrare:

Cazul I st a) (S. S. st)

Dorim sa inseram nodul cu cheia 1:

fig. 11

Dupa inserarea acestui nod se impune reechilibrarea arborelui.

La traversarea in inordine a arborelui obtinut dupa inserarea nodului cu cheia 1, secventa cheilor va fi: 1, 2, 4, 6, 8, 10. Reechilibrarea arborelui va trebui sa o facem astfel incat sa se mentina secventa monoton crescatoare a cheilor nodurilor la traversarea in inordine.

Notam cu variabila pointer ce indica adresa radacinii arborelui si cu variabila pointer care indica adresa radacinii subarborelui sau stang. Pentru a realiza reechilibrarea arborelui, vom face nodul de adresa radacina, iar pentru ca la traversarea in inordine secventa cheilor sa se pastreze, subarborele drept al nodului de adresa trebuie sa devina fiu stang al nodului indicat de variabila pointer :

fig. 12

Pentru ca in momentul in care s-a realizat inserarea (inainte de reechilibra-re) se cunoaste doar valoarea lui (adresa nodului radacina), secventa C care va realiza reechilibrarea arborelui asa cum am dedus din cele de mai sus va fi urmatoarea:

p1 = p->st;

p->st = p1->dr;

p1->dr = p;

p = p1;

Insa, asa cum se poate observa din fig. 12, dupa reechilibrare factorii de echilibru raman nemodificati! Dar in urma procesului de reechilibrare se modifica factorii de echilibru, deci trebuie facuta o modificare a acestora:

fig. 13

p->ech = 0;

p = p1;

p->ech = 0;

Din cele de mai sus rezulta ca operatiile ce trebuiesc efectuate in cazul I st a) sunt urmatoarele:

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

p->ech = -1;

p1->ech = -1;

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

p1->dr = p;

Modificarea factorilor de echilibru: p->ech = 0;

p = p1;

p->ech = 0;

Cazul I st b) (S. S. dr)

In arborele din fig. 3 dorim sa inseram nodul cu cheia 3:

fig. 14

Si in acest caz vom face nodul de adresa nod radacina. De asemenea, exact ca si in cazul precedent, subarborele drept al nodului de adresa trebuie sa devina subarbore stang al nodului de adresa :

fig. 15

operatiile necesare reechilibrarii fiind:

p1 = p->st;

p->st = p1->dr;

p1->dr = p;

Cum in urma acestor operatii arborele va fi AVL, insa factorii de echilibru nu s-au modificat, deoarece s-a schimbat structura arborelui trebuie sa modificam si factorii de echilibru care nu mai corespund realitatii:

fig. 16

p->ech = 0;

p = p1;

p->ech = 0;

Se constata ca in cazurile I st a) si b) avem aceleasi caracterizari ale cazu-lui de reechilibrare, se efectueaza aceleasi operatii de reechilibrare si factorii de echilibru se modifica la fel. Prin urmare putem reuni cele doua cazuri in Cazul I st:

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

p->ech = -1;

p1->ech = -1;

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

p1->dr = p;

Modificarea factorilor de echilibru: p->ech = 0;

p = p1;

p->ech = 0;

Cazul II st a) (S. D. st)

In arborele din fig. 3 dorim sa inseram nodul cu cheia 5:

fig. 17

Dupa inserarea acestui nod se impune reechilibrarea arborelui.

La traversarea in inordine a arborelui obtinut dupa inserarea nodului cu cheia 5, secventa cheilor va fi: 2, 4, 5, 6, 8, 10. Reechilibrarea arborelui va trebui sa o facem astfel incat sa se mentina secventa monoton crescatoare a cheilor nodurilor la traversarea in inordine.

Notam cu variabila pointer ce indica adresa radacinii arborelui, cu variabila pointer care indica adresa radacinii subarborelui sau stang si cu variabila pointer care contine adresa radacinii subarborelui drept al acestuia din urma. Pentru a realiza reechilibrarea arborelui, vom urca nodul intre si , facandu-l nod radacina. Pentru ca la traversarea in inordine secventa cheilor sa se pastreze, subarborele stang al lui trebuie sa devina subarbore drept al lui si referinta stanga a lui trebuie sa devina NULL (practic pentru a face acest lucru, modific referinta stanga a lui astfel incat sa fie egala cu referinta dreapta a lui ):

fig. 18

Pentru ca in momentul in care s-a realizat inserarea (inainte de reechilibra-re) se cunoaste doar valoarea lui (adresa nodului radacina), secventa C care va realiza reechilibrarea arborelui asa cum am dedus din cele de mai sus va fi urmatoarea:

p1 = p->st;

p2 = p1->dr;

p1->dr = p2->st;

p->st = p2->dr;

p2->st = p1;

p2->dr = p;

p = p2;

Insa, asa cum se poate observa din fig. 18, dupa reechilibrare factorii de echilibru raman nemodificati! Dar in urma procesului de reechilibrare se modifica factorii de echilibru, deci trebuie facuta o modificare a acestora:

fig. 19

p->ech = 1;

p1->ech = 0;

p = p2;

p->ech = 0;

Din cele de mai sus rezulta ca operatiile ce trebuiesc efectuate in cazul II st a sunt urmatoarele:

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

p1 = p->st;

p1->ech = 1;

p2 = p1->dr;

p2->ech = -1;

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

p->st = p2->dr;

p2->st = p1;

p2->dr = p;

Modificarea factorilor de echilibru: p->ech = 1;

p1->ech = 0;

p = p2;

p->ech = 0;

Cazul II st b) (S. D. dr)

In arborele din fig. 3 dorim sa inseram nodul cu cheia 7:

fig. 20

Dupa inserarea acestui nod se impune reechilibrarea arborelui.

La traversarea in inordine a arborelui obtinut dupa inserarea nodului cu cheia 7, secventa cheilor va fi: 2, 4, 6, 7, 8, 10. Reechilibrarea arborelui va trebui sa o facem astfel incat sa se mentina secventa monoton crescatoare a cheilor nodurilor la traversarea in inordine.

Ca si in cazul precedent, notam cu variabila pointer ce indica adresa radacinii arborelui, cu variabila pointer care indica adresa radacinii subarborelui sau stang si cu variabila pointer care contine adresa radacinii subarborelui drept al acestuia din urma. Pentru a realiza reechilibrarea arborelui, vom urca nodul intre si , facandu-l nod radacina. Pentru ca la traversarea in inordine secventa cheilor sa se pastreze, subarborele drept al lui trebuie sa devina subarbore stang al lui si referinta stanga a lui trebuie sa devina NULL (practic pentru a face acest lucru, modific referinta dreapta a lui astfel incat sa fie egala cu referinta stanga a lui ):

fig. 21

Pentru ca in momentul in care s-a realizat inserarea (inainte de reechilibra-re) se cunoaste doar valoarea lui (adresa nodului radacina), secventa C care va realiza reechilibrarea arborelui asa cum am dedus din cele de mai sus va fi urmatoarea:

p1 = p->st;

p2 = p1->dr;

p1->dr = p2->st;

p->st = p2->dr;

p2->st = p1;

p2->dr = p;

p = p2;

Observam ca este exact aceeasi secventa de instructiuni ca si in cazul II st a). Mai mult, pentru ca, asa cum se poate observa din fig. 21, dupa reechilibrare si in acest caz factorii de echilibru raman nemodificati! Dar in urma procesului de reechilibrare se modifica factorii de echilibru, deci trebuie facuta o modificare a acestora:

fig. 22

p->ech = 0;

p1->ech = -1;

p = p2;

p->ech = 0;

Din cele de mai sus rezulta ca operatiile ce trebuiesc efectuate in cazul II st b) sunt urmatoarele:

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

p1 = p->st;

p1->ech = 1;

p2 = p1->dr;

p2->ech = 1;

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

p->st = p2->dr;

p2->st = p1;

p2->dr = p;

Modificarea factorilor de echilibru: p->ech = 0;

p1->ech = -1;

p = p2;

p->ech = 0;

Comparand cazul II st a) cu cazul II st b) rezulta ca se fac aceleasi operatii pentru reechilibrare exceptand doar factorii de echilibru ai nodurilor , , care se restabilesc in functie de factorul de echilibru al lui .

Cazul II st c)

Sa presupunem ca avem urmatorul arbore:

fig. 23

in care dorim sa inseram nodul cu cheia 6:

fig. 24

Dupa reechilibrare:

fig. 25

Si dupa modificarea factorilor de echilibru:

fig. 26

Din cele de mai sus rezulta ca operatiile ce trebuiesc efectuate in cazul II st c) sunt urmatoarele:

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: p->ech = 0;

p1->ech = 0;

p = p2;

p->ech = 0;

Observam ca putem reuni cazurile II st a), b) si c) in Cazul II st cu caracteristicile:

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

p1 = p->st;

p1->ech = 1;

p2 = p1->dr;

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

p->st = p2->dr;

p2->st = p1;

p2->dr = p;

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

p->ech = 1;

else p->ech = 0;

if(p2->ech == 1)

p1->ech = -1;

else p1->ech = 0;

p = p2;

p->ech = 0;

Obs: Daca inserarea unui nod se va face in subarborele drept al radacinii arborelui, vom distinge tot 2 cazuri de inserare cu reechilibrare, care vor fi tratate in mod analog prin simetrie, schimband peste tot 1 cu -1 si st cu dr (si invers).

La fiecare pas al algoritmului de inserare trebuie sa transmitem informatia daca a crescut sau nu in inaltime subarborele in care s-a facut inserarea. In acest sens vom folosi o variabila de tip boolean a carei valoare de adevar va indica daca a crescut in inaltime subarborele in care s-a facut inserarea.

Conform celor discutate mai sus, functia care va realiza inserarea unui nod intr-un arbore AVL ordonat, astfel incat dupa inserarea acestuia arborele sa ramana tot AVL si ordonat este urmatoarea:

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

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

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)

}

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 '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*/

} /* Loc */

Observatii:

Se observa ca este modificata structura nodurilor arborelui fata de laboratorul precedent. Daca despre campul ech am vorbit, campul contor este folositor in cazul unor probleme asemanatoare problemei concordantei. Acest camp ne permite (spre deosebire de arborii din laboratorul anterior) sa nu avem in arbore mai multe noduri cu aceeasi cheie, astfel daca se doreste introducerea in arbore a unui nod cu o cheie care mai exista in arbore se va incrementa contorul asociat nodului respectiv. Pentru a arata ca se intampla acest lucru am folosit o variabila globala valoare_contor pe care o folosim in cadrul functiilor de creare a arborelui si de inserare a unui nod.

Deoarece arborele este reprezentat sub forma naturala se poate imbunatati si functia de cautare. Astfel putem "marca" un nod pe care il cautam (daca exista) in arbore, nu numai sa precizam daca exista sau nu. Pentru aceasta vom folosi o variabila globala afisare care va fi 1 in momentul in care am gasit nodul in arbore si foloseste in "marcarea" grafica a nodului cautat (in functia de tiparire a nodurilor arborelui). Insa trebuie sa fim atenti sa punem pe 0 acesta variabila inainte de a parasi ramura corespunzatoare cautarii din switch deoarece in caz contrar nodul pe care l-am cautat va fi marcat la fiecare afisare a arborelui pana la o noua cautare a unui nod in arbore.

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

Daca dorim sa manipulam un arbore AVL concret o sa introducem nodurile pe nivele (in acest caz sigur nu va avea loc reechilibrarea arborelui, deci nu se vor "muta" nodurile).