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