Tvíundartré
Úr Wikipediu, frjálsa alfræðiritinu
Tvíundartré 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íundartré hefur annað hvort 0 eða 2 börn þá er talað um það sem fullt tvíundartré.
Efsti hnúturinn í tvíundartrénu, þ.e. sá hnútur sem hefur ekkert foreldri er nefndur rót. Hnútur í tvíundartré sem hefur engin börn er kallað lauf.
[breyta] Útfærsla
Hægt er að útfæra tvíundartré sem safn hnúta þar sem hver hnútur er gagnagrind sem innifelur bendil á vinstra barn og hægra barn.
[breyta] Tvíundarleit
Ef tvíundartré 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.
[breyta] Tilvísanir
- Greinin „Binary_tree“ á ensku útgáfu Wikipedia. Sótt 15. febrúar 2007.