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
breytaHæ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
breytaEf 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- ↑ 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
breytaFyrirmynd greinarinnar var „Binary_tree“ á ensku útgáfu Wikipedia. Sótt 15. febrúar 2007.
