11. hét: bináris fák

Czirkos Zoltán · 2019.07.25.

Gyakorlófeladatok az előadás anyagához kapcsolódóan.

1. Bináris fák

Mikulás

A Mikulás a szánjával nekihajtott a fent látható, gyökerével adott fának. A csomagok a puttonyából kihullottak és szétszóródtak a fa ágain. Ezért a Mikulás felmászik a fára, végigjárja az összes ágát, és az ott található ajándékokat összegyűjti. Mindet a fa gyökeréhez cipeli. Az egyes ágakon található ajándékok számai a fa elemeiben tárolt egész érték által adottak. Feladat: megírni azt a függvényt, amely a gyökérnél összegzi a fában tárolt elemeket, míg az összes többi, fában tárolt egészet kinullázza.

Szintek sorszáma

    0
   / \
  1   1
 / \   \
2   2   2

Definiálj bináris fa típust, melynek csomópontjai egész számokat tartalmaznak!

Írj függvényt, amelyik bejárja a fát, és minden csomópontba beírja azt, hogy hányadik szinten van! A fa gyökere a nulladik szint.

Az ábra bejárás után mutajta egy ilyen fa tartalmát.

Cseresznye

Nevezzük cseresznyének az olyan részletet a bináris fában, ahol egy csomópontnak pontosan két gyereke van, azoknak pedig már nincsenek további gyerekeik!

Írj függvényt, amely paraméterként kap egy bináris fát, és megadja, hány cseresznye van rajta!

Kukac

Egy bináris fa egész számokat tárol. Definiáld az ehhez szükséges osztályt! Írj függvényt, amelyik megmondja egy ilyen fáról, hogy kukac-e. Másképp fogalmazva, listává fajult-e, vagyis úgy néz-e ki, mint a lent látható fák. A visszatérési értékében jelezze ezt, logikai igaz értékkel. Írj egy rövid programrészt, amelyben definiálsz egy fát, és meghívod arra a fára a megírt függvényt.

    o     vagy     o       vagy       o
   /                \                /
  o                  o              o
 /                    \              \
o                      o              o

Pontosan kettő vagy nulla leszármazott

Egy bináris fa szavakat tárol. Definiáld az ehhez szükséges osztályt! Írj függvényt, amelyik megmondja egy ilyen fáról, hogy minden csomópontnak pontosan kettő vagy nulla leszármazottja van-e. A visszatérési értékében jelezze ezt, logikai igaz értékkel. Írj egy rövid programrészt, amelyben definiálsz egy fát, és meghívod arra a fára a megírt függvényt.

     o
    / \
   /   \
  o     o
 / \   / \
o   o o   o

ez pl. ilyen

     o
    / \
   /   \
  o     o
 / \     \
o   o     o

ez meg nem

Meddig van teljesen kitöltve?

Írj egy függvényt, amelyik megkapja egy fának a gyökerét, és megmondja, hogy a fa felső hány szintje van teljesen kitöltve!

Megoldás

Onnantól van nem teljesen kitöltve, ahol van benne egy None referencia. Tehát a gyökérhez legközelebbi None referenciát kell keresni. Ha a gyökér maga is None, akkor ez a távolság nulla. Ha nem, akkor 1 + a két részfából a kisebbik érték.

Úgy is lehet gondolkozni, hogy egy fa adott szintjein lévő elemek száma egy teljesen kitöltött fában a kettő hatványait adják ki: 1, 2, 4, 8 stb. Ameddig ez igaz a szintekre, addig teljesen ki van töltve. Már csak kell egy ciklus, amelyik az egyre mélyebb szinteket ellenőrzi a külön segédfüggvény hívásával. Ez sokkal lassabb megoldás, de helyes.

Adott szavak között

Egy bináris fa szavakat tárol. Definiáld a szükséges osztályt! Írj függvényt, amelyik megszámolja, hogy egy ilyen fában hány olyan csomópont van, amelyik a „dinnye” és a „papaja” közötti szavakat tárolja az ABC-ben (beleértve pontosan ezeket is.) Az eredményt visszatérési értékként adja. Írj egy rövid programrészt, amelyben definiálsz egy fát, és meghívod arra a fára a megírt függvényt.

Keresés rendezetlen fában

Írj rekurzív függvényt, amely nem feltételez semmilyen rendezettséget a fa elemei részéről (az értékek részéről), és úgy keres meg egy karaktert a fenti fában!

Tipp
  • Ha üres a fa, akkor nincs meg a keresett elem.
  • Ha a gyökérelem pont az, amit keresünk, akkor arra kell visszatérni referenciával.
  • Amúgy lehet, hogy a bal oldali részfában lesz. Ha ott megtaláljuk, akkor egy onnan származó referenciával kell visszatérni.
  • Ugyanez lehet a jobb oldali részfánál is.
  • Ha egyikben sem – akkor None.

2. Bináris fák – összetettebb feladatok

Törlés a fából

A tananyagban nem szerepel a bináris fából törlés, de nem nehéz megcsinálni.

  • Ha a törlendő elem levél, simán törölhető.
                5                       5
               / \                     / \
              3   8                   3   8
             /   / \                 /   / \
            2   6   9               2   6   9
           /     \   \             /         \
          1       7   10          1           10
    
  • Ha egy gyereke van, akkor is. Természetesen ilyenkor helyettesíteni kell a töröltet a gyerekével:
                5                       5
               / \                     / \
              3   8                   3   8
             /   / \                 /   / \
            2   6   9               2   7   9
           /     \   \             /         \
          1       7   10          1           10
    
  • Nehézség csak akkor adódik, ha a törlendő elemnek két gyereke van, mivel ilyenkor az egyetlen törölt elem helyét nem foglalhatja el a két gyereke:
                5
               / \
              3   8
             /   / \
            2   6   9
           /     \   \
          1       7   10
    
    Ilyenkor a törlendő elem tartalmát helyettesíteni kell akár az in-order bejárás szerint utána következő, akár az in-order bejárás szerint őt megelőző elemmel (mindegy, hogy melyikkel, lent mind a kettő ki van emelve). Utána pedig a helyettesítő elem könnyedén törölhető, mivel bizonyítható, hogy annak nulla vagy egy gyereke volt csak, tehát a probléma vissza van vezetve az előző két esetek egyikére.
                5                       5                       5
               / \                     / \                     / \
              3   8                   3   7                   3   7
             /   / \                 /   / \                 /   / \
            2   6   9               2   6   9               2   6   9
           /     \   \             /     \   \             /         \
          1       7   10          1       7   10          1           10
    

Feladatok:

  • Gondold ki, hogyan lehet megtalálni egy adott elemet követő, vagy adott elemet megelőző elemet! Ehhez ne másold ki a fát lineáris adatszerkezetbe (tömbbe vagy listába), az felesleges.
  • Magyarázd meg, miért igaz az a kijelentés, hogy az így megtalált elemnek nulla vagy egy gyereke van csak!
  • A törlésnél figyelni kell arra, hogy a szülő elem valamelyik referenciájára, vagy esetleg a fa gyökere módosul. Ezt a problémát úgy oldhatod meg, hogy mindig visszatérsz a fa (új) gyökerével.
  • Írj programot, amelyben egy függvénnyel tudod egy keresőfa egy adott elemét törölni!
Részmegoldás: a következő és az előző elem

Egy adott elemet megelőző és az azt követő elem könnyen megtalálható iteratív algoritmussal is. Az őt megelőző elem a nála kisebbek közül a legnagyobb, tehát a bal oldali részfájának jobb szélső eleme. Az őt követő elem pedig szimmetrikusan a jobb oldali részfájának bal szélső eleme.

Az így megtalált elemek mindenképp legfeljebb egy gyerekkel rendelkeznek csak: a bal szélső elem azért, mert nincs bal oldali szomszédja (különben nem ő lenne a bal szélső), a jobb szélső pedig ugyanígy, csak a másik irányba.

Keresőfa-e

Írj függvényt, amely paraméterként egy egész számot tartozó fát kap, visszatérési értékében pedig azt jelzi, hogy ez rendelkezik-e keresőfa tulajdonsággal, vagy nem! Vagyis balra mindig a gyökértől kisebb, jobbra mindig a gyökértől nagyobb számok vannak, mindenhol.

Vizsgáld meg az algoritmusod futási idejét! Hogyan függ a fa csúcspontjainak számától?

