Page 42 - MATINF Nr. 1

42 C. B˘alc˘au

Urm˘atorul rezultat prezint˘a o metod˘a general˘a pentru rezolvarea acestei relat , ii de recurent , ˘a.

Teorema 1 (Teorema Master [3]). Fie T : N → R + o funct ,ie ce verific˘a relat ,ia de recurent ,˘a
(1), sub ipotezele s , i convent ,iile de mai sus.

c
Cazul 1. Dac˘a f(n) = O (n ), cu c < log a, atunci T(n) = Θ(n log a ).
b
b
k
c
Cazul 2. Dac˘a f(n) = Θ(n log n), cu c = log a s , i k ≥ 0, atunci T(n) = Θ(n log a log k+1 n).
b
2
b
2
c
Cazul 3. Dac˘a f(n) = Ω(n ), cu c > log a, s , i exist˘a k < 1 s , i n 1 ∈ N astfel ˆıncˆat
b
af(n/b) ≤ kf(n) ∀ n ≥ n 1 , atunci T(n) = Θ(f(n)).
Propriet˘at , i ale arborilor binari strict , i
Deoarece terminologia ˆın tematica arborilor nu este unificat˘a, definim not , iunile pe care le vom
utiliza ˆın continuare.

Definit , ia 6. Un arbore binar este un arbore cu r˘ad˘acin˘a, reprezentat pe nivele, ˆın care fiecare
nod x are cel mult doi descendent , i (fii, succesori direct ,i), situat ,i pe nivelul urm˘ator, s , i anume
(cel mult) un descendent stˆang, situat ˆın stˆanga lui x, s , i (cel mult) un descendent drept,
situat ˆın dreapta lui x, contˆand ordinea dintre aces , tia. Nodurile cu cel put ,in un descendent se
numesc interne (interioare), iar nodurile f˘ar˘a descendent ,i se numesc externe (exterioare,
frunze).

Definit , ia 7. Fie T = (V, F) un arbore binar avˆand r˘ad˘acina r, r ∈ V .

a) Not˘am cu I(T) mult , imea nodurilor interne s , i cu E(T) mult , imea nodurilor ex-
terne ale arborelui binar T.

b) Pentru orice nod x ∈ V , distant , a de la nodul r˘ad˘acin˘a r la nodul x, notat˘a cu
D T (x) = D(x), reprezint˘a lungimea lant ,ului elementar unic de la r la x.

c) Num˘arul h(T) = max{D T (x) | x ∈ V } se numes , te ˆın˘alt , imea arborelui binar T.

Observat ,ia 2. Fie T = (V, F) un arbore binar. Evident, avem V = I(T)∪E(T), I(T)∩E(T) = Ø,
E(T) 6= Ø s , i h(T) = max{D T (x) | x ∈ E(T)}. Deci h(T) = k − 1, unde k reprezint˘a num˘arul
de nivele ale arborelui T.

Dac˘a nivelul pe care este reprezentat˘a r˘ad˘acina arborelui este numerotat cu 0, atunci pentru
orice nod x ∈ V avem D T (x) = num˘arul nivelului pe care este situat nodul x, iar ˆın˘alt , imea
arborelui T este egal˘a cu num˘arul ultimului nivel al arborelui.

Definit , ia 8. Un arbore binar strict este un arbore binar pentru care orice nod intern are
exact doi descendent ,i (s , i anume un descendent stˆang s , i un descendent drept).

Propozit , ia 2. Orice arbore binar strict cu n noduri interne, n ∈ N, are n + 1 noduri externe.

Demonstrat¸ie. Demonstr˘am afirmat , ia din enunt , prin induct , ie dup˘a n.

Pentru n = 0 este evident c˘a arborele este format doar din nodul r˘ad˘acin˘a, deci are un singur
nod s , i acesta este extern.

Presupunem afirmat , ia adev˘arat˘a pentru n − 1 s , i o demonstr˘am pentru n, n ≥ 1. Fie
T = (V, F) un arbore binar strict cu n noduri interne. Fie x un nod intern al lui T situat pe