ARBORI BINARI DE CAUTARE

ARBORI BINARI DE CAUTARE

Fie A=(V, U) un arbore binar in care fiecare nod contine cel putin un camp informational de un tip ordinal (un tip pe care este definita o relatie de ordine). In acest caz, campul se poate numi camp cheie, iar valorile inscrise in acest camp se numesc chei.

Definitie. Se numeste arbore binar de cautare un arbore binar in care, pentru fiecare nod, se verifica urmatoarele:

orice cheie asociata unui nod din subarborele stang este mai mica
decat cheia asociata nodului;

orice cheie asociata unui nod din subarborele drept este mai mare
decat cheia asociata nodului;

Exemplu: Arborele binar figurat mai jos (pentru care presupunem valorile cheilor ca fiind valorile scrise langa nodurile sale) este arbore binar de cautare, deoarece, pentru orice nod, cheile nodurilor din subarborele stang sunt mai mici decat cheia sa, iar cheile nodurilor din subarborele drept sunt mai mari decat cheia sa.

Operatii principale, care se pot efectua asupra unui arbore binar de cautare, sunt:

crearea arborelui;

adaugarea unui nod la arbore;

cautarea unui nod in arbore;

listarea informatiilor nodurilor arborelui;

stergerea unui nod al arborelui.

Crearea si adaugarea

Crearea unui arbore binar de cautare se face aplicand de un numar de ori operatia de adaugare. De aceea, in continuare, vom prezenta procedura de adaugare, a unui nou nod la un arbore binar de cautare.

Observatie. Presupunem ca dorim sa adaugam un nod cu cheia val (val=valoare), la un arbore de cautare care are radacina c. Acest lucuru se realizeaza folosind procedura Adauga caracterizata astfel:

are doi parametri:

c : reprezinta radacina arborelui in care se face adaugarea;

val : reprezinta cheia nodului care se doreste adaugat; si procedeaza astfel:

- daca nodul c exista (c<>nil):

se compara cheia nodului c cu cheia nodului care se adauga la arbore
(val)

- daca cheia nodului c este egala cu cheia val,

- se afieaza mesajul 'Acest nod a mai fost adaugat'

daca cheia nodului c este mai mica decat val,

se reia procesul de adaugare a nodului in subarborele drept (se
aplica procedura Adauga asupra subarboreli cu radacina c^.dr)

daca cheia nodului c este mai mare decat val,

se reia procesul de adaugare a nodului in subarborele stang;
(se aplica procedura Adauga asupra subarborelui cu radacina

c^.st) altfel

se aloca spatiu pentru noul nod, c;

se incarca informatiile;

se stabilesc legaturile cu descendentii sai, adica:

c^st:=nil; c^dr:=nil;

Exemplu: Sa se creeze un arbore binar de cautare cu cheile:

5, 4, 10, 2, 1, 3, in care radacina are cheia 5.

Rezolvare: Se pornete de la arborele binar de cautare vid. Se adauga nodul cu cheia 5 (la inceput se adauga radacina)

Se adauga nodul 10; cum acesta este mai mare decat 5, se adauga in arborele drept.

Se adauga nodul 2; cum acesta este mai mic decat 5, se adauga in subarborele stang. Deoarece este mai mic decat 4 se adauga in arborele sau stang.

Se adauga nodul 1; cum acesta este mai mic decat 5, se adauga in subarborele stang. Deoarece este mai mic decat 4, se adauga in subarborele sau stang. Deoarece este mai mic decat 2, se adauga in subarborele sau stang.

Se adauga nodul 3; cum acesta este mai mic decat 5, se adauga in subarborele stang. Deoarece este mai mic decat 4, se adauga in subarborele sau stang. Deoarece este mai mare decat 2, se adauga in subarborele sau drept.

In continuare prezentam procedura de adaugare a nodului cu cheia val la arborele binar de cautare cu radacina c.

Procedure adauga(var c : nod; val : integer);

begin

if (c<>nil) then

if (c^.cheie=val) then

write('nodul exista deja')

else if (c^.cheie<val) then

adauga (c^.dr, val)

else

adauga (c^.st, val) else begin

new(c); c^.cheie:=val;

c^.st:=nil; c^.dr=nil;

end;

end;