Estructura arb??ria
De Viquip??dia
Les estructures arb??ries s??n un dels sistemes d'emmagatzemar informaci?? emprades en inform??tica.
Taula de continguts |
[edita] Introducci??
A la inform??tica, se cerquen maneres d'emmagatzemar informaci?? de manera eficient pel que fa a costos en temps. Una manera ??s mitjan??ant els arbres. Els contenidors s??n jer??rquics. Exemples:
director /
+-------------+-------------+ +--------+---------+--------+
cap de cap de cap de usr home etc bin
depart. depart. depart. +-----+-----+
+---------+ bin etc sbin
cap de cap de
secci?? secci??
Els elements d'un arbre s'anomenen nodes i poden contenir subarbres. El grau d'un node ??s el nombre de subarbres que pengen d'ell. Un node ??s una fulla si el seu grau ??s zero. L'arrel d'un arbre ??s aquell node que no penja de cap arbre. L'al??ada d'un node ??s la longitud del cam?? m??s llarg per anar des d'aquell node fins a una fulla. L'al??ada d'un arbre ??s l'al??ada de la seva arrel.
[edita] Definici?? d'arbres binaris
Donat un conjunt C (tipus elem), un arbre binari ??s o b?? un arbre buit o b?? un node x i dos arbres binaris A1 i A2. Exemples d'arbres binaris:
_
|_| (3) (6)
/ \ / \
-- -- (3) (2)
Arbre binari buit / \ / \
-- ---- --
Per conveni, els subarbres buits no es representen i els cercles dels nodes tampoc.
[edita] Definici?? d'arbres generals
Un arbre general ??s un element x i un bosc A1, A2, ??????, An. Un bosc ??s una seq????ncia (possiblement buida) d'arbres generals.
[edita] Definici?? d'arbres m-aris
Un arbre ??s m-ari si cada node o b?? t?? 0 fills o b?? en t?? exactament m.
[edita] Recorreguts d'arbres binaris
[edita] Recorregut en preordre
Per a cada subarbre: - si ??s buit, no es fa res.
- sin??: 1) es visita la seva arrel
2) es recorre en preordre el fill esquerre
3) es recorre en preordre el fill dret
Exemple:
A
+-----|----+
B F
/ \ / \
X Y H ---> A B X Y Q F H
/ \ / \
Q
esquema preordre (a: arbre binari)
si ?? buit (a):
"visitar" arrel(a)
preordre (fill_esq(a))
preordre (fill_dre(a))
[edita] Recorregut en postordre
Per a cada subarbre: - si ??s buit, no es fa res.
- sin??: 1) es recorre en postordre el fill esquerre
2) es recorre en postordre el fill dret
3) es visita la seva arrel
Exemple:
A
+-----|----+
B F
/ \ / \
X Y H ---> X Q Y B H F A
/
Q
esquema postordre (a: arbre binari)
si ?? buit (a):
postordre (fill_esq(a))
postordre (fill_dre(a))
"visitar" arrel(a)
[edita] Recorregut en inordre
Per a cada subarbre: - si ??s buit, no es fa res.
- sin??: 1) es recorre en inordre el fill esquerre
2) es visita la seva arrel
3) es recorre en inordre el fill dret
Exemple:
A
+-----|----+
B F
/ \ / \
X Y H ---> X B Q Y A H F
/ \ / \
Q
esquema inordre (a: arbre binari)
si ?? buit (a):
inordre (fill_esq(a))
"visitar" arrel(a)
inordre (fill_dre(a))
d) Recorregut per nivells.
Els nodes es visiten de dalt a baix i, per cadascun dels nivells, d'esquerra a dreta
Exemple:
A
+-----|----+
B F
/ \ / \
X Y H ---> A B F X Y H Q
/ \ / \
B Q
[edita] Arbres binaris de cerca (ABC)
Un arbre ??s un arbre binari de cerca (en angl??s, Binary Search Tree, BST) si per cada node x que tingui un arbre esquerre (E) i un arbre dret (D) tenim que totes les claus y que pertanyen a E s??n menors que x i totes les claus z que pertanyen a D s??n m??s grans que x. Exemples:
3 10
+---------------+ +----------------+
2 7 8 15
/ / \ / \ / \
0 6 9 6 12 13 17
/ /
4 9
\ \
5 11
L'arbre de l'esquerra ??s un ABC; el de la dreta no perque al fill esquerre de l'arrel hi ha un 12 que ??s menor que 10 (hauria d'estar al fill dret) i al fill dret de l'arrel hi ha un 9 que ??s menor que 10 (hauria d'estar al fill esquerre).
Es compleix que un recorregut en inordre d'un ABC d??na els elements ordenats de menor a major. Hi ha un teorema que diu que l'al??ada mitjana d'un ABC constru??t a partir d'n elements aleatoris ??s logar??tmica respecte els n elements, ??s a dir, que si tenim 8 elements aleatoris, l'al??ada mitjana de l'arbre resultant ser?? 2.
Les operacions que podem fer a un ABC s??n: cerca d'un element, consulta de l'element d'un node (si existeix), inserci?? d'un element (es cerca l'element x a inserir i, si no el trobem, l'inserim al node buit trobat) i esborrats. A efectes de cost, totes les operacions triguem un temps logar??tmic respecte la talla de l'entrada.
[edita] Arbres equilibrats i AVL's
Un ABC ??s equilibrat si la seva al??ada ??s SEMPRE logar??tmica per n nodes. Un ABC ??s un AVL (Adelson-Velskii i Landis, 1963) si per cadascun dels seus nodes, la difer??ncia en valor absolut de les al??ades dels seus fills ??s menor o igual que 1. Es defineix que l'al??ada de l'arbre buit ??s -1 i que l'al??ada d'un node ??s 1+max{al??ada(fill_esq), al??ada(fill_dre)}.
Lema: un AVL amb n nodes t?? al??ada menor o igual que 1.44 * log2(n) ??? 0.328 (al??ada logar??tmica).
Demostraci??: Sigui la funci?? minnodes(h) = m??nim nombre de nodes d'un AVL d'al??ada h. Hi ha 2 casos trivials: minnodes(0) = 0; minnodes(1) = 1. Per a h > 1, tenim un AVL amb arrel i 2 fills. Un d'ells ha d'??sser d'al??ada h - 1 per tal que l'arbre tingui al??ada h. L'altre pot tenir al??ada h - 1 o h - 2. Com que minnodes(h) s'incrementa amb h tindr?? un valor menor si t?? al??ada h - 2. A m??s, per obtenir el nombre m??nim de nodes, necessitem que els fills tinguin al??ada m??nima.
Aix??, tenim la recurr??ncia minnodes(h) = minnodes(h-1) + minnodes(h-2) + 1 per a h > 1. La soluci?? d'aquesta recurr??ncia ??s: minnodes(h) = Fibo(h+2) - 1, sent Fibo(x) la recurr??ncia de Fibonacci da Pisa [Fibo(x) = Fibo(x-1) + Fibo(x-2)]. Per exemple, minnodes(0) = Fibo(2) - 1 = 1 - 1 = 0; minnodes(1) = Fibo(3) - 1 = 2 - 1 = 1. Per a h > 1, minnodes(h) = Fibo(h+2) - 1 = Fibo(h+1) + Fibo(h) - 1 = 1 + [Fibo(h+1) - 1] + [Fibo(h) - 1] = 1 + minnodes(h-1)+ minnodes(h-2).
Fibo(x) = 1/???5 * (((1 + ???5))^x)/2 - 1/???5 * (((1 - ???5))^x)/2
Sigui f(x) = 1/???5 * (((1 - ???5))^x)/2
La funci?? f(x) tendeix a zero molt r??pidament (a x = 1, val -0.28; a x = 10 val 0.0036). Aix?? doncs, poden simplificar Fibo(x) com Fibo(x) = 1/???5 * (((1 + ???5))^x)/2. Aix?? ens d??na que minnodes(h) ???1/???5 * (((1 + ???5))^(h+2))/2.
Aix??, per a un AVL de n nodes, tenim:
Nota: denotem log[a](x) com el logaritme en base a de la variable x.
![n \ge 1/\sqrt{5} * (((1 + \sqrt{5}))^(h+2))/2 - 1 \Rightarrow \log[(1+\sqrt{5})/2] (n) \ge h + 2 + \log[(1+\sqrt{5})/2] (1/\sqrt{5}) - 1 \Rightarrow](../../../../math/1/d/d/1dd1931849c71425435ca0813d8b937d.png)
![\Rightarrow h \le \log[((1+\sqrt{5})/2)] (n) - \log[(1+\sqrt{5})/2] (1/\sqrt{5}) - 2 + 1 \approx \log[1.62] (n) - [ \log[1.62] (1/\sqrt{5}) + 1 ]](../../../../math/5/6/b/56b55f11a286ceddf6539f343206703a.png)
Com que log2[1.62](x) = 1.44 * log2(x), resulta 
