Mitől lesz egy fa kiegyensúlyozott? Hogyan állapítod meg egy fáról, részfáról, hogy kiegyensúlyozott?

A levelekhez vezető út hosszai között csak 1 lehet a különbség.

Ha (2^n)-1 darab dologból csinálsz fát, akkor egy kiegyensúlyozott fa pontosan n magas, és a levelektől eltekintve minden csomópontnak pontosan két gyereke van. Tehát teljesen "tele" van a fa. Mondjuk ilyen:

[link]

Ha kicsit kevesebb dolog van a fában, akkor a kiegyensúlyozott fa nem lesz teljesen tele, az alsó "szinten" néhol nem lesz levél (hanem ott egy szinttel feljebb lévő csomópont nem csomópont lesz, hanem levél, vagy csomópont lesz, de csak egy gyereke van). Mondjuk ilyesmi:

[link]

Ha pedig nem kiegyensúlyozott, akkor teljesen összevissza magasan vannak a levelek illetve a nem 2 gyerekes csomópontok. Pl. így:

[link]

Az előbb (#3) nem jól írtam, ott a minimális magasságú fákra mutattam példákat, nem a kiegyensúlyozottakra. Bocs...

- Szóval minimális magasságú egy fa (részfa) akkor, legfeljebb a legalsó szinten hiányoznak belőle elemek.

- Tökéletesen kiegyensúlyozott akkor, ha a bal- és jobboldali részfa tökéletesen kiegyensúlyozott ÉS a két részfa elemszáma legfeljebb 1-gyel tér el. Ez kicsit szigorúbb feltétel, mint a "minimális magasságú" eset.

- Kiegyensúlyozott akkor, ha mindkét oldali részfa kiegyensúlyozott ÉS a két részfa magassága legfeljebb 1-gyel tér el. Ez lazább feltétel mindkét előzőnél.

A "magasság" azt jelenit, hogy milyen hosszú  út vezet el a legmesszebb lévő levélhez. Tehát egy levél magassága 0, és mondjuk az ábrádon a 33-as gyökerű részfa, ami 7 elemből áll, a magassága 3 (a 17, 18, 32 úttal). (Lehetne a magasságot eggyel nagyobbnak is definiálni, de így találták ki...)

- A "szigorúan bináris" teljesen más jellegű feltétel: minden elemnek 0 vagy 2 gyereke van. Szóval egy gyerek nem lehet sehol.

Lehet, hogy ez egyértelmű, de akkor már ezt is leírom:

- A részfa az, hogy kinézünk egy elemet a fában, ami nem a gyökér, és az "alatta" lévő dolgok (gyerekei, unokái, stb.) lesz a részfa.

A legjobb, ha alulról kezdve nézed a fát:

- Az 52-estől induló részfa (szóval a 49 / 52 \ 55) egy szigorúan bináris részfa. Másik szigorúan bináris nincs is benne, csak a levelek (amiknek nincs gyereke).

- Az 52-es egyben minimális magasságú is, de ez ilyen 1 magasságú részfáknál nem kunszt. Az összes 1 magas részfa (tehát még a 18, 34, 66 és 89 gyökerűek) is minimális magasságú.

- Az 52-es ezeken kívül még kiegyensúlyozott és tökéletesen kiegyensúlyozott is. De az 1 magas részfákra ez is jellemző mindre, szóval a 18, 34, 66 és 89 gyökerűek mind olyanok.

- Persze a levelek is mind kiegyensúlyozottak meg tökéletesek meg minimális magasságúak meg minden. De ez triviális.

Na most ezekből felfelé lehet építkezni. Ha két részfának közös a szülője, és a két részfa mondjuk tökéletesen kiegyensúlyozott, akkor meg kell nézni, hogy az elemszámok között mennyi a különbség. Ha csak legfeljebb 1, akkor a szülő is tökéletesen kiegyensúlyozott lesz.

- Most itt az 52-es 3 elemű, a 66-os 2 elemű, ezért az 56-os gyökerű részfa is tökéletesen kiegyensúlyozott.

- A 77-es gyökerű is olyan, hisz a bal oldala 1 elemű, a jobb oldal meg 2 elemű, és mindkettő tökéletesen kiegyensúlyozott.

- A 17-es is olyan, azt már le se írom.

- A 33-as viszont nem lesz tökéletesen kiegyensúlyozott. Bár mindkét oldali részfája (17 és 34) tökéletesen kiegyensúlyozott, de az elemszámok 4 illetve 2. De sima kiegyensúlyozottnak jó a 33-as: A bal oldal 2 magas, a jobb pedig 1 magas.

- Ugyanígy a 71-es gyökerű részfa sem tökéletesen kiegyensúlyozott (6 illetve 4 elem), de kiegyensúlyozott: mindkét oldala 2 magas.

- A teljes fa (42-es gyökér) mindkét oldali részfája kiegyensúlyozott, és mindkét oldal magassága ugyanakkora (3), tehát a teljes fa is kiegyensúlyozott.

Még a "minimális magasságú"-ságról:

- A 17-es részfa olyan, mert csak az alsó szinten hiányzik belőle 3 elem (8-as két gyereke, meg 18-as bal oldali gyereke).

- A 34-es is olyan.

- A 33-as már nem, mert ott a 32-es szintjén is, meg a 41-es szintjén is hiányoznak elemek.

- A 71-es is minimális magasságú, csak a 66-os jobb gyereke, a 73-as két gyereke, meg a 89-es bal gyereke hiányzik. Ezek mind ugyanazon a szinten vannak.

- A 42-es persze már nem minimális magasságú, mert a bal oldali részfa sem olyan (a 34-es hiányzó bal oldali gyereke nem a legalsó szintről hiányzik).

Remélem, így már minden kérdésre tudsz válaszolni.