Scrieti programul C care permite crearea si vizualizarea unui arbore AVL precum si inserarea unui nod de cheie data astfel incat dupa inserare sa ramana tot AVL

Inainte de inserare

Dupa inserare

h_s < h_d p->ech = 1

h_s = h_d p->ech = 0

h_s > h_d p->ech = -1

h_s = h_d p->ech = 1

h_s > h_d p->ech = -1

h_s > h_d p->ech = -2

se cauta in arbore nodul cu cheia de inserat

daca nodul exista in arbore se incrementeaza contorul asociat nodului si algoritmul se opreste, altfel se insereaza in locul determinat la pasul 1

se merge inapoi pe drumul de cautare intre locul de inserat si nodul radacina restabilind in mod corespunzator factorul de echilibru pentru toate nodurile de pe acest drum.

Exemplu:

Se considera arborele:

Cazul I a)

Inserarea nodului de cheie 1

Dupa inserare

Se dezechilibreaza arborele de radacina 8 => se impune reechilibrarea.

p->ech = -1

p1->ech = -1

caracteristicile cazului I a)

Dupa reechilibrare

Dupa reechilibrare factorii de echilibru nu s-au modificat.

Reechilibrare:

p1->st = p1->dr;

p1->dr = p;

Dupa reechilibrare modificam factorii de echilibru ai nodurilor care intervin in reechilibrare (adica *p, *p1).

Restabilirea factorilor de echilibru:

p->ech = 0;

p1->ech = 0;

p = p1;

Cazul I b)

Inserarea nodului de cheie 3

La inserarea nodului de cheie 3 se constata ca se efectueaza aceleasi operatii si deci le putem comasa in cazul I stanga.

Descrierea cazului I stanga

Cazul II a)

Inseram in arborele initial nodul de cheie egala cu 5

Caracteristicile cazului II a)

p1 = p->st;

p2 = p1->dr;

p->ech = -1;

p1->ech = 1;

Arborele se dezechilibreaza si deci se impune reechilibrarea.

Reechilibrarea consta in:

p1->dr = p2->st;

p->st = p2->dr;

p2->st = p1;

p2->dr = p;

p2->ech = -1;

Dupa reechilibrare nu sunt stabiliti factorii de echilibru. Restabilirea factorilor de echilibru consta in:

p->ech = 1;

p1->ech = 0;

Cazul II b)

Inseram in arborele initial nodul de cheie egala cu 7

Dupa inserare factorii de echilibru ai nodurilor nu au fost modificati si mergem inapoi pe drumul de cautare pentru a restabili factorii de echilibru.

p->ech = -1;

p1->ech = 1;

Observam ca sunt aceleasi caracteristici ca in cazul II a).

Arborele se dezechilibreaza si deci se impune reechilibrarea.

Modificarea factorilor de echilibru:

p->ech = 0;

p1->ech = -1;

p = p2;

p->ech = 0;

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

Cazul II c)

Insearea nodului de cheie 6

p->ech = 0;

p1->ech = 0;

p = p2;

p->ech = 0;

Cele 3 cazuri II a), b), c) le putem uni intr-un singur caz: cazul II stanga(S.D.)

Consideram ca p este nodul radacina.

Descrierea cazului II Stanga(S.D.)

p1 = p->st;

p2 = p1->dr;

p->ech = -1;

p1->ech = 1;

p1->dr = p2->st;

p->st = p2->dr;

p2->st = p1;

p2->dr = p;

if(p2->ech==-1)

p->ech = 1;

else p->ech = 0;

if(p2->ech==1)

p->ech = 1;

else p1->ech = 0;

p = p2;

p->ech = 0;

Cazurile I dreapta si II dreapta de reechilibrare(D.D. si D.S.) se trateaza in mod analog prin simetrie inlocuind st cu dr si cu .

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 h a carei valoare de adevar va indica daca a crescut in inaltime subarborele in care s-a facut inserarea.

Functia care realizeaza inserarea cu reechilibrare intr-un arbore AVL este:

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

Observatii:

Informatia care trebuie transmisa la fiecare pas este cea referitoare la modificarea inaltimii subarborelui in care s-a facut insertia.Astfel,in lista de parametri ai functiei,se introduce parametrul variabila de tip boolean h,a carui valoare “adevarat” semnifica cresterea inaltimii subarborelui.

Programul C:

#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>

#include <conio.h>

#include <graphics.h>

#include <dos.h>

#define CALE 'e:BcBGI'

#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 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)

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);

r = NULL;

}/*tiparire grafica*/

ref Loc(int x, ref t)

/*Loc*/

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 'F':

if(radacina==NULL)

afisare = 0;

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

while(scanf('%d', &x)==0)

r = Loc(x, radacina);

if(r == NULL)

printf('Nodul nu exista in arbore!n');

else

break;

case 'I':

if(radacina==NULL)

else

break;

case 'P':

if(radacina==NULL)

else

break;

case 'O':

if(radacina==NULL)

else

break;

case 'E':

break;

default:

printf('nOptiune invalida !nApasati o tasta!n');

getch();

break;

}

}

while(op!='E');

}/*main*/

Document Info

Accesari: 623
Apreciat:

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta

Creaza cont nou