Arbo (datumstrukturo)

El Vikipedio, la libera enciklopedio
Salti al navigilo Salti al serĉilo
Simpla neordigita arbo. En ĉi tiu skemo, la nodo 7 havas du "infanojn" 2 kaj 6 kaj unu "patro" 2. La radika nodo, je la supro, havas neniun patron.

En informadiko, arbo estas vaste uzata abstrakta datumtipo (ADT) aŭ datumstrukturo, kiu realigas tiun datumtipon, kiu simulas hierarkian arbon, kun radika valoro kaj subarboj de infanoj kun poa patra nodo, reprezentata kiel aro de ligitaj nodoj.

Arba datumstrukturo povas esti difinita rikure kiel kolekto de nodoj (komenciĝantaj el radika nodo), kie ĉiu nodo estas datumstrukturo konsistanta el valoro kaj listo de referencoj al nodoj (la "infanoj"), kun la limoj, ke neniu referenco estas duplikatita kaj neniu indikas la radikan nodon.

Alternative, arbo povas esti difinita abstrakte kiel ordigita arbo kun valoro asignita al ĉiu nodo. Ambaŭ ĉi tiuj perspektivoj estas utilaj: dum arbo povas esti analizita matematike kiel tuto, kiam efektive reprezentita kiel datumstrukturo ĝi estas kutime reprezentata kaj prilaborata kiel apartaj nodoj. Ekzemple, rigardante arbon kiel tuton, oni povas paroli pri "la patra nodo" de ajna nodo, sed ĝenerale kiel datumstrukturo, ajna nodo nur enhavas la liston de siaj infanoj, sen referenco al sia patro.