Láncolt listák, bináris fák

p1 = Pont()
p2 = Pont()

p = p1     # 1

p = p2     # 2

p = Pont() # 3

A fenti kódban kettő pontot hozunk létre, és ehhez tartozóan három referenciát. Az alsó, jelölt kódsorok jelentését érdemes átgondolni: az értékadás ezekben a sorokban új Pont típusú objektumot már nem hoz létre, csak egy meglévő pontra mutat rá újabb referenciával. Az első értékadás után a p-ban és a p1-ben tárolt referenciával is a bal oldali pontot érjük el (p is p1 értéke True). A második után pedig a p2 és a p ugyanaz: p is p2. Ezek egyike sem ugyanaz, mint ami a p = Pont() sor legalul: az létrehoz egy harmadik Pont objektumot is.

Végezzünk méréseket a Python listájának, a beépített list típusnak tesztelésére! A műveletekben az a közös, hogy mind módosítják a lista méretét: hozzáadnak egy elemet, vagy törölnek egy elemet. Méghozzá így: a) elem hozzáfűzése a lista végéhez és eldobása onnan, illetve b) elem beszúrása a lista közepére, és törlése onnan, c) ugyanez a legelején. Mindezeket elvégezzük két listán; az egyik csak ezer, a másik viszont egymillió elemű.

Látható, hogy a lista végét érintő módosítások sebessége független a lista méretétől, 5–6 ms között változott (ez már a mérés pontatlansága lényegében). Akár az ezer elemű, akár az egymillió elemű listáról van szó, ugyanannyi időbe telik elvégezni ezeket a műveleteket százezerszer.

Nem ez a helyzet azokkal a műveletekkel, amelyek a lista közepét módosítják: az egymillió elemű listán ezek a műveletek kb. 500-szor lassabbak. Ha az elejére szúrúnk be és onnan törlünk elemet, akkor ez még szembetűnőbb, több mint ezerszeres a lassulás. Tehát a szükséges idő igen erősen függ a lista méretétől, de csak akkor, ha a belsejébe szúrunk elemet vagy törlünk onnan; ha a végén, akkor független a mérettől. Mi okozza ezt?

A Python a lista típust egy tömbbel valósítja meg. Ez azt jelenti, hogy a listában tárolt adatokat egy összefüggő memóriaterületen, méghozzá az indexek szerinti sorrendben. Vagyis van egy előre lefoglalt memóriaterület, ahova egy adott lista tartalma kerülhet. Ha hozzá szeretnénk fűzni egy elemet a végéhez, az könnyen megy: csak be kell másolni oda. Ha törölni kell egy elemet a lista végéről, az sem gond: lényegében csak le kell csökkenteni a számlálót, amelyik az elemek számát mutatja.

A lista közepébe (vagy akár az elejébe) beszúrás esetén viszont hirtelen elég sok feladat van. Mivel a listában tárolt elemek sorrendjét meg kell tartani, ezért a beszúrandó elemnek helyet kell csinálni: a mögötte álló elemeket egyesével arrébb kell tenni, hogy az új elemnek legyen hely. Minél inkább a lista elejére szúrunk be, annál több adatot kell megmozgatni. Extrém esetben, ha a lista elejére szúrunk be, a teljes adatsort meg kell mozgatni, arrébb kell helyezni a memóriában. A törléssel ugyanez a helyzet: a listában nem lehet lyuk, ezért a hátsó elemeket – akár a teljes listát – előrébb kell eggyel hozni. Ezért lassul le a beszúrás, ha nagy a lista, és ezért még szembetűnőbb a jelenség, ha nem a közepén, hanem a legelején jelenik meg új elem vagy tűnik el egy régi.

Felmerül a kérdés: hogy lehet egy olyan tárolót építeni, amelynek az elejére vagy a közepére is lehet hatékonyan elemet beszúrni, vagy törölni onnan?

Láncolt lista (linked list): adatszerkezet, ahol az egyes elemek (node) láncba vannak fűzve azáltal, hogy tárolják a soron következő elem referenciáját.

A láncolt listába fűzhető elem egy objektum. Az osztálya:

class ListaElem:
    def __init__(self, adat):
        self.adat = adat
        self.kov = None

