LICEUL TEORETIC CU PROFIL DE ARTE”MIHAIL BEREZOVSCHI”

DISCIPLINA:Informatica

TITLUL REFERATULUI:”Arbori binari”

Profesor: Mihai Gandrabura

Elevă:Ceban Cristina

O clasă foarte importantă de arbori cu rădăcină o constituie arborii binari. Un arbore binar este un arbore cu rădăcină în care gradul oricărui vârf este cel mult egal cu doi. Putem defini recursiv arborii  binari astfel :DefiniţieUn arbore binar este un arbore care fie este vid fie constă din constă dintr-un nod rădăcină şi doi arbori binari disjuncţi numiţi subarborele stâng, respectiv subarborele drept.Se face o distincţie clară între subarborele drept şi cel stâng. Dacă subarborele stâng este nevid, rădăcina lui se numeşte fiul stâng al rădăcinii..Analog, dacă subarborele drept este nevid, rădăcina lui se numeşte fiul drept al rădăcinii.

Clase de arbori binari:

1. Arbori binari stricţi sunt arborii binari în care orice vârf are gradul zero (este terminal ) sau doi (are exact doi fii).

2. 2. Arbori binari plini sunt arbori binari care au 2k-1 vârfuri dispuse pe nivelurile 0, 1, ... , k-1, astfel încât pe fiecare nivel i se găsesc 2i vârfuri.

3. Arborii binari compleţi sunt arbori binari care se obţin dintr-un arbore binar plin prin eliminarea din dreapta către stânga a unor noduri de pe ultimul nivel. Mai exact, pentru a construi un arbore binar complet cu n noduri, determinăm k astfel încât 2k n < 2k1 k log2n.Construim arborele binar plin cu 2k1-1 noduri şi eliminăm de pe ultimul nivel nodurile 2k1-1, 2k1-2, ..., n1

4. . Arbori binari degeneraţi- sunt arbori binari cu n vârfuri dispuse pe n niveluri. 5. Arbori binari echilibraţi - sunt arbori binari în care, pentru orice nod, numărul nodurilor

din subarborele drept şi numărul nodurilor din subarborele stâng diferă cu cel mult o unitate

Proprietăţi ale arborilor binari

Proprietatea 1.

Numărul maxim de noduri de pe nivelul i al unui arbore binar este 2i.

Demonstraţie:

Vom proceda prin inducţie după numărul nivelului.

P(0) Pe nivelul i 0 se găseşte un singur nod (rădăcina).

P(k) Presupunem că numărul maxim de noduri de pe nivelul k este

2k.

P(k1) Vom demonstra că pe nivelul k1 sunt cel mult 2k1 noduri.

Pe nivelul k1 se găsesc fiii nodurilor de pe nivelul k. Din ipoteza inductivă, pe nivelul k se găsesc cel mult 2k noduri, iar fiecare nod poate avea cel mult doi fii, deci pe nivelul k1 se găsesc cel mult 2*2k 2k1 noduri.

Proprietatea 2.

Numărul maxim de noduri într-un arbore cu înălţimea h este 2h1-1.

Demonstraţie:

Numărul maxim de noduri într-un arbore cu înălţimea h se obţine atunci când fiecare nivel i este plin, deci, conform propoziţiei anterioare, conţine 2i noduri. Numărul maxim de noduri într-un arbore cu înălţimea h va fi:

Proprietatea 3.

În orice arbore binar nevid cu n0 noduri terminale există n0-1 noduri de grad 2.

Demonstraţie:

Notăm cu n0 numărul de noduri terminale, cu n1 numărul de noduri de grad 1 şi cu n2

numărul de noduri de grad 2. Deci, numărul total de noduri nn0n1n2.

Dacă numărăm muchiile dintr-un arbore binar, observăm că fiecare nod, cu excepţia rădăcinii, are o singură muchie orientată spre el. Notând m numărul de muchii obţinem n m1. Dar orice muchie provine de la un nod de grad 1 sau 2, rezultă că m n12n2.

Din n0n1n2 n şi n12n2 n-1 n2 n0-1.

Proprietatea 4.

Un arbore cu n vârfuri are înălţimea cel puţin egală cu log2n.

Demonstraţie:

În cazul cel mai favorabil, nodurile sunt dispuse pe niveluri astfel încât fiecare nivel să fie plin, cu excepţia, eventuală, a ultimului nivel. Deci arborele binar cu n noduri de înălţime minimă este arborele binar complet cu n vârfuri, care, din modul de construcţie, are înălţimea log2n.

