ARBORI BINARI DE CAUTARE

GRUP SCOLAR "IOAN BUTEANU"

SOMCUTA MARE

ARBORI BINARI DE CAUTARE

Introducere in teoria arborilor

Programatorii folosesc,de multe ori, prin abuz de limbaj , termenul de arbore , in loc de

arborescenta. In astfel de cazuri, se specifica radacina, care se mai numeste si varf si se

considera ca sensul arcelor este implicit, motiv pentru care nu se mai reprezinta grafic.

Se numeste arborescenta un graf orientat care indeplineste simultan doua conditii: este

arbore . Intr-o arborescenta radacina este unica. Daca de exemplu ,exista doua radacini v1 si v2

atunci exista drum de la v1 la v2 si de la v2 la v1. Aceasta presupune un ciclu deci nu este

arbore. De regula, atunci cand se da o arborescenta sa precizeaza radacina sa. Din radacina

pleaca arce. Daca ar si intra s-ar obtine un ciclu.

In cazul in care arborescenta are cel mult doi descendenti, unul stang si unul drept,

facundu-se abstractie de sunsul sagetilor, spunem ca avem un arbore binar. Vom face distinctie

intre subarborele stang si subarborele drept. Intr-un arbore binar nodurile sunt asezate pe mai

multe niveluri. Radacina este pe nivelul 0, descendentii directi ai radacinii sunt pe nivelul 1,

descendentii directi ai nodurilor de pe nivelul 1 sunt pe nivelul 2 etc. . Numarul de nivelui mai

putin cel al radacinii, ocupate de nodurile grafului, se numaste adancimea arborelui binar.

Se numeste arbore binar de cautare un arbore binar ale carui noduri au o cheie de identificare,

iar pentru fiecare nod avem proprietatile urmatoare:

-orice cheie asociata unui nod al subarborelui stang este mai mica decat cheia asociata nodului

-orice cheie asociata unui nod al subarborelui drept este mai mare decat cheia asociata nodului

Arborii binari de cautare sunt structuri de date care suporta un set de operatii

dinamice cum ar fi: cautare , succesor , predecesor , minim , maxim , inserare sau stergere.

Timpul in care operatiile de baza ,intr-n arbore binar de cautare, sunt rezolvate ,este direct

proportional cu adancimea arborelui. Cazul cel mai defavorabil apare in momentul cand avem

un arbore binar complet cu n noduri sau arborele este reprezentat printr-un lant de n noduri. In

aceste doua cazuri avem cel mai slab timp de executie a operatiilor destinate acestei structuri.

Un arbore binar de cautare , dupa cum sugereaza si numele, este organizat intr-un

arbore binar ca si in figura de mai jos. Asemenea arbore poate fi reprezentat ca si o structura de

date inlantuita in care fiecare nod este un obiect. Fiecare nod contine cate un camp care

reprezinta adresa catre subarborele stang respectiv subarborele drept. Daca acest subarbore

lipseste , campul se va referi la o variabila presetata NIL care arata absenta acestuia.

Formularea problemei

Fiind dat intr-un fisier o succesiune de noduri sa se preia intr-un arbore binar de

cautare si sa se intocmeasca un program cu care sa se poata adauga, sterge sau cauta o

cheie in arborele binar, creat in functie de optiunea utilizatolului. De asemenea programul

va trebui sa includa modalitatile de parcurgere a arborilor binari de cautare si o afisare a

arborelui in model grafic

Prezentarea problemei:

Pentru a realiza programul si a-i oferi o interfata cat mai atractiva am apelat la

modul grafic. Pentru a rula sunt necesare fisierele grafice uzuale situate in folder-ul Bgi al

mediului Turbo Pascal. Se poate folosi programul si prin intermediul fisierului executabil.

Programul in sine se compune din doua unit-uri "binar.pas", "grafica.pas" si programul

principal "proiect.pas".

In unitul "binar.pas" sunt descrise principalele functii si procedure folosite de

catre programul principal si apelate in interiorul lui iar in unitul "grafica.pas" sunt descrise

principalele proceduri prin care am dat programului o interata grafica foarte prietenoasa cu

utilizatorul si foarte usor de folosit, utilizatorul trebuind doar sa urmeze niste mesaje data de

catre program si sa aleaga optiunea dorita dintr-un meniu afisat pe "desktop-ul" programului.

Crearea arborelui

procedure creare(var vf:adr;rad:integer);

begin

new(vf);

vf^.inf:=rad;

vf^.st:=nil;

vf^.dr:=nil; end;

Arborele binar se va crea cu un singur nod care va reprezenta radacina.Ulterior vom insera

noduri in arbore exact in pozitia corespunzatoare .

Inserarea unei chei in arbore

procedure inserare(var vf:adr;cheie:integer);

var nou:adr;

begin

if vf<>nil then begin

if cheie<vf^.inf then inserare(vf^.st,cheie);

