Arbre (estructura de dades): diferència entre les revisions
Contingut suprimit Contingut afegit
Cap resum de modificació |
Cap resum de modificació |
||
Línia 13:
* 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.
** Pre-ordre o en ordre anterior: per cada node primer tractar el node i després recórrer cada un dels subarbres fills.▼
▲
La majoria d'operacions que es fan sobre un arbre comencen pel node arrel, especialment en implementacions d'algorismes recursius.
Linha 35 ⟶ 36:
* 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 ''
* Una operació per trobar el nivell d'un node determinat
* Una operació per trobar cada un dels nodes ascendents d'un node determinat
| |||