Ha nem O(n) időben fut az algoritmusod, oldd meg azt O(n) időben is!

Megoldás

Nem elég azt vizsgálni, hogy a teljes fa gyökeréhez képest csak balra kisebbek, jobbra nagyobbak vannak-e. Az alábbi fában ez teljesül (a 2 és a 3 kisebbek a gyökérben lévő 5-nél, illetve a 6, 9 és 8 nagyobbak nála), mégsem keresőfa; a jelölt elemek elrontják azt.

    5
   / \
  3   9
 /   / \
2   6   8

Azt sem elég vizsgálni, hogy minden csomópont gyerekei balra kisebbek, jobbra nagyobbak-e. Az alábbi fában ez minden közvetlen kapcsolatban lévő elemre teljesül, mégsem keresőfáról van szó: a 6-os elem rossz helyen van, bár a 3-nál nagyobb, de az egész fát tekintve a gyökérben lévő 5-től jobbra keresnénk.

    5
   / \
  3   8
 / \   \
2   6   9

A két tulajdonságnak együtt kell teljesülnie. Ezek alapján a program megírható.

Ez nem hatékony; minden részfát annyiszor bejár (sőt duplán annyiszor), amilyen magas részfában van.

Hatékonyabb megoldáshoz érdemes egy bejárásból kiindulni. Tudjuk, hogy a keresőfát inorder bejárva növekvő számsort kapunk. Tehát nem kell mást tenni, mint elvégezni a bejárást, és ha bárhol olyan számot találunk, amelyik egyenlő az előbb látottal vagy kisebb annál, akkor a fát hibásnak jelölhetjük.

Másik megoldási lehetőség: figyelembe vehetjük azt is, hogy a hierarchia milyen intervallumba szorítja be a részfák csomópontjaiban található értékeket. Ehhez vegyük példának az alábbi fát:

    5
   / \
  3   9
     / \
    x   10

Ebben a fában az x-szel jelölt helyen (akár egy csomópont van ott, akár egy nagyobb részfa) csak 5-nél nagyobb, és 9-nél kisebb szám lehet. 5-nél nagyobb azért, mert a gyökérben lévő 5-től jobbra van (ha kisebb lenne, akkor az 5-től balra kellene legyen). 9-nél kisebb pedig azért, mert egy attól balra lévő részfáról van szó.

Fát másol, fák egyformák-e

Definiálj egy adatszerkezetet, amelyik karaktereket tároló bináris fa létrehozására alkalmas!

Írj egy függvényt, amelyik paraméterként egy ilyen bináris fa gyökerére mutató referenciát kap! Visszatérési értéke legyen egy másik bináris fa gyökerének referenciája, amelyik az előbbinek a másolata! (A másolást is végezze el a függvény!)

Írj egy függvényt, amelyik paraméterként két ilyen bináris fa gyökerét kapja! Térjen vissza igazzal a függvény, ha a paraméterként kapott két bináris fa egyforma, hamissal akkor, ha nem egyformák.

Megoldás

Hogy lehet lemásolni egy fát? Egy fa másolata az a gyökér csomópontjának a másolata, és a két részfájának másolata (itt a rekurzió.) Ügyelni kell arra, hogy mindenhol új csomópontot kell létrehozni, nem elég csak a referenciákat beállítani (mély másolat kell). Az új csomópont bal oldali részfája az eredeti fa bal oldali részfájának másolata; és a jobb oldalira ugyanez. Természetesen üres fa másolata üres fa.

Az összehasonlítás a következő módon képzelhető el. A függvény ebben az esetben két fát kap. Ha mind a két fa üres, akkor igazat kell válaszoljon; két üres fa ugyanis egyforma. Ha az egyik fa üres, a másik meg nem, akkor nem egyformák (legyen bármi is a másikban, ha az első teljesen üres.) Ha egyik fa sem üres, akkor össze kell hasonlítani őket: akkor egyformák, ha a gyökérelemeik egyformák, és a bal részfáik egyformák, és a jobb részfáik egyformák.

Buktató: hogy két fa inorder bejárással ugyanazt a listát adja, nem biztosan jelenti azt, hogy a két fa egyforma! Például:

    5       7
   /       / \
  7       9   5
 /
9