Proprietatea 5.

Definim lungimea drumurilor interne (I) ca fiind suma lungimilor drumurilor de la rădăcină la noduri neterminale (interne) şi lungimea drumurilor externe (E) ca fiind suma lungimilor drumurilor de la rădăcină la noduri terminale (frunză sau externe). Într-un arbore binar cu n noduri interne, E I2n.

Demonstraţie:

Vom proceda prin inducţie după n, numărul nodurilor interne.

P(0) Într-un arbore cu 0 noduri interne (vid sau format numai din rădăcină) E I 0.

P(n-1) Presupunem că într-un arbore binar An-1, cu n-1 noduri interne, are loc relaţia En-1 In-

12(n-1).

P(n) Vom demonstra că într-un arbore binar An, cu n noduri interne, are loc relaţia En In2n.

Fie An un arbore binar cu n noduri interne. Există în An un nod intern x care are drept fii două noduri terminale. Îndepărtând din An fiii nodului x, nodul x se transformă în nod terminal, deci obţinem un arbore An-1 cu n-1 noduri interne. Din propoziţia inductivă rezultă că în arborele A n-1, En-1 In-12(n-1). Dacă notăm cu d, lungimea drumului de la rădăcină la nodurile eliminate, obţinem relaţiile :

En En-12d-(d-1) (în An nodurile eliminate sunt terminale, dar nodul x nu, lungimea drumului de la rădăcină la x fiind d-1).

In In-1(d-1) (în An nodul x este intern).

Deci En In-12(n-1)d1 In-d12n-2d1 In2n.

Reprezentarea arborilor

Reprezentarea cu referinţe descendente

Pentru fiecare nod din arbore vom reţine informaţia asociată nodului şi referinţe către fiii săi. Dacă presupunem că gradul oricărui nod este cel mult egal cu n, putem reprezenta referinţele spre fii printr-un vector cu n componente.

Structura unui nod va fi :

Informaţie Fiu1 Fiu2 ...... Fiun

Declararea acestei structuri în secţiunea type în limbajul Pascal este :

Arbore ^NodArbore;

NodArbore record

Inf: TipInformaţie;

Fiu: array1..NrMaxFii of Arbore;

end;

Într-o astfel de reprezentare risipa de memorie este foarte mare, în fiecare nod alocăm memorie pentru numărul maxim de referinţe către fii. În plus, numărul maxim de fii este, în general, necunoscut. Acest neajuns ar putea fi eliminat folosind în locul vectorului de referinţe

(cu număr a priori fixat de componente) o listă simplu înlănţuită în care să reţinem toţi fiii nodului respectiv.

Declararea acestei structuri în secţiunea type în limbajul Pascal va fi :

ListaFii ^Fiu;

Fiu record

F: Arbore;

Urm: ListaFii;

end;

Arbore ^Nod Arbore;

NodArbore record

Inf: TipInformaţie;

Ref: ListaFii;

end;

Reprezentarea cu referinţe ascendente

În această reprezentare, pentru fiecare nod din graf reţinem pe lângă informaţia aferentă, o legătură spre nodul părinte.

Arbore ^NodArbore;

NodArbore record

Inf: TipInformaţie;

Tata: Arbore;

end;

Mai simplu, putem utiliza doi vectori în care pentru fiecare nod reţinem informaţia, respectiv nodul părinte. Această reprezentare este mai compactă, dar pentru a avea acces la toate nodurile arborelui trebuie să reţinem toate nodurile terminale. O astfel de reprezentare este utilă pentru reprezentarea mulţimilor disjuncte cu ajutorul arborilor şi o rezolvare eficientă a problemelor de reuniune a două mulţimi şi de determinare a mulţimii căreia îi aparţine un element dat.

Reprezentarea Fiu-Frate.

Pentru fiecare nod reţinem fiul cel mai din stânga şi fratele lui din dreapta cel mai apropiat.

Arbore ^NodArbore;

NodArbore record

Inf: TipInformaţie;

FiuSt, FrateDr: Arbore;

end;

Reprezentarea arborilor binari

. Reprezentarea înlănţuită.

În această reprezentare, pentru fiecare nod reţinem, pe lângă informaţia asociată nodului, rădăcina subarborelui stâng, rădăcina subarborelui drept şi dacă este necesar, părintele nodului respectiv.

ArboreBinar ^NodArboreBinar;

NodArboreBinar record

c: TipInformaţie;

st, dr, părinte: ArboreBinar;

end;