if cheie>vf^.inf then inserare(vf^.dr,cheie);

end

else

begin

new(vf);

vf^.inf:=cheie;

vf^.st:=nil;

vf^.dr:=nil;

end;

end;

Regula de inserare este urmatoarea: se compara cheia asociata unui nod cu cheia inregistrarii

care se insereaza. Avem trei posibilitati:

- cheia coincide cu numarul si renuntam la inserarea acelui numar;

- cheia este mai mare decat numarul si se incearca inserarea in subarborele drept;

- cheia este mai mica decat numarul si se incearca inserarea in subarborele stang;

Cautarea unei chei :

procedure caut(vf:adr;cheie:integer;var gasit:boolean);

begin

if vf<>nil then

if vf^.inf=cheie then gasit:=true

else begin

if cheie<vf^.inf then caut (vf^.st,cheie,gasit);

if cheie>vf^.inf then caut (vf^.dr,cheie,gasit);

end

else gasit:=false;

end;

Aceasta procedura va returna programului principar o variabila booleana care va returna true

daca cheia a fost gasita in arbore sau false in caz contrar. Principiul de functionare este exact ca

si cel al insearii: se compara cheia cu radacina, daca coincid procedura se termina,in caz contrar

daca cheia este mai mica decat radacina se cauta in subarborele stang respectiv daca este mai

mare se cauta in subarborele drept.

Stergerea informatiei :

procedure cmdd(var r,vf:adr);

var el:adr;

begin

if vf^.dr<>nil then

cmdd(r,vf^.dr)

else begin

r^.inf:=vf^.inf;

el:=vf;

vf:=vf^.st;

dispose(el);

end;

end;

procedure sterg(var r:adr;cheie:integer;var sters:boolean);

var el:adr;

begin

if r=nil then sters:=false

else

if r^.inf<cheie then sterg(r^.dr,cheie,sters)

else

if r^.inf>cheie then sterg(r^.st,cheie,sters)

else

if (r^.st=nil) and (r^.dr=nil) then begin

el:=r;

dispose(el);

r:=nil;

end

else if (r^.st=nil) and (r^.dr<>nil) then begin

el:=r;

r:=r^.dr;

dispose(el);

end

else if (r^.st<>nil) and (r^.dr=nil) then begin

el:=r;

r:=r^.st;

dispose(el);

end

else cmdd(r,r^.st);

end;

Dupa stergerea unui nod care are o anumita cheie, arborele trebuie sa ramana tot de cautare

Se disting 4 situatii posibile:

nodul care urmeaza a fi sters este nod terminal si in acest caz se face stergerea avnd

grija ca la parintele lui sa inlocuim adresa catre el cu NIL

- nodul care urmeaza a fi sters subordoneaza un singur arbore drept, caz in care parintelui

i se va inlocui adresa catre el cu adresa subarborelui drept, iar nodul respectiv se sterge

- nodul care urmeaza a fi sters subordoneaza un singur arbore stang, caz in care parintelui

i se va inlocui adresa catre el cu adresa subarborelui stang, iar nodul respectiv se sterge

nodul care urmeaza a fi sters subordoneaza doi arbori, caz in care nodul va fi sters logic si

se vor efectua urmatoarele operatii: se identifica cel mai din dreapta nod al subarborelui

stang corespunzator nodului care va fi sters(acesta va fi sters in mod efectiv , nu inainte de a

muta informatia sa in nodul care se sterge logic- procedura cmdd) ; cheia acestuia si alte

informatii utile continute de el se muta la nodul care urmeaza a fi sters ; subarborele stang al

nodului care se va sterge fizic se leaga: in stanga nodului care se sterge logic(daca nodul

identificat ca cel mai din dreapta din subarborele stang este descendent direct al nodului care se

sterge logic) , in dreapta tatalui nodului care se sterge fizic in caz contrar.

Afisarea arborelui in model grafic

procedure afis_arbore_nod(val:integer;rad:adr;h,nr,x,y:integer);

var s:string;

x0:integer;

begin

setcolor(white);

x0:=(640 div (nr_elem(h)+1))*(nr+1);

line(x,y+5,x0,h*30+10);

if rad=nil then

begin

setcolor(lightgreen);

line(x0-3,h*30+10,x0+3,h*30+10);

end

else begin

if rad^.inf=val then setcolor(lightblue)

else setcolor(white);

circle(x0+3,h*30+18,7);

setcolor(red);

str(rad^.inf,s);

if rad^.inf>=10 then

outtextxy(x0-3,h*30+15,s)

else outtextxy(x0,h*30+15,s);

afis_arbore_nod(val,rad^.st,h+1,2*nr,x0,h*30+20);

afis_arbore_nod(val,rad^.dr,h+1,2*nr+1,x0,h*30+20);

end;

end;

Aceasta procedura are la baza parcurgerea unui arbore in inordine. Variabilele folosite

