Tvíundatré

Tvíundatrétvíundatré hk. Raðað tré þar sem hver hnútur hefur í hæsta lagi tvo aðra beint undirskipaða hnúta.  á Tölvuorðasafninu (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.

 Tilvísanir 

 Heimildir 

Flokkur:Gagnagrindur