Egy olyan osztályról van szó, amely tetszőleges adatot (adatokat), és azon felül egy következő referenciát tárol. Így a lista olyan, mintha az elemei egy madzagra lennének felfűzve.

A referencia lehet None is, kezdetben nincs ott semmi, de oda betehetnénk egy másik ilyen ListaElem referenciáját. Az utolsó elemben lévő adattag biztosan None: ezzel a speciális értékkel jelezzük, hogy nincsen további elem a listában.

A lista első elemének referenciáját kell eltárolnunk: ettől elindulva a teljes adatszerkezet bejárható. Az első elemet listafejnek (list head) is nevezzük.

eleje = ListaElem(6)
eleje.kov = ListaElem(9)
eleje.kov.kov = ListaElem(5)
eleje.kov.kov.kov = # ...

Vegyük észre, kezdetben szükségünk van egy változóra, amely az első elem referenciája: eleje = ListaElem(6). Amellett, hogy az első elemben tárolt adat megvan: eleje.adat, létrehozhatunk egy újabb listaelemet is, mert annak referenciáját is van hova tenni, az eleje.kov tagváltozóba. Ugyanezt folytathatjuk bármeddig: a harmadik elem referenciáját a második elem fogja tárolni, az eleje.kov.kov adattag, és így tovább.

A lenti pontok példa kódjaiban mindig ki fogjuk használni, hogy az osztály konstruktora a kov adattagba a None értéket teszi. Tehát vegyük úgy, hogy ennek alapértelmezett értéke None.

A listán ciklussal tudunk végigmenni:

mozgo = eleje
while mozgo is not None:
    print(mozgo.adat)
    mozgo = mozgo.kov   # a referenciát állítja

Nincs új a nap alatt: kezdeti értékadással beállunk az adatszerkezet elejére, aztán amíg túl nem mentünk a végén, addig lépünk a következőre mindig. Az „első” itt a lista első eleme: mozgo = eleje. A „következő” az aktuális elem által mutatott: mozgo = mozgo.kov. A ciklus feltétele az, hogy már nincs elem. Ilyenkor a mozgo változó értéke None; ez az a None, amit a legutolsó elem „következő” referenciájából másoltunk ki. Vagyis a legutolsó elemnél még lefut a ciklus, de olyankor már mozgo.kov értéke None, vagyis végülis az értékadás által maga a mozgo változó is üres lesz.

Hogy szúrunk be egy elemet a lista elejére? Ez a legegyszerűbb művelet: az eleje változó fogja mutatni az új elemet, az új elem következője pedig az lesz, amelyik eddig az első volt.

Az alábbi forráskódban az egyes sorok mutatják azokat a referencia-beállításokat, amelyek a rajzon is megtörténnek. Látszik, hogy mindegyik értékadás, azaz mindegyik referencia beállítása tulajdonképp egy új nyíl megjelenése a rajzon.

uj = ListaElem(adat)    # 1
uj.kov = eleje  # 2
eleje = uj  # 3

1. Új elem létrehozása
2. Az új elem „következő” referenciájának beállítása az „eleje” által jelzett elemre.
3. Az „eleje” változó beállítása az új elemre

Ha az „eleje” mutató kezdetben None, a fenti kód akkor is egy teljes listát helyesen épít fel a teljesen ürestől indulva.

Írjuk meg az előző beszúrást függvényként! A függvény vegye át paraméterként a lista eleje mutatót, és a beszúrandó adatot! Például:

eleje = None
elore_beszur(eleje, 1)  # működhet ez?
elore_beszur(eleje, 2)

Működhet ez így? Biztosan nem! A függvény a változót nem tudja módosítani. Ha a függvény első paramétereként átadjuk az „eleje” változót, akkor csak létrejön egy újabb változó (a függvény paramétere), az „eleje” változó másolataként. Az „eleje” viszont nem fog megváltozni, a beszúrás után még mindig None lesz az értéke. Akármit is csinál az elore_beszur() függvény, a fenti kódrészlet csak hibás lehet! Ezt a problémát még meg kell oldani: a beszúrás által meg kell tudni változtatni a lista elejének címét tároló változót.

A probléma például úgy oldható meg, hogy a függvény mindig visszaadja az új „eleje” referenciát, amivel felül kell írni a tároltat. A függvény használata ez lesz:

eleje = None
eleje = elore_beszur(eleje, 1)  # csak így!
eleje = elore_beszur(eleje, 2)

A beszúró függvény, amely visszatérési értéke az új, megváltozott lista eleje referencia:

def elore_beszur(eleje, adat):
    """Új elemet hoz létre, és a lista elejére fűzi.
    Visszatér a megváltozott lista eleje referenciával."""
    uj = ListaElem(adat)
    uj.kov = eleje
    return uj  # !

Az előbb bemutatott technika kiválóan működik, de elég kényelmetlen. Egyrészt mert ezzel elhasználjuk a függvény visszatérési értékét – mivel oda mindig az új lista eleje referencia kerül, ezért nem jó már másra. Másrészt pedig mert így könnyű rosszul használni ezt a függvényt, elfeledkezni arról, hogy nem a beszur(lista, adat), hanem a lista = beszur(lista, adat) formát kellene használni.

Ehelyett lehet egy másik ötletünk. Mégpedig az, hogy a lista elejére teszünk egy olyan objektumot, egy olyan listaelemet – strázsát –, amelyet nem használunk semmire. Vagyis adatot nem tárolunk benne, de mindig ott van. Ilyenkor az üres lista is már tartalmaz egy elemet, a strázsát; a későbbi beszúrások pedig már a strázsa után fogják tenni a tényleges, adatot is tároló elemeket. Mivel mindig a kezdetben létrehozott strázsa lesz a lista elején, így a lista elejét mutató változó soha nem változik majd meg:

eleje = ListaElem(None)  # üres lista: csak a strázsa

elore_beszur(eleje, 1)   # nem változik az eleje ref
elore_beszur(eleje, 2)

A lista elejére beszúráskor nem a lista elejét tároló változó fog módosulni, hanem a strázsában lévő „következő” referenciát módosítjuk majd. Márpedig a strázsa egy objektum, és mint tudjuk, a függvényparaméteren keresztül ennek az objektumnak a tartalmát módosítani is tudjuk majd, ahogy ez a következő pontban kiderül.

A strázsára a lista bejárásakor figyelni kell majd. Az ugyanis nem tartalmaz adatot, a bejárásnál át kell ugranunk. De ez könnyű, nem mozgo = eleje, hanem mozgo = eleje.kov értékadással indítjuk a ciklust:

def mindet_kiir(eleje):
    """Kiírja a listában tárolt összes adatot."""
    mozgo = eleje.kov  # strázsát átlépi
    while mozgo is not None:
        print(mozgo.adat)
        mozgo = mozgo.kov

Vegyük észre, hogy bár a strázsa nagyobb memóriahasználatot jelent – van egy felesleges objektumunk, amiben nem tárolunk adatot –, valójában ez elhanyagolható. A strázsából mindig csak egyetlen egy darab kell, függetlenül a lista méretétől.

Milyen lett ezáltal a lista elejére beszúró függvényünk?

def elore_beszur(eleje, adat):
    """Új elemet hoz létre, és a lista elejére fűzi.
    A lista elején lévő elemet strázsának tekinti."""
    uj = ListaElem(adat)
    uj.kov = eleje.kov
    eleje.kov = uj      # a strázsa utáni

Ha abban a sorrendben szeretnénk elérni az elemeket, amiben érkeztek, akkor a lista végére kell hozzáfűzni (append) őket. Hogy tudjuk ezt elérni? Mivel csak a lista elejét ismerjük, ezért a hozzáfűzés előtt meg kell keresnünk annak legutolsó elemét. Azt fogja követni az új elem, tehát annak a „következő” referenciáját kell módosítani.

def vegehez_hozzafuz(eleje, adat):
    uj = ListaElem(adat)          # 1
    mozgo = eleje
    while mozgo.kov is not None:  # 2
       mozgo = mozgo.kov
    mozgo.kov = uj                # 3

Feladat: várakozási sor építése.

• Pénztárban sorban álló emberek.
• Web szerverre beérkező, feldolgozandó kérések.

A beszúrás és a törlés is legyen O(1) művelet, a hossztól független!