au urmatoarea semnificatie: rad-adresa nodului parcurs la un moment dat, h-nivelul nodului , nr-

nr nodului(pe orizontala) , x,y coordonatele nodului parinte(de la acesta trebuie legat cu linie).

Se calculeaza pozitia noului nod, interesandu -ne doar pe axa OX deoarece pa axa OY intervine

doar nivelul. In acest moment se traseaza o linie de la nodul parinte iar daca am ajuns la NIL se

traseaza o linie orizontala, in caz contrar se traseaza un cerc. Dupa care se apeleaza procedura

pentru subarborele stang , pozitia nodului radacina devenind pozitia nodului curent. Numarul de

noduri din stanga se dubleaza iar nivelul creste cu o unitate. Acelasi lucru se face si prin

apelarea procedurii pentr subarborele drept.

Modalitati de parcurgere:

procedure preordine(vf:adr);

begin

if vf<>nil then begin

afis_arbore_nod(vf^.inf,aux,1,0,320,0);

delay(7000);

str(vf^.inf,s);

inc(nrnod);

setcolor(lightblue);

outtextxy(10+nrnod*20,420,s+' ');

preordine(vf^.st);

preordine(vf^.dr);

end;

end;

procedure inordine(vf:adr);

begin

if vf<>nil then begin

inordine(vf^.st);

str(vf^.inf,s);

inc(nrnod);

setcolor(lightblue);

outtextxy(10+nrnod*20,420,s+' ');

afis_arbore_nod(vf^.inf,aux,1,0,320,0);

delay(7000);

inordine(vf^.dr);

end;

end;

procedure postordine(vf:adr);

begin

if vf<>nil then begin

postordine(vf^.st);

postordine(vf^.dr);

str(vf^.inf,s);

inc(nrnod);

setcolor(lightblue);

outtextxy(10+nrnod*20,420,s+' ');

afis_arbore_nod(vf^.inf,aux,1,0,320,0);

delay(7000);

end;

end;

Parcurgerea in preordine- are la baza tot afisarea arborelui in model grafic.Se parcurge mai

intai varful dupa care se afiseaza arborele marcandu-se locul in care suntem prin colorarea

cercului respectiv din arbore cu o alta culoare.Se afiseaza pe ecran informatia din nodul in care

ne aflam. Dupa care se apeleaza pentru subarborele stang respectiv subarborele drept

Parcurgerea in inordine- are la baza tot afisarea arborelui in model grafic.Se parcurge mai

intai subarborele stang, dupa care se afiseaza arborele marcandu-se locul in care suntem prin

colorarea cercului respectiv din arbore cu o alta culoare.Se afiseaza pe ecran informatia din

nodul in care ne aflam. Dupa care se apeleaza procedura pentru subarborele drept

Parcurgerea in postordine- se parcurge mai intai subarborele stang, apoi subarborele drept

apoi varful dupa care se afiseaza arborele marcandu-se locul in care suntem prin

colorarea cercului respectiv din arbore cu o alta culoare.Se afiseaza pe ecran informatia din

nodul in care ne aflam.

Alte proceduri care mai apar in unit-ul "binar.pas" sunt acelea de citire a unui arbore din

fisier, utilizatorul avand posibilitatea de a alege unul dintre cele 4 fisiere presetate, in progam la

optiunea corespunzatoare, fiindu-i afisat continutul fiecarui fisier. De asemenea mai apare o

procedura care preia ora din sistem prin procedura implementata automat in mediul de

programare Borland Pascal - gettime si o afiseaza pe "desktop-ul" programului.

In unit-ul "grafica.pas" sunt descrise toate procedurile, prin care interfata programului

devine din ce in ce mai prietenoasa cu utilizatorul, cum ar fi procedura de trasare a "desktop-

ului" sau procedura care apare in interiorul optiunii "1" , care ne arata continutul fiecarui fisier

din care se poate crea arborele. De asemenea mai apare si o procedura care ia data din sistem si

o afiseaza pe ecran in mod text (ex. vineri 25 iunie 2005) .

In programul principal sunt apelate procedurile desrise in cele doua unit-uri,

acestea fiind apelate de catre utilizator alegand una din optiuniile dorite. De asemenea

utilizatorului ii este cerut sa introduca calea directorului "BGI" din care este initializat modul

grafic prin procedura "initgraph".

Per ansamblu algoritmul nu este foarte greu de inteles si profita in mare parte de avantajele puse la dispozitie mediul Turbo Pascal fiind totodata ingradit si de limitarile pe care mediul amintit le prezinta.

Bibliografie

1.Tudor Sorin

Manual pentru clasa a XI-a , varianta Pascal, Ed. L&S Info-mat

2. Geoge Daniel Mateescu, Pavel Florin Moraru

Manual pentru clasa a XI-a, varianta Pascal, Ed. Niculescu

3. Cormen Book