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.