Tvíundatré

Tvíundatré (stundum ritað tvíundartré) eða tvíundahrísla er sértilvik af gagnagrindinni "tré", þar sem hver hnútur getur einungis haft 0, 1 eða tvö börn. Almennt er talað um börn hnútsins sem vinstra-barn og hægra-barn eftir því hvorumegin það er ritað við foreldri sitt.

Ef sérhver hnútur í tvíundatré hefur annað hvort 0 eða 2 börn þá er talað um það sem fullt tvíundatré.

Efsti hnúturinn í tvíundatrénu, þ.e. sá hnútur sem hefur ekkert foreldri er nefndur rót. Hnútur í tvíundatré sem hefur engin börn er kallað lauf.

Útfærsla

Hægt er að útfæra tvíundatré sem safn hnúta þar sem hver hnútur er gagnagrind sem innifelur bendil á vinstra barn og hægra barn.

Tvíundarleit

Ef tvíundatré er skilgreint þannig að hver hnútur hafi gildi, gildi vinstra barns er ætíð minna eða jafnt og gildi foreldris, og gildi hægra barns er ætíð stærra eða jafnt og gildi foreldris, þá er talað um tréð sem tvíundarleitartré. Í slíku tré er hægt að framkvæma tvíundarleit sem finnur stak í O(log n) aðgerðum.

Heimildir

Fyrirmynd greinarinnar var „Binary_tree“ á 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.