7/24/2019 5b1 a b Stricti Th Avl (2)

1/36

7/24/2019 5b1 a b Stricti Th Avl (2)

2/36

Reamintim urmatoarele proprietati pentru unarbore binar strict T:NE(T) (sau NE) = numarul de frunze ale lui T;NI(T) (sau NI) = numarul de noduri interne ale lui T;LE(T) (sau LE) = lungimea externa a lui T;LI(T) (sau LI) = lungimea interna a lui T;

abs 2012 2 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

3/36

Reamintim urmatoarele proprietati pentru unarbore binar strict T:NE(T) (sau NE) = numarul de frunze ale lui T;NI(T) (sau NI) = numarul de noduri interne ale lui T;LE(T) (sau LE) = lungimea externa a lui T;LI(T) (sau LI) = lungimea interna a lui T;

Propozitie 1:

In oricare a.b.s. T avem relatia:

NE =NI+ 1.

abs 2012 2 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

4/36

Reamintim urmatoarele proprietati pentru unarbore binar strict T:NE(T) (sau NE) = numarul de frunze ale lui T;NI(T) (sau NI) = numarul de noduri interne ale lui T;LE(T) (sau LE) = lungimea externa a lui T;LI(T) (sau LI) = lungimea interna a lui T;

Propozitie 1:

In oricare a.b.s. T avem relatia:

NE =NI+ 1.

Propozitie 2:In oricare a.b.s. T avem relatia:

LE =LI+ 2NI.

abs 2012 2 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

5/36

Propozitie 3:

In oricare a.b. oarecare T de naltime h(T) =d avem relatia:

NE 2d.

abs 2012 3 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

6/36

Propozitie 3:

In oricare a.b. oarecare T de naltime h(T) =d avem relatia:

NE 2d.

Corolar 1:

In oricare a.b. oarecare T de naltime h(T) =d avem relatia:

d log2NE.

abs 2012 3 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

7/36

Propozitie 3:

In oricare a.b. oarecare T de naltime h(T) =d avem relatia:

NE 2d.

Corolar 1:

In oricare a.b. oarecare T de naltime h(T) =d avem relatia:

d log2NE.

Propozitie 4:

In familia a.b. stricti cu numar de frunze fixat, NE, lungimea externa

minima se atinge pentru aceia care au frunzele repartizate pe cel mult

doua niveluri adiacente.

abs 2012 3 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

8/36

Propozitie 5:Lungimea externa minima a unui a.b.s. cu NE frunze este:

LminE =NElog2NE + 2(NE 2log2NE).

abs 2012 4 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

9/36

Propozitie 5:Lungimea externa minima a unui a.b.s. cu NE frunze este:

LminE =NElog2NE + 2(NE 2log2NE).

Din Demonstratie:Daca d=h(T)= naltimea unui a.b.s. T pe care se atinge lungimea externa minima, avem 2cazuri (cf. Prop. 4):

abs 2012 4 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

10/36

Propozitie 5:Lungimea externa minima a unui a.b.s. cu NE frunze este:

LminE =NElog2NE + 2(NE 2log2NE).

Din Demonstratie:Daca d=h(T)= naltimea unui a.b.s. T pe care se atinge lungimea externa minima, avem 2cazuri (cf. Prop. 4):

Cazul (a)

Toate frunzele sunt la acelasi nivel, d=h(T), daca NE = 2d.

abs 2012 4 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

11/36

Propozitie 5:Lungimea externa minima a unui a.b.s. cu NE frunze este:

LminE =NElog2NE + 2(NE 2log2NE).

Din Demonstratie:Daca d=h(T)= naltimea unui a.b.s. T pe care se atinge lungimea externa minima, avem 2cazuri (cf. Prop. 4):

Cazul (a)

Toate frunzele sunt la acelasi nivel, d=h(T), daca NE = 2d.

Cazul (b)

Frunzele nu sunt toate la acelasi nivel. Dar atunci ele sunt repartizate doar pe nivelurile d 1(fie ynr. de frunze de la acest nivel), si d (fie 2xnr. de frunze de la acest nivel, x= nr. de

noduri interne de la nivelul d 1).Se rezolva sistemul:

x+y= 2d1 (1)x+y= NE (2)

Avem:

nr. de frunze la nivelul d 1 =y= 2d NE,

nr. de frunze la nivelul d= 2x= 2NE 2d

.abs 2012 4 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

12/36

Propozitie 6:

Intr-un a.b.s. lungimea externa medie LmedieE = LE

NEare marginea