Vegyük észre: az O(1) elvárás miatt a sima, beépített lista (list típus) nem lenne alkalmas a feladat megoldására. Annak a végéhez általában nagyon gyorsan, elemszámtól függetlenül lehet hozzáfűzni elemet. Viszont az elejéről törölni nagyon nehéz, O(n) ideig tart, mert a teljes adatsort meg kell mozgatni.

A Python maga is tartalmaz egy queue osztályt (import queue), amely sok egyéb tulajdonsággal is rendelkezik a fenti műveleteken túl, amelybe most nem megyünk bele. Amiről szó lesz, az az, hogy hogyan valósítható meg egy ilyen, hogyan működik. Egy láncolt listával ugyanis el tudjuk érni azt, hogy a beszúrás és a törlés is O(1), konstans idejű művelet legyen, azaz ne függjön a lista hosszától.

Láttuk, hogy a láncolt lista elejét könnyű módosítani: beszúrni is pillanat alatt lehet (csak az eleje változót módosítani kell, vagy a strázsában tárolt referenciát), és amúgy törölni ugyanilyen egyszerű. A végéhez fűzni bonyolultabb, ha nem tudjuk, hol van a lánc vége, mert előbb el kell sétálnunk odáig. Most viszont azt szeretnénk, ha az elejét és a végét is tudnánk módosítani könnyen.

Mi kell ehhez? Az, hogy mindvégig ismerjük a lista végét is. Ezért a láncolt lista adatszerkezet felépítése közben nyilvántartjuk nem csak az első (eleje) elem referenciáját, hanem az utolsóét is (vége). Mivel ez a két referencia egyazon listához tartozik, összetartozó adatokról van szó, betesszük őket egy objektumba.

class ListaElem:
    def __init__(self, adat):
        self.adat = adat
        self.kov = None

class VarakozasiSor:
    def __init__(self):
        self.eleje = None
        self.vege = None

Kezdetben a sor üres, egyetlen egy eleme sincs. Ilyenkor az eleje és a vége változók értéke is None. Az üres sort is innen ismerjük meg később.

def sorba_beszur(sor, adat):
    uj = ListaElem(adat)
    if sor.eleje is None:
        sor.eleje = uj
        sor.vege = uj
    else:
        sor.vege.kov = uj
        sor.vege = uj

A sorba új elemet beszúrni, azaz a végéhez hozzáfűzni, nagyon könnyű. Mivel megvan a régi utolsó elem referenciája, semmi dolgunk nincs, csak be kell az abban tárolt „következő” változót állítani az új elemre (sor.vege.kov = uj). Az új elem lesz ezáltal a sor vége, ezt is meg kell jegyezni (sor.vege = uj). Különleges esetként kell kezelni azt, amikor üres a sor, ekkor az eleje és a vége is az új elem lesz egyben.

def sorbol_kivesz(sor):
    if sor.eleje is None:
        raise ValueError("üres")
    kivett = sor.eleje
    sor.eleje = kivett.kov
    if sor.eleje is None:
        sor.vege = None
    return kivett.adat

A sorból kivenni ugyanilyen egyszerű; ehhez a művelethez a lista elejét kell módosítani. Egyszerűen a lista elejét mutató eleje változót át kell állítani a kivett elemet követő elemre: sor.eleje = kivett.kov, persze figyelve arra, hogy az utolsó elem eltávolításánál a vége változó is None értékűre kell változzon.

Mivel a kivett adattal kell visszatérni, a függvény első lépésként ellenőrzi, nem teljesen üres-e a várakozási sor. Ha igen, akkor kivételt dob. Vegyük észre, hogy a két sor.eleje is None feltétel nem ugyanazt jelenti; a kettő között a sor.eleje változót felülírjuk. Az első azt nézi, üres volt-e a sor, mielőtt megpróbáltuk kivenni az elemet; a második pedig azt, hogy üressé válik-e a sor az elem törlése után.

Strázsa használatával kicsit egyszerűsíteni lehetne az algoritmusokon, mert mindkettőből elmaradhatna az üres lista speciális esetként kezelése.

Mikor gyorsabb a láncolt lista a beépített list típusnál?

A bináris fák és algoritmusaik

Minden elemnek két gyereke lehet:

• az elemtől balra a nála kisebb, (kisebbek!)
• tőle jobbra a nála nagyobb (nagyobbak!)

