Tré (tölvunarfræði)

Tré eða hrísla (einnig hrísluskipan) er gagnagrind sem kemur víða fyrir í tölvunarfræðum og samanstendur af einum eða fleiri hnútum sem hver um sig getur haft 0 eða fleiri börn. Hvert barn er hnútur sem getur aftur haft 0 eða fleiri börn og svo koll af kolli. Það er þó sá hængur á að barn getur ekki verið hnútur ofar í trénu, þar eð þá myndi skapast lykkja í gagnagrindinni, og þá væri ekki lengur um tré að ræða, heldur net.

Ef þau skilyrði eru sett á tréð að hver hnútur megi hafa að hámarki tvö afkvæmi þá er tréð nefnt tvíundartré.

Skilgreiningar

Allir hnútar í tré sem hafa sama foreldri eru systkyni.
Í hverju tré er einn og aðeins einn hnútur sem á ekkert foreldri. Þessi hnútur er kallaður rót trésins.
Barnslaus hnútur í tré er kallað lauf
Hnútar sem ekki teljast lauf eru kallaðir innhnútar
Hnútur A telst afkomandi hnútar B ef A er barn B, barn barns B, barn barns barns B, o.s.frv.
Hnútur A telst forfaðir hnútar B ef A er foreldri B, foreldri foreldra B, foreldri foreldra foreldra B, o.s.frv.
Innhnútur í tré ásamt öllum afkomendum þess er kallað undirtré

Að ferðast um tréð

Ef þurfa þykir að skoða hvern hnút í tré þá er slíkt yfirleitt gert með því að ferðast eftir dýptinni eða ferðast eftir breiddinni. Þegar ferðast er eftir breiddinni þá skoðum við öll systkini hnúts áður en við skoðum börn hnútsins, en þegar við ferðumst eftir dýptinni þá skoðum við fyrst öll börn tiltekins hnúts áður en við skoðum systkinahnúta hans.

Tilvísanir

Fyrirmynd greinarinnar var „Tree_structure“ á ensku útgáfu Wikipedia. Sótt 15. febrúar 2007.

Þessi tölvunarfræðigrein er stubbur. Þú getur hjálpað til með því að bæta við greinina.