inferioaraLmedieE log2NE.

abs 2012 5 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

13/36

Teorema AVL

Teorema AVL:

Margine superioara si margine inferioara pentru naltimea unui arbore binarechilibrat AVL

abs 2012 6 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

14/36

Teorema AVL

Teorema AVL:

Margine superioara si margine inferioara pentru naltimea unui arbore binar

echilibrat AVL

Fie T un arbore binar strict si echilibrat AVL, cu n noduri interne. Fie

h(T) naltimea lui. Avem:

log2(n+ 1)h(T)1.4404log2(n+ 2)0.328.

abs 2012 6 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

15/36

Teorema AVL

Teorema AVL:

Margine superioara si margine inferioara pentru naltimea unui arbore binar

echilibrat AVL

Fie T un arbore binar strict si echilibrat AVL, cu n noduri interne. Fie

h(T) naltimea lui. Avem:

log2(n+ 1)h(T)1.4404log2(n+ 2)0.328.Mai precis: sunt satisfacute urmatoarele inegalitati:

(1) In orice arbore binar cu n noduri, avem

h(T)log2(n+ 1).

(2) In orice arbore binar strict si echilibrat AVL, cu n noduri interne, avem

h(T)

(1/log2)log2(n+ 2) + (log25/2log2

2)

abs 2012 6 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

16/36

Teorema AVL

Teorema AVL:

Margine superioara si margine inferioara pentru naltimea unui arbore binar

echilibrat AVL

Demonstratie:

abs 2012 6 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

17/36

Teorema AVL

Teorema AVL:

Margine superioara si margine inferioara pentru naltimea unui arbore binar

echilibrat AVL

Demonstratie:

Inegalitatea (1) este adevarata pentru a.b.s. n general (rezulta din Corolarul laProp. 3), si se poate demonstra direct pentru a.b. oarecari din n

numarul

maxim de noduri la naltime data h.

abs 2012 6 / 10

AVL

7/24/2019 5b1 a b Stricti Th Avl (2)

18/36

Teorema AVL

Teorema AVL:

Margine superioara si margine inferioara pentru naltimea unui arbore binar

echilibrat AVL

Demonstratie:

Inegalitatea (1) este adevarata pentru a.b.s. n general (rezulta din Corolarul laProp. 3), si se poate demonstra direct pentru a.b. oarecari din n

numarul

maxim de noduri la naltime data h.Pentru a dem. ineg. (2) construim o clasa particulara de a.b.s. si echil. AVL,arborii Fibonacci.

abs 2012 6 / 10

T AVL

7/24/2019 5b1 a b Stricti Th Avl (2)

19/36

Teorema AVL

Teorema AVL:

Margine superioara si margine inferioara pentru naltimea unui arbore binar

echilibrat AVL

Demonstratie:

Inegalitatea (1) este adevarata pentru a.b.s. n general (rezulta din Corolarul laProp. 3), si se poate demonstra direct pentru a.b. oarecari din n

numarul

maxim de noduri la naltime data h.Pentru a dem. ineg. (2) construim o clasa particulara de a.b.s. si echil. AVL,arborii Fibonacci.

Numerele Fibonacci (de ordinul 1)

F1 =F2 = 1 si relatia de recurenta Fn+2=Fn+1+Fn, pentru n1.

abs 2012 6 / 10

T AVL

7/24/2019 5b1 a b Stricti Th Avl (2)

20/36

Teorema AVL

Teorema AVL:

Margine superioara si margine inferioara pentru naltimea unui arbore binar

echilibrat AVL

Demonstratie:

Inegalitatea (1) este adevarata pentru a.b.s. n general (rezulta din Corolarul laProp. 3), si se poate demonstra direct pentru a.b. oarecari din n

numarul

maxim de noduri la naltime data h.Pentru a dem. ineg. (2) construim o clasa particulara de a.b.s. si echil. AVL,arborii Fibonacci.

Numerele Fibonacci (de ordinul 1)

F1 =F2 = 1 si relatia de recurenta Fn+2=Fn+1+Fn, pentru n1.

Formula Binet pentru numere Fibonacci

Fn = (1/

5)(n n), unde = (1 + 5)/2.

abs 2012 6 / 10

D t ti

7/24/2019 5b1 a b Stricti Th Avl (2)

21/36

Demonstratie:

Construim prin recurenta familia de arbori binari (FTk)k0, FTk= ArboreFibonacci (Fib Tree) de ordin k.

abs 2012 7 / 10

Demonstratie

