Arbo (datumstrukturo)

fonto: http://pt.wikipedia.org/wiki/%C3%81rvore_%28estrutura_de_dados%29 

Simpla prezento de duuma arbo de alteco tri ekvilibra (h = 4).

 

Arbo, en la kunteksto de programado kaj komputiko, estas datumstrukturo kiu heredas la karakterizaĵojn de arbaj topologioj. Koncepte la malsamaj ligitaj lertaj en la datumoj estas en ordo, la datumaj arboj estas aranĝitaj nivele.
La arbo estas formita de unu (1) elemento nomata ĉefa Radiko, kiu havas ligojn al aliaj elementoj, kiuj estas nomitaj ramoj aŭ infanoj. Tiuj branĉoj kondukas al aliaj elementoj kiuj havas ankaŭ aliajn branĉojn. La elemento kiu havas ne branĉo estas konata kiel folio kaj/aŭ nodo-termino.
La maksimuma nombro da branĉoj en elemento estas nomata ordo de la arbo. A duuma arbo estas tiu dua ordo, te en kiu ĉiu ero havas maksimume du branĉoj.
Unu el la gravaj operacioj estas paŝo tra ĉiu ero de la arbo nur unufoje. Ĉi tiu itinero, ankaŭ nomata arbo traversala povas fari en antaŭ-ordo (la infanoj de nodo estas procesitaj post la nodo) aŭ postordo (filoj estas procesitaj antaŭ la nodo). En duumaj arboj povas ankoraŭ fari kruciĝo en-ordo, kiu okazas en la maldekstra infano, nodo, kaj fine la dekstra infano.
La algoritmo sub priskribas antaŭ-ordon traversalan: Percurso preordo(nodo): Procezas nodon por ĉiu infana nodo (se estas)
Runs rekursie
Percurso Preordo(filo)
Alia operacio, uzata en la serĉaj arboj estas transiri la radikon al unu el la folioj. Ĉi tiu operacio havas komputan koston proporcia al la nombro de niveloj de la arbo. La plej malbona kazo estas laüiris ĉiuj elementoj ĝis la malsupra nivela folio. Ekvilibra arboj havas la plej bonan plej malbona kazo, pro kelkaj Nodo. La plej malbona kazo estas montrita en degenera arbo en kiu ĉiu vertico havas akurate al infano, kaj la arbo havas la saman nombron de niveloj kiujn nodo, similaj al ligitaj listo.