Download - 5b1 a b Stricti Th Avl (2)
-
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