Aceasta structura de date e importanta pentru ca e usor de reprezentat si prelucrat, orice arbore putand fi transformat in arbore binar .
Un arbore generalizat A cu radacina A1 si subarborii A1,1, A1,2, ...,A1,k se transforma in arbore binar avand radacina A1, A1,1 fiul sau stang, iar A1,i devin fiii drepti ai lui A1,i-1 pentru 2<=i<=k.
Secventele de noduri in parcurgerea in preordine a arborelui generalizat si
a celui binar obtinut prin transformare, sunt identice.
Exemplu: Se considera arborele generalizat din figura 1. Aplicand regula descrisa mai sus, se obtine arborele binar din figura.
Varianta a.) O prima implementare se poate realiza printr-un tablou de dimensiune egala cu numarul nodurilor, fiecare intrare avand trei campuri: cheia nodurilor si cate un cursor la fiul stang si drept.
var t : array [1..maxnod] of record
cheie : tip_cheie;
stang,drept : 0..maxnod
end;
Varianta b.) O alta implementare se bazeaza pe doua leme ce se vor preciza mai jos.
Lema1: Numarul maxim de noduri al nivelului i al unui arbore binar este 2i-1. Astfel numarul maxim de noduri al unui arbore binar de inaltime h este 2h-1.
Arborele binar de inaltime h cu exact 2h-1 noduri se numeste arbore binar plin de inaltime h.
Numerotand secvential nodurile unui arbore binar plin de inaltime h, incepand cu nodul radacina (de pe nivelul 1) si continuand nivel cu nivel, de la stanga la dreapta, se poate realiza o implementare eleganta a structurii de arbore, asociind fiecarui nod locatia corespunzatoare numarului sau intr-un tablou liniar:
const nr_noduri={2h-1};
var t : array [1..nr_noduri] of tip_cheie;
Un arbore binar oarecare va pastra numerotarea nodurilor existente, ca intr-un arbore complet.
Lema urmatoare precizeaza maniera simpla in care se poate determina tatal, fiul stang si fiul drept al unui nod precizat.
Lema 2: Pentru un nod oarecare cu indicele i, 1<=i<=n, sunt valabile relatiile:
TATA(i) - e nodul cu indicele [i/2], daca i <> 1;
FIUL_STANG(i) - e nodul cu indicele 2*i daca 2*i <= n;
FIUL_DREPT(i) - e nodul cu indicele 2*i+1 daca 2*i+1 <= n.
Aceasta implementare e avantajoasa doar pentru arbori binari completi, dar dezavantajoasa la insertia sau suprimarea unui nod.
Exemplu: Se considera arborele binar din figura 2. Acesta poate fi
memorat intr-un tablou in forma indicata in figura.
type ref = ^nod;
nod = record
cheie:tip_cheie;
stang,drept:ref
end;
var radacina:ref;
Aceasta implementare e cea mai avantajoasa, inlaturand limitarile
reprezentarii secventiale si utilizand proprietatile recursive ale tipului arbore.
preordine - lista R, A, B
inordine - lista A, R, B
postordine- lista A, B, R.
Cele trei metode de traversare se concretizeaza in trei proceduri recursive in care Prelucrare e operatia ce trebuie facuta asupra fiecarui nod (tipul nod e cel definit mai sus). Se va prezenta procedura Preordine. Algoritmul de parcurgere este acelasi, indiferent de metoda de implementare a arborelui. Diferentele de implementare vor consta in modul de gasire a fiilor nodului curent(fiul stang si drept).
procedure preordine(r:ref);
begin
if r <> nil then
begin
prelucrare(r^);
preordine(r^.stang);
preordine(r^.drept)
end
end;
Urmatoarea parcurgere in inordine permite vizualizarea pe nivele a
arborelui (rotit cu 90 grade spre dreapta ):
procedure tipareste_arbore(r:ref; h:integer);
var i:integer;
begin {tipareste arborele r}
if r<>nil then
with r^ do
begin
tipareste_arbore(stang,h-5);
for i:=1 to h do write(' ');
writeln(cheie);
tipareste_arbore(drept,h-5)
end {with}
end; {tipareste_arbore}
Arborele binar ordonat e arborele binar cu proprietatea ca parcurgand nodurile in inordine, secventa cheilor este monoton crescatoare.
Are proprietatea ca daca un nod oarecare al arborelui are cheia c, toate nodurile din subarborele stang al nodului au cheile mai mici decat valoarea c, respectiv toate cheile din subarborele drept au cheile mai mari sau egale cu c. De aici rezulta procedeul de cautare foarte simplu, prin trecerea la fiul stang sau drept de la nodul curent, functie de relatia dintre cheia cautata si cea a nodului curent.
Cum inaltimea minima a unui arbore binar ordonat cu n noduri este hmin=[log2 (n+1)], rezulta ca o cautare intr-un arbore binar ordonat necesita aproximativ log2n comparatii de chei, fata de n/2 comparatii intr-o lista liniara.
Pentru a cauta un nod cu o cheie data x in cadrul unui arbore binar ordonat, se parcurge arborele, incepand cu radacina, pana la gasirea nodului cautat sau pana la terminarea drumului in arbore. La fiecare nod, se va urma in continuare calea spre fiul stang sau spre cel drept, dupa cum cheia x este mai mica sau mai mare decat cheia nodului curent. Se va returna pointerul spre nodul cu cheia cautata sau nil daca nu s-a gasit o astfel de cheie.
function loc(x:integer;t:ref):ref;
var gasit:boolean;
begin
gasit:=false;
while (t <> nil) and not gasit do
begin
if t^.cheie = x then gasit:=true
else
if t^.cheie < x then t:=t^.stang
else t:=t^.drept
end;
loc:=t
end;
Cautarea se poate simplifica aplicand metoda fanionului, modificand
structurile arborelui astfel incat orice referinta nil se inlocuieste cu cea spre
nodul fanion. inainte de inceperea cautarii, cheia nodului fanion se asigneaza cu
valoarea cautata x, astfel incat va exista in arbore cel putin un nod cu acea cheie.
var fanion:ref;
function loc1(x:integer;t:ref):ref;
begin
fanion^.cheie:=x;
while t^.cheie <> x do
if x < t^.cheie then t:=t^.stang
else t:=t^.drept;
loc1:=t
end;
Faptul ca valoarea cautata x exista in arbore e indicat de o valoare
returnata de functia loc1 diferita de fanion.
Procesul de creare consta in insertia cate unui nod intr-un arbore binar ordonat, care initial este vid, astfel incat dupa insertie el sa ramana ordonat.
Pentru aceasta se traverseaza arborele incepand cu radacina si se selecteaza fiul stang sau drept, dupa cum cheia de inserat e mai mica sau mai mare decat a nodului parcurs. Se repeta pana cand se ajunge la un pointer nil care se inlocuieste cu pointerul spre noul nod creat. Pentru ca sortarea sa fie stabila, se trece la fiul drept chiar daca valoarea cheii e egala.
procedure inarbior(x:integer; var t:ref);
begin
if t <> nil then
if x < t^.cheie then inarbior(x,t^.stang)
else inarbior(x,t^.drept)
else { t = nil }
begin
new(t);
with t^ do begin
cheie:=x;
stang:=nil;
drept:=nil
end { with }
end
end;
In urma suprimarii unui nod avand cheia x dintr-un arbore binar ordonat, acesta trebuie sa ramana ordonat.
Cazurile ce se disting sunt functie de numarul de fii ai nodului ce se suprima. Daca numarul fiilor este:
cel mult unu - referinta spre nodul de suprimat se inlocuieste cu referinta spre
unicul sau fiu ( sau nil daca nodul e terminal );
doi fii
Se numeste arbore binar total echilibrat (sau perfect echilibrat), un arbore in care, pentru fiecare nod, numarul nodurilor din subarborele sau stang difera cel mult cu unu de cel al nodurilor subarborelui drept. In consecinta, toate nodurile terminale ale unui asemenea arbore sunt pe ultimele doua nivele.
Avand secventa ordonata crescator a celor n noduri ale arborelui ( cea care se va obtine la parcurgerea in inordine ), construirea ABO total echilibrat se realizeaza prin urmatorul algoritm recursiv: