# Bináris fa üres levelekkel

Czirkos Zoltán · 2023.01.13.

A bináris fákat néha úgy építjük fel, hogy a levelek üresek – előre létrehozva az adatnak a helyet. Miért jó ez?

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.

## 1. Az üres csomópontok

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.

## 2. A keresőfa építése

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

    gyoker = BinfaElem(None)

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

Legfontosabb, hogy az üres fát most egy üres csomópont reprezentálja, amiben nincs adat. Ezért kapta a `BinfaElem` konstruktora is a `None` paramétert az adat helyén. Vagyis van egy csomópont, de a fa még üres. Az 5-ös értékű elem beszúrása ezt az elemet fogja módosítani, beleírni az 5-öt; és mivel innentől kezdve nem üres, létrehozza az ő két gyerekét. Vagyis a fa az alább látható lépésekkel kezd el épülni:

Ez azt jelenti, hogy minden út végén találunk egy üres csomópontot, amelybe adatot írhatunk. Ha írunk bele, akkor pedig létre kell hozni annak gyerekeit. Mindeközben a `gyoker` nevű változó értéke nem változik meg, és így nem kell visszaadni a gyökérelemet. Az algoritmust megírhatnánk rekurzívan is, az előzőt átalakítva:

    def binfa_beszur(gyoker, adat):
        if gyoker.adat is None:            # üres csomópont?
            gyoker.adat = adat
            gyoker.bal = BinfaElem(None)
            gyoker.jobb = BinfaElem(None)
            return

        if adat < gyoker.adat:             # kisebb?
            binfa_beszur(gyoker.bal, adat)
        elif adat > gyoker.adat:           # nagyobb?
            binfa_beszur(gyoker.jobb, adat)
        else:
            pass # benne van

De ilyen körülmények között az iteratív megoldás is nagyon egyszerű. A működés lényege, hogy úgy haladunk, mint a keresésben: egy ciklus balra vagy jobbra lép tovább, ha nem találta meg akeresett elemet. Ahol megáll, a keresett elem ott van – vagy ha nincs, akkor oda kell tenni, mert elvégre is jelenleg nem konkrétan a keresés, hanem a beszúrás a feladatunk.

    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.