Arborele binar va fi referit prin intermediul rădăcinii.

Reprezentarea secvenţială.

Pentru fiecare nod reţinem într-un vector doar informaţia asociată nodului, legăturile dintre noduri fiind implicite. Acest tip de reprezentare este convenabil pentru arbori binari compleţi. Pentru aceasta, vom numerota nodurile astfel :

- rădăcina este numerotată cu 1.

- cele 2i noduri de pe nivelul i sunt numerotate 2i, 2i1, ... , 2i1-1 de la stânga la dreapta(i > 0).

- pe ultimul nivel nodurile sunt numerotate până la n, numărul de noduri din arbore.

Această numerotare ne permite să deducem legăturile existente între nodurile arborelui.

Operaţii elementare pe arbori binari

Crearea unui arbore binar.

Algoritmul de creare depinde în mod esenţial de tipul arborelui binar pe care dorim să-l construim. Vom prezenta o procedură de creare a unui arbore binar echilibrat, alţi algoritmi de creare fiind prezentaţi în capitolele următoare. Pentru a crea un arbore binar echilibrat cu n vârfuri se stabileşte un vârf rădăcină, se construieşte un arbore binar echilibrat cu n/2 vârfuri ca subarbore stâng şi un arbore binar echilibrat cu n-1-n/2 vârfuri ca subarbore drept. Dacă n este par numărul nodurilor din subarborele stâng va fi cu o unitate mai mare decât numărul nodurilor din subarborele drept, altfel cei doi subarbori au un număr egal de noduri.

function CreareArboreBinarEchilibrat(n: byte): ArboreBinar;

// funcţia întoarce adresa rădăcinii unui arbore binar echilibrat cu n //vârfuri

var rad: ArboreBinar;

begin

if n 0 then //arborele este vid

CreareArboreBinarEchilibrat : nil

else

begin

new(rad) //aloc zonă de memorie pentru rădăcina arborelui

readln(rad^.Inf);//citesc informaţia rădăcinii arborelui

// creez subarborele stâng, apoi cel drept

rad^. St : CreareArboreBinarEchilibrat(n div 2);

rad^. Dr : CreareArboreBinarEchilibrat(n - n div 2 -1 );

CreareArboreBinarEchilibrat : rad

end

end;

Parcurgerea arborilor binari

Parcurgerile sunt cele mai frecvent utilizate operaţii pe arbori. A parcurge un arbore înseamnă a vizita fiecare nod al arborelui o singură dată, în scopul prelucrării informaţiei asociate nodului.

Există mai multe posibilităţi de parcurgere a arborilor- în adâncime (preordine, inordine, postordine) sau pe niveluri, dar în toate cazurile atât arborele, cât şi subarborii sunt prelucraţi în acelaşi mod.

a) Parcurgerile în adâncime

În toate cele trei tipuri de parcurgere în adâncime se vizitează mai întâi subarborele stâng, apoi subarborele drept. Diferenţa constă în poziţia rădăcinii faţă de cei doi subarbori. Fie scrise recursiv, fie iterativ, procedurile de parcurgere în adâncime necesită o stivă.

Pentru a parcurge un arbore binar în preordine, se vizitează mai întâi rădăcina, se parcurge în preordine subarborele stâng, apoi se parcurge în preordine subarborele drept.

procedure Preordine(rad: ArboreBinar);

begin

if rad nil then

begin

write(rad^.inf); //vizitez rădăcina

Preordine(rad^.st); //parcurg subarborele stâng

Preordine(rad^.dr); //parcurg subarborele drept

end;

end;

Pentru a parcurge în inordine un arbore binar, se parcurge în inordine subarborele stâng, se vizitează radăcina, apoi se parcurge în inordine subarborele drept.

procedure Inordine(rad: ArboreBinar);

begin

if rad nil then

begin

Inordine(rad^.st);

write(rad^.inf);

Inordine(rad^.dr);

end;

end;

Pentru a parcurge în postordine un arbore binar, se parcurge în postordine subarborele stâng, apoi cel drept, apoi se vizitează rădăcina.

procedure Postordine(rad: ArboreBinar);

begin

if rad nil then

begin

Postordine(rad^.st);

Postordine(rad^.dr);

write(rad^.inf);

end;

end;

Pentru a înţelege mai bine operaţia de parcurgere, vom prezenta şi o variantă iterativă de parcurgere în inordine a unui arbore binar.

Pentru a simula recursia vom folosi o stivă S la care vom adăuga sau şterge elemente în acelaşi mod ca în procedura recursivă.

