Estructura arbòria

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

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. LPlantilla:'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

Donat un conjunt C (tipus elem), un arbre binari és o bé un arbre buit o bé un node x i dos arbres binaris A₁ i A₂. Exemples d'arbres binaris:

_
|_| (3) (6)
/ \ / \
-- -- (3) (2)

Per conveni, els subarbres buits no es representen i els cercles dels nodes tampoc.

Definició d'arbres generals

Un arbre general és un element x i un bosc A₁, A₂, ..., A_n. Un bosc és una seqüència (possiblement buida) d'arbres generals.

Definició d'arbres m-aris

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

Recorreguts d'arbres binaris

Recorregut en preordre

Per a cada subarbre:

• si és buit, no es fa res.
• sinó:
• # es visita la seva arrel
• # es recorre en preordre el fill esquerre
• # 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

Per a cada subarbre:

• si és buit, no es fa res.
• sinó:
• # es recorre en postordre el fill esquerre
• # es recorre en postordre el fill dret
• # 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

Per a cada subarbre:

• si és buit, no es fa res.
• sinó:
• # es recorre en inordre el fill esquerre
• # es visita la seva arrel
• # 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

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)

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

Un ABC és equilibrat si la seva alçada és semprelogarí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 Plantilla:Nowrap.

Lema: un AVL amb n nodes té alçada menor o igual que $1,44\cdot {\log }_2(n)-0,328$ (alçada logarítmica).