Figyeljük meg, hogy a fenti szabály nem csak a közvetlen gyermekekre igaz! Például az 5-től balra található elemek a 3, 4, 1, 2 mind kisebbek nála. Az a tény, hogy ha egy állítás igaz egy elem bal/jobb oldali gyermekére, akkor az igaz az összes az elemtől balra/jobbra elhelyezkedő elemre, egy nagyon fontos tulajdonsága a bináris fáknak.

class BinfaElem:
    def __init__(self, adat):
        self.adat = adat
        self.bal = None
        self.jobb = None

A fa egy csúcsát egy objektum írja le, amelyben az adatokon túl van két ugyanilyen objektumra mutató referencia: a bal, illetve jobb gyermek. Vagy ha épp arrafelé már nem lehet továbbmenni, akkor None.

Ahogy a listáknak is van eleje, úgy a fáknál is van egy referencia, amely az adatszerkezet kiindulópontját jelenti. Ezt az előbb látott módon a fa gyökerének nevezzük, és egyszerűen egy változóban tároljuk. Ez a változó ugyanolyan szerepet tölt be, mint az egyes csomópontok .bal és .jobb adattagja, amelyek pedig a részfák gyökereit tárolják.

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

a. megvan

b. üres fa

c. nincs benne

A fa teljes bejárása rekurzió nélkül csak nehézkesen oldható meg.
Ha kihasználjuk, hogy ez rekurzív adatszerkezet, akkor egyszerű feladat!

Ha rekurzív az adatszerkezet (vagy eleve a programozási probléma), akkor általában annak megoldása is rekurzív. Itt pont egy ilyen esettel állunk szemben: mivel az adatszerkezetünk felépítése rekurzív (a bal oldali és a jobboldali részfák a teljessel megegyező felépítésűek), ezért a megoldás is ilyen lesz.

Feladat: írjuk ki a fában tárolt számokat!

1. Járjuk be az aktuális elem bal részfáját,
2. Írjuk ki az aktuális csúcsban tárolt számot,
3. Járjuk be az aktuális elem jobb részfáját.

def binfa_sorban_kiir(gyoker):
    if gyoker is None:   # leállási feltétel
        return
    
    binfa_sorban_kiir(gyoker.bal)  # 1
    print(gyoker.adat, end=" ")       # 2
    binfa_sorban_kiir(gyoker.jobb) # 1

if gyoker.bal is not None:
    binfa_sorban_kiir(gyoker.bal)

A megismert algoritmust inorder bejárásnak nevezik, ugyanis a fa elemein növekvő sorrendben hajtja végre a művelet.

Megcserélve a bal és a jobb részfa bejárását, csökkenő a sorrend:

1. Járjuk be a elem jobb részfát (nagyobb elemek),
2. Dolgozzuk fel az aktuális elemet,
3. Járjuk be a bal részfát (kisebb elemek).

Tegyük fel, hogy van egy fa a memóriában, amit szeretnénk fájlba menteni, majd onnan visszaállítani! Ha ezt az inorder bejárással tennénk:

1, 2, 3, 4, …

1, 2, 3, 4, …

A fájlban sorrendben lesznek az elemek, az újra felépített fába rendezetten, a legkisebb elemtől kezdve szúrjuk be az elemeket. Ez azt jelenti, hogy az „1” lesz a gyökér, és minden további elem nagyobb, mint az előző, tehát a fa egy láncolt listává degradálódik. Így a keresés már nem logaritmikus időben fut! Persze ki is egyensúlyozhatjuk a fát (lásd pl. Algoritmusok és gráfok: AVL-fa) – de célravezetőbb egy olyan sorrendet találni a fájlba mentéshez, hogy utána a fa építése könnyen elvégezhető legyen.

Hogy néz ki egy ilyen sorrend? A fát a gyökerétől kezdve tudjuk építeni. Vagyis ebben a sorrendben a gyökérnek kell előbb szerepelnie, csak utána a gyerekeknek. Persze ez így kell legyen rekurzívan az összes szinten. Így jutunk a preorder bejáráshoz: gyökér–bal–jobb.

A preorder bejárás lényege: a gyökeret vesszük előre!