7/24/2019 5b1 a b Stricti Th Avl (2)

22/36

Demonstratie:

Construim prin recurenta familia de arbori binari (FTk)k0, FTk= ArboreFibonacci (Fib Tree) de ordin k.

FT0

F1

1

FT1

F2

1

FT2

F3

2

FT3

F4

3

FT4

F5

5

FTk2

FTk1

. . . FTk

. . . Fk+1

. . . Fk1 + Fk

abs 2012 7 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

23/36

Lema 1:

Pentru orice k 0 arborele FTkeste a.b.s.

abs 2012 8 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

24/36

Lema 1:

Pentru orice k 0 arborele FTkeste a.b.s.

Lema 2:Pentru orice k 1 arborele FTk are caracteristicile:

(a) h(FTk) = k

1.

(b) NE(FTk) =Fk+1.

(c) NI(FTk) =Fk+1 1.

abs 2012 8 / 10

Lema 1:

7/24/2019 5b1 a b Stricti Th Avl (2)

25/36

Lema 1:Pentru orice k 0 arborele FTkeste a.b.s.

Lema 2:

Pentru orice k 1 arborele FTk are caracteristicile:(a) h(FTk) = k 1.(b) NE(FTk) =Fk+1.

(c) NI(FTk) =Fk+1 1.

Demonstratie:Este suficient sa demonstram (a) si (b), (c) este consecinta a lui (b) prin Prop 1.Inductie dupa k, k 1.k= 1: FT1 este ... cu h(FT1) = 0 si NE(FT1) = 1 =F2.Pp. (a) si (b) adev. pentru FTm, orice m

7/24/2019 5b1 a b Stricti Th Avl (2)

26/36

Lema 1:

Pentru orice k 0 arborele FTkeste a.b.s.

Lema 2:Pentru orice k 1 arborele FTk are caracteristicile:

(a) h(FTk) = k

1.

(b) NE(FTk) =Fk+1.

(c) NI(FTk) =Fk+1 1.

Lema 3:

Pentru orice k 0 arborele FTkeste echilibrat AVL.

abs 2012 8 / 10

7/24/2019 5b1 a b Stricti Th Avl (2)

27/36

Lema 1:Pentru orice k 0 arborele FTkeste a.b.s.

Lema 2:Pentru orice k 1 arborele FTk are caracteristicile:

(a) h(FTk) = k 1.(b) NE(FTk) =Fk+1.

(c) NI(FTk) =Fk+1 1.

Lema 3:Pentru orice k 0 arborele FTkeste echilibrat AVL.

Demonstratie:Pt. k= 0, 1, 2 direct. Pt. k 3, (inductie), de dem. in nodul radacina se fol. (a) din Lema 2.

abs 2012 8 / 10

Lema 4:

7/24/2019 5b1 a b Stricti Th Avl (2)

28/36

Lema 4:

In familia arborilor binari stricti si echilibrati AVL de naltime data, h,

arborii Fibonacci au numar minim de noduri interne.

abs 2012 9 / 10

Lema 4:

7/24/2019 5b1 a b Stricti Th Avl (2)

29/36

Lema 4:

In familia arborilor binari stricti si echilibrati AVL de naltime data, h,

arborii Fibonacci au numar minim de noduri interne.

Demonstratie: Inductie dupa hh= 0. Singurii a.b.Fib. ... au NI = 0.h= 1. T1= a.b.s. de naltime 1 si nr minim de noduri interne, are 1 nod intern (radacina) si 2frunze, i.e. T1 =FT2.

abs 2012 9 / 10

Lema 4:

7/24/2019 5b1 a b Stricti Th Avl (2)

30/36

In familia arborilor binari stricti si echilibrati AVL de naltime data, h,

arborii Fibonacci au numar minim de noduri interne.

Demonstratie: Inductie dupa hh= 0. Singurii a.b.Fib. ... au NI = 0.h= 1. T1= a.b.s. de naltime 1 si nr minim de noduri interne, are 1 nod intern (radacina) si 2frunze, i.e. T1 =FT2.Notam cu Th un a.b.s. si echil. AVL de naltime h care are nr. minim de noduri interne.Ipot. inductie: pentru orice k, k< h avem Tk =FTk

+1.

h oarecare, h 2: fie Th ca mai sus. Are nod rad. cu fii left(Th) si right(Th). Putem pp. cah(left(Th)) > h(right(Th)).

abs 2012 9 / 10

Lema 4:

7/24/2019 5b1 a b Stricti Th Avl (2)

31/36