Stivă ^NodStivă;

NodStivă record

Inf: ArboreBinar;

Urm: Stivă;

end;

procedure InordineIterativ (rad: ArboreBinar);

// procedura parcurge iterativ în inordine arborele cu rădăcina rad

var S, p: Stivă;

NodCurent: ArboreBinar;

begin

S : nil;

NodCurent : rad;

repeat

while NodCurent nil do

begin

//adaugă nodul curent în stiva S

new(p)

p^.Inf : NodCurent;

p^.Urm : S;

S : p;

//rădăcina subarborelui stâng devine nod curent

NodCurent : NodCurent^.St

if S nil then //extrage un element din stivă

begin

p : S;

S : S^.Urm;

write(p^.inf)

NodCurent : p^.Inf^.Dr

dispose(p);

//eliberează zona de memorie a lui p

until (S nil) and (NodCurent nil)

end;

Observaţie

Fiecare nod din arbore este plasat şi şters din stivă o singură dată, deci timpul necesar parcurgerii inordine este de O(n). Spaţiul suplimentar necesar depinde de înălţimea arborelui, deci în cazul cel mai defavorabil este de O(n).

b) Parcurgerea pe niveluri

Se vizitează întâi rădăcina, apoi fiul stâng al rădăcinii, apoi cel drept şi se continuă în acest mod vizitând nodurile de pe fiecare nivel de la stânga la dreapta.

Pentru a realiza acest mod de parcurgere, vom utiliza o coadă, pe care o iniţializăm cu rădăcina arborelui şi din care, la fiecare pas, vom extrage un nod, îl vizităm şi inserăm în coadă fii săi, dacă aceştia există.

Coadă ^NodCoadă;

NodCoadă record

Inf: ArboreBinar;

Urm: Coadă;

end;

procedure ParcurgerePeNiveluri (rad: ArboreBinar)

//procedura parcurge pe niveluri arborele cu rădăcina rad

var C, SfC, p: Coadă;

begin

if rad nil then //arborele este nevid

begin

new(C) // iniţializez coada cu rădăcina arborelui

C^.Inf : rad;

C^.Urm : nil;

SfC : C;

while C nil do // coada nu este vidă

begin

p : C;

write(p^.Inf);

if p^.Inf^.St nil then begin

//adaug fiul stâng în coadă

new(q);

q^.Inf : p^.Inf^.St;

q^.Urm : nil;

SfC^.Urm : q;

SfC : q;

end;

if p^.Inf^.Dr nil then

begin //adaug fiul drept în coadă

new(q);

q^.Inf : p^.Inf^.Dr;

q^.Urm : nil;

SfC^.Urm : q;

SfC : q;

end;

C : C^.Urm //extrag din coadă nodul p

dispose(p);

end

end

end;

Observaţie

Mai întâi am inserat în coadă fiii nodului ce urmează a fi vizitat şi apoi am extras efectiv nodul respectiv din coadă, pentru a evita inserarea unui nod într–o coadă vidă.

Determinarea înălţimii unui arbore.

Dacă arborele este vid, vom considera că înălţimea sa este –1, astfel putem calcula înălţimea arborelui ca fiind maximul dintre înălţimile subarborilor rădăcinii plus nivelul pe care se află rădăcina.

function Înălţime (rad: ArboreBinar): integer;

// funcţia întoarce înălţimea arborelui binar cu rădăcina rad

begin

if rad nil then // arbore vid

Înălţime : –1

else

Înălţime : max(Înălţime(rad^.st), Înălţime(rad^.dr))1

end;

Am presupus cunoscută funcţia max, care întoarce cel mai mare dintre cele două argumente ale sale.

Egalitatea a doi arbori binari.

Spunem că doi arbori binari sînt egali dacă au aceeaşi structură şi conţin aceleaşi informaţii în nodurile corespondente.

function Egali (rad1, rad2: ArboreBinar): boolean;

//funcţia întoarce true dacă arborii cu rădăcinile rad1,

// respectiv rad2 sunt egali, altfel întoarce false

begin

Egali : (rad1 nil) and (rad2 nil) //ambii sunt vizi sau

or (rad1 nil) and (rad2 nil) // ambii sunt nevizi şi

and (rad1^.c rad2^.c) //au aceeaşi informaţie în rădăcină

and Egali(rad1^.St, rad2^.St) //subarborii stângi egali

and Egali(rad1^.Dr, rad2^.Dr) // subarborii drepţi egali

end;