Bináris fa üres levelekkel

Czirkos Zoltán · 2019.08.07.

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.