Next: About this document ...
Megoldások a harmadik gyakorlathoz
1. Vegyünk két elemet, x-et és y-t, és
vegyük azt a z csúcsot (z=x vagy z=y is lehet), amely x és y
legalacsonyabban levő közös őse.
Ekkor a következő lehetőségek vannak:
(a) z=x Ekkor, ha x nagyobb
y-nál, akkor az y az x bal részfájában van, tehát
az inorder y-t adja előbb.
Ha y a nagyobb, akkor y jobbra esik, és az inorder később adja.
(b) Ha z=y, akkor hasonlóan járunk el.
(c)
Ha a közös ős se nem x, se nem y, akkor ennek az közös ősnek az
egyik részfájában van az egyik csúcs, a másikban a másik,
jobbra a nagyobb, amit ezért az inorder később ad vissza.
Tehát bármely két csúcsot jó sorrendben ad vissza az inorder bejárás.
2. (a) Az előző feladat értelmében az inordernél nem lehetséges.
A másik kettőnél viszont igen, lásd a (b) rész megoldását.
(b) Az inorder nem lehet, az első feladat miatt. Preorder esetén:
mivel a preorder a gyökeret adja vissza először, a gyökérben az n
áll. Ettől jobbra nem állhat semmi, mert nincsen nagyobb elem.
A preorder ezután a most megvizsgált csúcs jobboldali részfájának
gyökerét adja vissza, itt áll tehát az n-1. Ettől balra megint senki se
lehet.
Ezt a gondolatmenetet folytatva kapjuk, hogy a fa egy jobbra
tartó út, amin csökkenő sorrendben vannak a pontok.
Postordernél: legutoljára a gyökeret adja vissza, tehát most a
gyökér az 1. Ettől jobbra senki se állhat.
Ilyen fákra az utolsó előtti visszaadott elem, vagyis most a 2,
áll a gyökér balrészfájának gyökerében. Ezt továbbgondolva, a fa
egy balramenő út, a pontok növő sorrendben vannak rá felrakva.
3. A teljes feladatsorban szerepel a megoldás a Keresőfák 7. feladatnál.
4. A teljes feladatsorban szerepel a megoldás a Keresőfák 19. feladatnál.
5.A teljes feladatsorban szerepel a megoldás a Keresőfák 1. feladatnál.
6. A teljes feladatsorban szerepel a megoldás a Keresőfák 4. feladatnál.
7. A teljes feladatsorban szerepel a megoldás a Keresőfák 9. feladatnál.
8. A teljes feladatsorban szerepel a megoldás a Keresőfák 15. feladatnál.
9. Elmesélem, hogy hogyan néz ki egy ilyen fa: a gyökér baloldali
részfája egy teljes bináris fa, mely négy szintből áll. A gyökér
jobboldali fája a következő: a részfa gyökeréből megy balra egy
egy hosszúságú út, jobbra pedig egy kettő hosszúságú.
Ha az egy hosszúságú balra menő utat töröljük, az AVL tulajdonság
sérül a gyökér jobb fiánál és semmilyen egy darab forgatás
nem segít ezen, ezt gondoljátok meg.
10. A teljes feladatsorban szerepel a megoldás a Keresőfák 22. feladatnál.
11. Gondolkodjatok, nem írom le a megoldást.
Next: About this document ...
Judit Csima
1999-11-10