1. Vegyük sorra az aktuális elemet,
2. Járjuk be az aktuális elem bal részfáját,
3. Járjuk be az aktuális elem jobb részfáját.

def binfa_fajlbair(gyoker, f):
    if gyoker is None:   # leállási feltétel
        return
    
    print(gyoker.adat, file=f)       # 1
    binfa_fajlbair(gyoker.bal, f)       # 2
    binfa_fajlbair(gyoker.jobb, f)   # 3

Sokféle kérdés feltehető egy fával kapcsolatban:

• Hány eleme van? Hány levele van? Milyen magas?
• Mekkora egy adott szintjén lévő elemek száma?
• Hányadik szintig van teljesen betöltve?

A fenti feladatokat rekurzív algoritmusokkal lehet könnyen megoldani.

A megoldás sémája

1. A feladatot megoldjuk a bal részfára (rekurzív hívás)
2. A feladatot megoldjuk a jobb részfára (rekurzív hívás)
3. Számbavesszük az aktuális elemet

Feladat: számoljuk meg, hogy hány eleme van egy fának!

1. Ha üres a fa (None-t kaptunk), térjünk vissza 0-val!
2. Különben vegyük az aktuális elem bal részfájának az elemszámát!
3. Adjuk hozzá a jobb részfa elemszámát!
4. Adjunk hozzá 1-et (aktuális elem)! Térjünk vissza így.

def binfa_elemszam(gyoker):
    if gyoker is None:
        return 0  # 1
    
    return (binfa_elemszam(gyoker.bal)  # 2
            + binfa_elemszam(gyoker.jobb)  # 3
            + 1) # 4

Elv: amennyi a bal, plusz a jobb oldalon, meg még a gyökér.

return binfa_elemszam(gyoker.bal) + binfa_elemszam(gyoker.jobb) + 1

Levelek száma: hasonló, de feltételhez kell kötni a számlálást:

1. Ha üres a fa (None kaptunk), 0-val térünk vissza. Üres fában nincs levél sem.
2. Ha az aktuális elem levél, 1-gyel térünk vissza.
3. Különben vegyük az aktuális elem bal részfájában a levelek számát, adjuk hozzá a jobb részfa leveleinek számát, és ezt adjuk vissza.

def binfa_levelszam(gyoker):
    if gyoker is None:
        return 0    # 1
    if gyoker.bal is None and gyoker.jobb is None:  # 2
        return 1

    return (binfa_levelszam(gyoker.bal)
            + binfa_levelszam(gyoker.jobb))

Elv: ha ennek nincs gyereke, akkor levél, tehát 1.

Feladat: adott szinten hány elem van?

1. Üres fa esetén a visszatérési érték 0.
2. Ha az átvett szint értéke 0, akkor azt a szintet kell megszámolni: visszatér 1-gyel.
3. Különben megszámolja a bal és jobb részfában a megfelelő elemeket. Ehhez a szintet eggyel csökkentve hívja magát.

def binfa_szint_elemei(gyoker, szint):
    if gyoker is None:
        return 0    # 1
    if szint == 0:
        return 1    # 2

    return (binfa_szint_elemei(gyoker.bal,  szint-1)  # 3
            + binfa_szint_elemei(gyoker.jobb, szint-1))

A fontos mozzanat itt az, hogy ennek a függvénynek nemcsak, hogy van egy paramétere, hanem azt a paramétert a rekurzióban változtatja is. Hogy hány csúcs van az ötödik szinten, ahhoz azt kell összeadni, hogy hány csúcs van a bal és a jobb oldali részfában a negyedik szinten. Miért negyedik? Mert az ő gyökerükhöz képest kell ott már viszonyítani!

Az algoritmus hasonló a levelek számának meghatározásához: az adott szinten „elvágjuk a fát”, az ott található elemeket levélnek tekintjük, mélyebbre már nem megyünk. Az adott szintig el fogunk jutni, mert a rekurzív hívásban a szint paraméter értéke mindig csökken eggyel; ha ez 0, akkor találtunk egy elemet (és nem nézzük tovább a gyerekeket).

Rekurzívan könnyű az új elem hozzáadása a keresőfához:

