Arbre (estructura de dades)
![]() |
Aquest article o secció no cita les fonts o necessita més referències per a la seva verificabilitat. |
En informàtica, un arbre és una estructura de dades jeràrquica que conté una col·lecció d'elements distribuïts en nodes enllaçats. Tots els nodes tenen almenys un únic node anomenat pare o ascendent, excepte un únic node que no té node pare que anomenen arrel i que és el punt de partida de tot l'arbre. Al seu torn, cada node pot tenir zero o més nodes anomenats fills o descendents. A més, els nodes fills d'un determinat node tenen un ordre determinat entre ells. Tots els nodes han de poder-se abastar des del node arrel seguint els enllaços dels nodes fills.
A les implementacions, els nodes sempre tenen referències als seus nodes fills, però no sempre al seu únic node pare.
Matemàticament es tracta d'un graf acíclic (sense cicles) i connex (tots els nodes són connectats).
Per convenció es parla de:
- El node arrel és l'únic node que no té pare.
- Un node terminal o node fulla és un que no té cap fill.
- Un node intern o node branca és un qualsevol que no sigui ni arrel ni fulla, és a dir, que té pare i que almenys té un fill.
- La fondària o nivell d'un node és el nombre d'enllaços que cal passar des del node arrel fins a aquest node. Per convenció -1 és la fondària d'un arbre buit, i 0 és la fondària d'un arbre amb un únic node arrel sol.
- Un subarbre és la part d'un arbre que penja d'un node determinat si el prenguéssim com a node arrel, és a dir l'arbre format pel node i tots els seus descendents recursivament. Com a cas especial, el subarbre del node arrel és el mateix arbre sencer.
L'acció de recórrer els nodes de l'arbre (walking the tree) es pot fer aplicant diferent criteris:
- Pre-ordre o en ordre anterior, o primer en fondària (en anglès depth-first-search o DFS): per cada node primer tractar el node i després recórrer cada un dels subarbres fills.
- Post-ordre o en ordre posterior: per cada node primer recórrer cada un dels subarbres fills i després tractar el node.
- En ordre de nivell, o primer en amplada (en anglès breadth-first-search o BFS): es recorren successivament tots els nodes de cada nivell, i a continuació es passa al nivell següent.
La majoria d'operacions que es fan sobre un arbre comencen pel node arrel, especialment en implementacions d'algorismes recursius.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/220px-Binary_tree.svg.png)
Les operacions habituals que ha d'implementar un arbre són:
Les habituals dels contenidors (vegeu l'article contenidor):
- Una operació per comprovar quan un arbre està buit
- Una operació per obtenir el nombre d'elements de l'arbre
Les específiques d'un arbre:
- Un constructor que crea un nou arbre buit
- Una operació per obtenir el nombre de nivells de l'arbre
- Una operació per trobar el node arrel de l'arbre
- Algun mètode recursiu per recórrer tots els nodes de l'arbre, sigui pre-ordre, post-ordre, o en ordre de nivell
- Una operació per trobar el nivell d'un node determinat
- Una operació per trobar cada un dels nodes ascendents d'un node determinat
- Una operació per cercar un element d'un valor determinat
- Una operació per afegir un nou element en una posició concreta de l'arbre, potser rebalancejant l'arbre
- Una operació per eliminar un nou element, potser rebalancejant l'arbre
- Una operació per eliminar un subarbre, operació també anomenada podar (pruning)
- Una operació per afegir tot un subarbre en una posició concreta de l'arbre, operació també anomenada empeltar (grafting)
![]() |
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Arbre |