Scrieti programul C care va permite crearea unui arbore AVL dat si vizualizarea acestuia sub forma naturala

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

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 -1 cu 1.

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 Insert_Echil(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

} /* Insert_Echil */

Rezolvare:

Realizati programul C care permite crearea si vizualizarea 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 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)

}/*InordineS*/

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

Document Info

Accesari: 515
Apreciat:

Comenteaza documentul:

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

Creaza cont nou