• Ha a fa üres, akkor gyökér lesz az új.
• Ha a gyökérnél kisebb az új, a bal oldali részfába kell beszúrni.
• Ha a gyökérnél nagyobb, a jobb oldaliba.
• Amúgy pedig már benne van.

Csakhogy közben változhat a fa gyökere pointer!

Ez ugyanúgy probléma, mint a láncolt listába beszúráskor. Ezt a problémát megoldhatjuk a listáknál megismert módszerrel: mindig visszatérünk a fa gyökerét mutató pointerrel, és a hívóra bízzuk, hogy írja ezt be az azt tároló változóba.

gyoker = None

gyoker = binfa_beszur(gyoker, 5)
gyoker = binfa_beszur(gyoker, 3)
gyoker = binfa_beszur(gyoker, 8)

Az algoritmus:

def binfa_beszur(gyoker, adat):
    if gyoker is None:                        # üres?
        gyoker = BinfaElem(adat)
    elif adat < gyoker.adat:                  # kisebb?
        gyoker.bal = binfa_beszur(gyoker.bal, adat)
    elif adat > gyoker.adat:                  # nagyobb?
        gyoker.jobb = binfa_beszur(gyoker.jobb, adat)
    else:
        pass # benne van
    
    return gyoker

Fontos végiggondolni, mi történik az egyes referenciákkal. Tegyük fel, hogy a függvényt a következő formában hívták meg:

gyoker = binfa_beszur(gyoker, 5)

gyoker = binfa_beszur(gyoker, 5)

gyoker.bal = binfa_beszur(gyoker.bal, 5)

Feladat: készítsünk szavakról statisztikát! Melyik hányszor szerepel?

kutya 2
cica 6
mérési 4
hiba 1

Megoldás: sorban haladunk a beolvasott szavakon; ha az aktuális szó még nincs benne a fában, akkor betesszük és a darabszámot 1-re állítjuk; ha már benne van, akkor megnöveljük a darabszámot.

A fák ideálisak erre a feladatra, hiszen gyors a beszúrás és az „eleme-e” művelet. Bónusz: ábécé rendben kapjuk meg az eredményt. A feladathoz szükséges adatstruktúra:

class BinfaElem:
    def __init__(self, szo):
        self.szo = szo
        self.db = 1
        self.bal = None
        self.jobb = None

A szükséges módosítás a beszúró algoritmuson: le kell kezelni azt az esetet, amikor az elem már benne van a fában. Ilyenkor megnő eggyel az adott szóhoz tartozó számláló.

def szo_szamlal(gyoker, szo):
    if gyoker is None:
        gyoker = BinfaElem(szo)
    elif szo < gyoker.szo:
        gyoker.bal = szo_szamlal(gyoker.bal, szo)
    elif szo > gyoker.szo:
        gyoker.jobb = szo_szamlal(gyoker.jobb, szo)
    else:
        gyoker.db += 1
    return gyoker

Az ehhez tartozó főprogram:

def main():
    szavak = None   # üres fa
    szo = input()
    while szo != "":
        szavak = szo_szamlal(szavak, szo)
        szo = input()
    szostat_kiir(szavak)

A teljes program letölthető innen: binfa_szostat.py.

Kiegyensúlyozott fa: bármely csúcspont részfáinak magassága közötti különbség legfeljebb egy. A bal oldali nem ilyen.

Ha a fa nem kiegyensúlyozott, akkor a keresés lassabb. Az ebben az előadásban bemutatott faépítő algoritmusok nem kiegyensúlyozott fát építenek. Az általuk épített fa kiegyensúlyozottsága attól függ, mennyire érkeznek szerencsésen a beszúrandó adatok. A kiegyensúlyozott építéshez összetettebb algoritmusok szükségesek – ezeket az Algoritmusok és gráfok tárgy mutatta be.

Sorozattárolók

Tömb / Python list

• Gyors, O(1) adatelérés

• Hozzáfűzés/törlés csak a végén gyors

Láncolt lista

• Bárhol gyors lehet a hozzáfűzés/törlés

• Nem indexelhető, csak O(n)

Asszociatív tárolók

Bináris fa

• O(log n) keresés, beszúrás
• Dinamikusan növekszik

• Ki kell egyensúlyozni

Hash tábla

• O(1) keresés, beszúrás

• Előre tudni kell a hozzávetőleges elemszámot