Estructura arbòria

De Viquipèdia
Dreceres ràpides: navegació, cerca

Les estructures arbòries són un dels sistemes d'emmagatzemar informació emprades en informàtica.

Introducció[modifica | modifica el codi]

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.

Definició d'arbres binaris[modifica | modifica el codi]

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.

Definició d'arbres generals[modifica | modifica el codi]

Un arbre general és un element x i un bosc A1, A2, ···, An. Un bosc és una seqüència (possiblement buida) d'arbres generals.

Definició d'arbres m-aris[modifica | modifica el codi]

Un arbre és m-ari si cada node o bé té 0 fills o bé en té exactament m.

Recorreguts d'arbres binaris[modifica | modifica el codi]

Recorregut en preordre[modifica | modifica el codi]

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))

Recorregut en postordre[modifica | modifica el codi]

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)

Recorregut en inordre[modifica | modifica el codi]

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))

Recorregut per nivells[modifica | modifica el codi]

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
/ \
Q

Arbres binaris de cerca (ABC)[modifica | modifica el codi]

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 perquè 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 de n elements aleatoris és logarítmica respecte als 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 (se 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.

Arbres equilibrats i AVL's[modifica | modifica el codi]

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 * log_2(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

 \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 ]

Com que  \log_2[1.62] (x) = 1.44 * \log_2(x) , resulta  h \le 1.44 * log_2(n) - 0.328