Bináris fa üres levelekkel

Láttuk a bináris fákkal kapcsolatos előadáson, hogy a fa gyökerét mutató változó kezelése néha nehézkes; minden csomópont hozzáadásakor be kell írni az új csomópont referenciáját egy változóba.

A láncolt listák kapcsán bemutatott strázsa technika itt is adhat egy ötletet. Az megoldotta ugyanis azt a problémát, hogy a függvény nem tudta módosítani a neki paraméterként átadott változóban tárolt referenciát. A megoldás ott az volt, hogy az üres lista sem volt üres, hanem volt benne egy elem. Azt az elemet, amikor átadtunk paraméterként, akkor egy objektum referenciáját adtuk át – és maga az objektum viszont már módosítható volt ezen keresztül.

Az ötlet tehát a következő. Úgy építjük fel a fát, hogy a nem létező csomópontokat nem a None érték reprezentálja, hanem egy üres csomópont. Vagyis a fában legyenek üres levelek mindenhol:

Mindjárt meglátjuk kódban is, ez miért lesz jó. Előbb nézzük meg, hogyan kell a fás algoritmusainkat megfogalmazni egy ilyen felépítésű fánál! Legyen a példa az elemszám:

def binfa_elemszam(gyoker):
    if gyoker.adat is None:     # !
        return 0
    return (binfa_elemszam(gyoker.bal)
            + binfa_elemszam(gyoker.jobb)
            + 1)

Az egyetlen különbség a fát bejáró algoritmusban a felkiáltójellel jelzett helyen van. Az üres fát most nem arról ismerjük meg, hogy a paraméter értéke None; hanem hogy egy olyan csomóponton állunk, amelyben nincsen adat, vagyis gyoker.adat is None. Egyébként pedig ugyanúgy működik minden.

Érdekes kérdés, hogy mit jelent ilyenkor a fa elemeinek száma. A fenti algoritmus az üres csúcsokat nem számolja bele ebbe. Vagyis a rajzon látható fára a csúcsok száma 5 lenne (üres csomópontok nélkül), nem pedig 11 (üres csomópontokkal együtt). Ez helyes is; a fába 5 adatelemet tettünk, a többi csomópontok csak technikailag szükségesek, az algoritmusaink fogják használni őket.

Vegyük észre, mi változik az üres levelekkel:

gyoker = BinfaElem(None)

binfa_beszur(gyoker, 5)
binfa_beszur(gyoker, 3)
binfa_beszur(gyoker, 7)

def binfa_beszur(gyoker, adat):
    mozgo = gyoker
    while mozgo.adat is not None:
        if mozgo.adat == adat:
            return  # benne van
        elif adat < mozgo.adat:
            mozgo = mozgo.bal
        else:
            mozgo = mozgo.jobb
            
    mozgo.adat = adat
    mozgo.bal = BinfaElem(None)
    mozgo.jobb = BinfaElem(None)

Figyeljük meg az algoritmus működését! Ez egy lokális változót, a „mozgót” beállítja a gyökérelemre. A ciklusban három eset lehetséges:

• Épp megtaláljuk az elemet, amit be kellene szúrni. Ilyenkor nem csinálunk semmit, csak visszatérünk, mert az elem már benne van a fában.
• Balra vagy jobbra megyünk tovább, attól függően hogy kisebb vagy nagyobb elemet kell beszúrni.

Mindezt addig folytatjuk, amíg meg nem találjuk azt a levelet, ahova az új adat kerül. Ne feledjük, ilyen mindig lesz, mert a fának minden ága egy üres levélben végződik. Ha ez megvan, akkor az egy üres csomópont (mozgo.adat is None), amelybe az új adat betehető; és mivel innentől kezdve az egy adatot tároló csomóponttá válik, létre kell hozni a hozzá tartozó üres leveleket.

A függvény megírható úgy is, hogy a keresés mindkét megállási feltételét a ciklus feltételébe tesszük. Így már tényleg teljesen úgy néz ki, mint a téma elején bemutatott kereső algoritmus – figyelembe véve persze, hogy a megállási feltétel most az üres csomópont, és nem pedig a nem létező csomópont:

def binfa_beszur(gyoker, adat):
    mozgo = gyoker
    while mozgo.adat is not None and mozgo.adat != adat:
        if adat < mozgo.adat:
            mozgo = mozgo.bal
        else:
            mozgo = mozgo.jobb
    
    if mozgo.adat is None:
        mozgo.adat = adat
        mozgo.bal = BinfaElem(None)
        mozgo.jobb = BinfaElem(None)
    else:
        pass

A pass utasítás jelöli meg a kódban azt a helyet, ahova akkor jutunk, ha a keresett adat benne van a fában.

Az üres levelek technikáját ritkán alkalmazzuk. Észre kell venni, hogy ez nem olyan hatékony, mint a láncolt listák strázsái esetében. Ott mindig pontosan egyetlen egy elem volt a strázsa, a lista hosszától függetlenül, vagyis elhanyagolható volt a lista értékes csomópontjaihoz képest. Itt viszont nem ez a helyzet: az üres csomópontok a fa növekedtével egyre többen vannak. Egészen pontosan n + 1 darab üres csomópont lesz n darab értékes csomópont mellé, mivel a beszúrás mindig 2 új üreset hoz létre, és 1 meglévő üresnek értéket ad. Vagyis ezt csak akkor érdemes csinálni, ha nem túl nagy a fánk, vagy ha az üres csomópontoknak jelentést, szerepet tudunk adni.