Tvíundatré
Tvíundatré[1] (stundum ritað tvíundartré) eða tvíundahrísla[1] 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
[breyta | breyta frumkóða]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
[breyta | breyta frumkóða]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.
Tilvísanir
[breyta | breyta frumkóða]- ↑ 1,0 1,1 tvíundatré hk. Raðað tré þar sem hver hnútur hefur í hæsta lagi tvo aðra beint undirskipaða hnúta. Geymt 3 október 2008 í Wayback Machine á Tölvuorðasafninu
Heimildir
[breyta | breyta frumkóða]Fyrirmynd greinarinnar var „Binary_tree“ á ensku útgáfu Wikipedia. Sótt 15. febrúar 2007.