In familia arborilor binari stricti si echilibrati AVL de naltime data, h,

arborii Fibonacci au numar minim de noduri interne.

Demonstratie: Inductie dupa hh= 0. Singurii a.b.Fib. ... au NI = 0.h= 1. T1= a.b.s. de naltime 1 si nr minim de noduri interne, are 1 nod intern (radacina) si 2frunze, i.e. T1 =FT2.Notam cu Th un a.b.s. si echil. AVL de naltime h care are nr. minim de noduri interne.Ipot. inductie: pentru orice k, k< h avem Tk =FTk+1.h oarecare, h 2: fie Th ca mai sus. Are nod rad. cu fii left(Th) si right(Th). Putem pp. cah(left(Th)) > h(right(Th)).Avem:

(i) h(left(Th)) = h 1 si NI(left(Th)) minim, deci left(Th) = Th1.(ii) h(right(Th)) = h 2 si NI(right(Th)) minim, deci right(Th) = Th2.

Dar, cf. ipot. ind., Th1 =FTh si Th2 = FTh1, deci, din (i) left(Th) = FTh si din (ii)right(Th) = FTh1, din care rezulta ca Th =FTh+1.

abs 2012 9 / 10

Lema 4:

7/24/2019 5b1 a b Stricti Th Avl (2)

32/36

In familia arborilor binari stricti si echilibrati AVL de naltime data, h,

arborii Fibonacci au numar minim de noduri interne.

Demonstratie: Inductie dupa hh= 0. Singurii a.b.Fib. ... au NI = 0.h= 1. T1= a.b.s. de naltime 1 si nr minim de noduri interne, are 1 nod intern (radacina) si 2frunze, i.e. T1 =FT2.Notam cu Th un a.b.s. si echil. AVL de naltime h care are nr. minim de noduri interne.Ipot. inductie: pentru orice k, k< h avem Tk =FTk+1.h oarecare, h 2: fie Th ca mai sus. Are nod rad. cu fii left(Th) si right(Th). Putem pp. cah(left(Th)) > h(right(Th)).Avem:

(i) h(left(Th)) = h 1 si NI(left(Th)) minim, deci left(Th) = Th1.(ii) h(right(Th)) = h 2 si NI(right(Th)) minim, deci right(Th) = Th2.

Dar, cf. ipot. ind., Th1 =FTh si Th2 = FTh1, deci, din (i) left(Th) = FTh si din (ii)right(Th) = FTh1, din care rezulta ca Th =FTh+1.

Observatie:Cf. Lemei 1 nr. minim de noduri interne pentru naltime h data va fi NI(FTh+1) =Fh+2 1.

abs 2012 9 / 10

Revenim la dem. Th. ineg. (2).

7/24/2019 5b1 a b Stricti Th Avl (2)

33/36

g ( )

abs 2012 10 / 10

Revenim la dem. Th. ineg. (2).

7/24/2019 5b1 a b Stricti Th Avl (2)

34/36

g ( )Fie Tun a.b.s. si echil AVL, cu n= NI(T) noduri interne si naltime h=h(T). Cf. Obs. dedupa lema 4, avem

n Fh+2 1.1

5h+2

1

5 h+2

1 n,

unde = 1+

52

, = 1

52

.

abs 2012 10 / 10

Revenim la dem. Th. ineg. (2).

7/24/2019 5b1 a b Stricti Th Avl (2)

35/36

g ( )Fie Tun a.b.s. si echil AVL, cu n= NI(T) noduri interne si naltime h=h(T). Cf. Obs. dedupa lema 4, avem

n Fh+2 1.1

5h+2

1

5 h+2

1 n,

unde = 1+

52

, = 1

52

.

Din1 0 rezultan 1

5h+2 2,

n+ 2 15h+2,

log2(n+ 2) (h+ 2)log2 12

log25.

abs 2012 10 / 10

Revenim la dem. Th. ineg. (2).

7/24/2019 5b1 a b Stricti Th Avl (2)

36/36

Fie Tun a.b.s. si echil AVL, cu n= NI(T) noduri interne si naltime h=h(T). Cf. Obs. dedupa lema 4, avem

n Fh+2 1.1

5h+2

1

5 h+2

1 n,

unde = 1+

52

, = 1

52

.

Din1 0 rezultan 1

5h+2 2,

n+ 2 15h+2,

log2(n+ 2) (h+ 2)log2 12

log25.

Desfac, n fct. de h ... rezulta

h 1log2

log2(n+ 2) + log25

2log2 2 = a log2(n+ 2) +b,

si a