1. Ráhangolódás

Emlékezzünk vissza a referenciákra és az objektumokra!

  • A konstruktorokkal létrehozhatunk egy objektumot: osztályneve(paraméterek...).
  • Ehhez egy referenciát kell kötnünk, különben elveszik.
  • A változók tárolják a referenciákat.
  • Leggyakrabban ezért változóval „fogjuk meg” az objektumot: változó = osztályneve(paraméterek...).
  • Egy objektumnak több referenciája is lehet, több változón keresztül.
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.

2. Vajon hogyan működik a Python list típus?

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ű.

Művelet103 elem106 elem
Hozzáadás/törlés a végén 5–6 ms 5–6 ms
Hozzáadás/törlés a közepén 10–11 ms 6 270 ms
Hozzáadás/törlés az elején 12–13 ms 17 920 ms
100 000 egymás utáni művelet

Látható, hogy a lista végét értintő 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.

Hozzáfűzés a tömb végéhez

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.

Beszúrás a tömb közepére

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?

3. A láncolható elem

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.

Lista eleje
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.

4. A lista bejárása (traversing the list)

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

Ciklus végig a listán

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.

5. Listaépítés – beszúrás előre I.

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.

Új elem a lista elejére

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.

6. Listaépítés – beszúrás előre II.

Í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  # !
Fontos!

A lista elejére kerül az új elem, ezért pont annak a referenciájával tér vissza. Ha nem tároljuk el az új elemet, akkor az elvész! Ezért a függvényt mindig úgy kell használni, hogy a kapott referenciát betesszük abba a változóba, amelyből kivettük.

7. Listaépítés – a strázsa I.

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.


Új elem a lista végére

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.

8. Listaépítés – a strázsa II.

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

Beszúrás a lista elejére, strázsával
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

A beszúrás műveletei ugyanazok, mint eddig:

  1. Létrehozzuk az új listaelemet.
  2. Ez a lista elejére kerül, vagyis őt az eddigi első (strázsa utáni) elem fogja követni: eleje.kov.
  3. És ő lesz a lista első eleme, vagyis a strázsa utáni elem: eleje.kov = uj.

A függvénynek visszatérési értéke nincs, nem is kell: a strázsában lévő referencia beállításával be tudja fűzni az új elemet a listába.

9. Listaépítés – hozzáfűzés

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.

Új elem a lista végére
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

Hozzáfűzés a lista végéhez (append):

  1. létrehozzuk az új elemet,
  2. megkeressük az utolsót (mivel csak az első referenciája van meg),
  3. az utolsó elem „következő” referenciáját beállítjuk az új elem címére. Az új elemé amúgy None.

A ciklus egy apró, de fontos dologban különbözik a bejárás ciklusától. Itt a ciklusfeltétel nem mozgo is not None, hanem mozgo.kov is not None – vagyis a ciklus nem az utolsó elem után áll meg, hanem még az utolsó elemnél. Az utolsó elemet éppen arról ismerjük meg, hogy a benne lévő kov adattag értéke None.

Ha a listánk nem lenne strázsás, itt is külön esetként kellene kezelni az üres listát (olyankor ugyanis az „eleje” változónak kellene megváltoznia, az új elemre mutatnia). Ha van strázsa, akkor ez is könnyebb, mert akkor biztosak lehetünk abban, hogy egy listaelem „következő” referenciája az, amit felül kell írni az új elem referenciájával. Fontos, hogy bár a lista strázsás, a keresést mégis mozgo = eleje értékadással kell kezdenünk: azért, mert lehet hogy épp a strázsa az, amit a ciklusnak meg kell találnia.

10. A várakozási sor (queue)

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

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

Várakozási sor műveletei

Egy várakozási sor a következőket tudja.

  • Sorba állíthatunk, azaz beszúrhatunk a sorba (enqueue) egy új elemet. Ez az elem a sor végére kerül (rear).
  • A sorból kivehetünk, törölhetünk egy elemet (dequeue). Ez az elem mindig a sor elején (front) álló elem.
  • Az adatszerkezet megőrzi az elemek sorrendjét, vagyis mindig az az elem kerül legelőször sorra a törléskor, amelyiket legelőször beszúrtuk (FIFO: first in, first out).

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.

11. Várakozási sor építése láncolt listával

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.

Várakozási sor reprezentációja láncolt listával
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.

12. Várakozási sor listaműveletei

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.

13. Listák hatékonysága

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

művelet láncolt lista Python list
(igazából tömb)
elején módosítás O(1) O(n)
közepén módosítás O(1), ha ismerjük O(n)
végén módosítás O(1), ha ismerjük O(1)
elem véletlen elérése O(n) O(1)

Láttuk, hogy bizonyos speciális helyzetekben a láncolt lista jobban tud teljesíteni, gyorsabb mint a beépített list típus, amely valójában egy tömb.

Legszembetűnőbb az elejére beszúrás, és onnan törlés. Mivel a láncolt lista elejét ismerjük mindig, oda bármikor könnyen be tudunk szúrni egy elemet, vagy törölni tudjuk onnan az elsőt. Mivel ehhez a többit nem kell megmozgatni, a tömb O(n)-jével szemben ez konstans időben elvégezhető: O(1).

A lista közepén és végén is ilyen egyszerű az elemek manipulációja – feltéve, hogy ismerjük a módosítandó elemet. Ha nem, akkor előbb meg kell keresni a lista elejéről indulva, és ez O(n) időbe telik; minél hosszabb a meglévő lista, annál tovább. Ha viszont ismerjük a módosítandó helyet, akkor azonnal el tudjuk végezni a módosítást, és a többi elemtől ez megint független tud lenni: O(1). Ezt legjobban a várakozási sor példája mutatja meg.

Ami problémát jelenthet, az az, hogy nem tudunk bármikor egy adott elemhez ugrani. Míg a beépített lista típust bármikor indexelhetjük, és elővehetjük egy tetszőleges elemét O(1) időben, addig a láncolt listánál ez nincs így: csak sorrendben tudunk haladni, mindig a következő elemre ugorva. Ha szükségünk van egy adott elemre, a lista elejétől kezdve el kell lépkednünk odáig, és az ehhez szükséges idő lineárisan nő a lista méretével: O(n). Vegyük észre, hogy ez sok algoritmus hatékony működését is megakadályozza. Például egy láncolt listán, hiába van rendezve, lényegében nem lehet bináris keresést alkalmazni, mert nem tudunk a közepére ugrani.

A bináris fák és algoritmusaik

15. A bináris keresőfa: rendezett tárolás

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.

A fa elemeinek megnevezéséhez a családfa analógiáját szoktuk használni. Minden csomópontból (node) maximum két nyíl indul ki, a csomópont két gyereke felé. A csomópont maga ilyenkor a szülő csomópont. Leszármazottaknak nevezzük egy csomópont összes gyerekét, azok gyerekeit stb. (Vagyis a gyerekek a közvetlen leszármazottak.)

A fa gyökerének a szerkezet kezdőpontját nevezzük. Ez egy olyan elem, amelyiknek nincsen már szülője. A fa levelei azok a csomópontok, amelyeknek nincsen gyerekük. A fa rekurzív adatszerkezet: egy elem bal oldali gyereke is egy részfa kiindulópontja, jobb oldali is egy részfa. Ezeknek természetesen további részfáik lehetnek.

A fa csomópontjainak megnevezéséhez használjuk a gráfelméletből vett szavakat is. A fa egy gráf: csúcsokból áll, amelyeket élek kötnek össze. Két elem között csak egy út létezik – nincs kör a fában. Az élek irányítottak, a nyíl egy elemtől a másikra mutat, visszafelé nem.

Egy csomópont szomszédai azok, amelyek egy éllel össze vannak kötve (vagyis az adott csomópont szülője és két gyereke). A bal oldali gyereket így nevezhetjük bal oldali szomszédnak, a jobb oldali gyereket pedig jobb oldali szomszédnak. Ilyen értelemben a szülő is szomszéd.

16. A fa reprezentációja Python nyelven

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.

17. Keresés a fában: O(log n)

Algoritmusok
és gráfok
tárgyról ismert

Az algoritmus:

  1. a gyökér elemtől indulunk,
  2. ha az aktuális elem nem létezik, akkor nincs a fában a keresett,
  3. összehasonlítjuk a keresett elemmel:
    • ha pont az, akkor végeztünk,
    • ha nagyobb, akkor balra megyünk tovább,
    • ha kisebb, akkor jobbra megyünk tovább;
  4. folytatjuk a 2. ponttól.

Elvileg minden lépésben feleződik a még megvizsgálandó elemek száma, tehát a keresés O(log2n) időben fut le.

Tudjuk, merre
kell menni!
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 ciklussal addig megyünk, amíg a „mozgo” None nem lesz, és még nem találtuk meg a keresett elemet. A „mozgo” None lehet, mert:

  • a fa még teljesen üres és eleje None-t kaptunk argumentumként,
  • a legutóbbi összehasonlítást egy levélben végeztük és továbbindultunk egy nemlétező gyermek felé.

A logikai rövidzár miatt a ciklus fejében az ÉS kapcsolat második fele már nem értékelődik ki, ha „mozgo” értéke None. Ez nagyon fontos, hiszen egy None értéken a mozgo->adat kifejezés kivételt dobna. A logikai rövidzárat pontosan az ilyen jellegű kifejezések miatt vezették be a nyelvbe. (Persze ha az lett volna a feladat, hogy nem létező elem esetén dobjunk kivételt... De akkor is inkább nekünk illene azt a kivételt dobni egy raise kulcsszóval, hogy megadhassuk a típusát is.

A lehetséges visszatérési értékek:

  • a megtalált elem referenciája,
  • None, mert a fa üres volt és el sem indult a ciklus,
  • None, mert az elemet nem találta meg és egy levél nemlétező gyermekén állt meg a ciklus.
a. megvan
b. üres fa
c. nincs benne

18. A fa bejárása I. – rekurzió

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.

19. A fa bejárása II. – algoritmus

bal–gyökér–jobb

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.

 

A rekurzióban az a szép, hogy a leírás a programban is egyszerű:

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

Leállási feltétel: üres részfához értünk:

  • Vagy az egész fa üres,
  • Vagy az adott részfa üres!

A függvény meghívódik az üres részfákra is!

Megtehetnénk, hogy a rekurzív hívások előtt ellenőrizzük, hogy van-e valami az adott részfában, pl.:

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

Ettől azonban hosszabb lesz a kód, hiszen a függvény első sorában amúgy is mindenképpen ellenőrizni kell, hogy a gyökér None vagy nem. Az egész fa is lehet üres, és az üres fa is fa, amelyre a függvény hívható.

20. A fa bejárása III. – inorder bejárás fordítva

jobb–gyökér–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).

 

21. A preorder bejárás I.

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.

22. A preorder bejárás II.

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.

 

A fájlt, amelybe írjuk az adatokat, természetesen át kell adni paraméterként mindenhol:

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

23. Műveletek fákon – általában

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

24. Műveletek – fák elemszáma

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.

A levelek
gyerekeire is
1 fut le!
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.

Valójában az történik, hogy a return utáni kifejezésben bejárjuk a fát.

Ha üres fára hívjuk meg a függvényt, akkor 0-val tér vissza. De ez nem csak akkor történik, amikor az egész fa üres, hanem minden nem létező gyermeknél.

Ezért tér vissza egy levélnél 1-gyel a függvény. A levélben a 2-es hívás visszatér 0-val (mert a bal részfája nincs), a 3-as hívás is visszatér 0-val (mert jobb oldali gyermeke sincs), és ehhez a 0+0-hoz adunk még egyet, ami a levél maga.

Bármelyik másik részfában hasonlóan történik a számlálás; előbb az adott csomópont bal oldali részfájának elemeit számoljuk meg, majd a jobb oldali részfájának elemeit, végül pedig hozzáadunk 1-et, mert a vizsgált csomópont is egy elemnek számít.

A return utasítás után a zárójelnek csak annyi a szerepe, hogy több sorba írhatjuk általa a kifejezést (így fért ki az előadáson). De alapvetően ezt a kifejezést egyetlen sorba írnánk:

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

25. Műveletek – levelek száma

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.

Itt is bejárjuk a fát.

  • Ha egy levélhez jutunk, akkor 1-et adunk vissza, hiszen neki már nem lehetnek gyermekei, ahonnan egyéb érték érkezhetne. Ilyenkor rekurzív hívásra sincs már szükség (hiszen nincsenek részfák, amelyekben számolni kellene bármit is).
  • Ha nem levélen állunk, akkor megszámláljuk a bal részfában a leveleket (meghívjuk a függvényt a bal gyermekre, majd ugyanezt megtesszük a jobb részfában és a kettő összegével térünk vissza.
  • Üres fa, vagy nem létező gyermek esetén 0-val térünk vissza.

Figyeljük meg, hogy csak akkor nem hívjuk meg a gyermekekre a függvényt, ha levélben vagyunk. Olyankor ha csak az egyik gyermek None, meghívjuk rá, tehát ilyenkor is az (1) feltétel fut le.

26. Műveletek – elemek adott szinten

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).

27. Keresőfa építése I.

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)

28. Keresőfa építése II.

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)
  • Ha a fa üres, akkor gyoker értéke None. Ilyenkor az első feltétel igaz lesz, és keletkezik egy új elem. Végül visszatérünk az új elem címével, és az eredeti gyökér mutatót a hívás után az értékadás fogja átállítani; a függvény ezt hiába próbálná.
  • Ha a fa nem üres, akkor a gyökerében van egy elem. Ennek értékétől függ, hogy az új elemet a bal vagy a jobb oldali részfába kell szúrni. Ha a gyökérnél kisebb a beszúrandó, valahova balra kell kerülnie.
  • Ha a jobb oldali részfába kerül az elem, akkor ugyanez a helyzet.
  • Ha se nem kisebb, se nem nagyobb, akkor a gyökérelemben azt látjuk, amit amúgy is be kell szúrni. Ilyenkor simán visszatérünk, nincs teendő, hiszen az elem már szerepel a fában.

Fontos mozzanat az utolsó: hogy visszatérünk a változatlan gyökér pointerrel. A hívó ugyanis az értékadást mindenképpen elvégzi, és ilyenkor azt kell biztosítani, hogy a teljes fa gyökér pointere ne változzon – ehhez pedig egyszerűen visszaadjuk ugyanazt a gyökér pointert, amit kaptunk.

Ha a gyökér létezik, és annak a bal oldali részfájába szúrunk be, akkor hasonlóan megy minden. Ha ott None van, akkor az felülíródik. Ha nem None, akkor az ott meghívott függvény változatlan referenciával tér vissza, vagyis az értékadásból gyoker.bal = gyoker.bal lesz végül. Minden helyen ez lesz a helyzet, kivétel ott, ahol valamelyik helyen üres fa van!

Ebből következik a függvény hívásának módja a függvény belsejében is. Ha azt mondtuk, hogy a függvényt így kell használni:

gyoker = binfa_beszur(gyoker, 5)

Akkor a bal oldali részfába beszúrásnál ezt kell írnunk:

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

29. Példa – szavak statisztikája

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

30. Példa – szavak statisztikája, megvalósítás

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.

31. Keresőfa építése – hatékonyság

B-fák, AVL-fák, …
Algoritmusok és
gráfok tárgy

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.

32. Fák alkalmazásai – hierarchia

Hierarchia tárolása.
Műveletek, pl. (2+3)*5.
Nincs szükség zárójelezésre!
Dekódoló fa.
Morze: ti = balra, tá = jobbra.

Hierarchia tárolása

A matematikai műveletek – sőt általában a programozási nyelvek szövegei – leírhatók ún. absztrakt szintaxisfákkal (abstract syntax tree), más néven kifejezésfákkal. Ilyenekről már esett szó az operátorok kapcsán. Ezekben a hierarchia nem kisebb–nagyobb viszonyt jelent, hanem az operátorok és az operandusok összerendeléseit adja meg. Vegyük észre, hogy ebben a levelek a konstansok, a köztes csomópontok az operátorok.

Szintén hierarchiát tárolnak a fájlrendszerek. Ezekben a fájlokat mappákba rendezhetjük, a mappák saját maguk is kerülhetnek mappákba – ezeket is felrajzolhatjuk egy fában.

Dekódoló fák

A második rajz egy dekódoló fát mutat. Ebben a balra és jobbra irány megint nem kisebb vagy nagyobb elemet jelent, hanem a morzekód két elemét, a ti és a tá jelet. Egy jelsorozat dekódolásakor mindig a gyökértől indulunk, és balra vagy jobbra megyünk a jeltől függően; pl. a .-., azaz a ti-tá-ti jel balra-jobbra-balra lépést jelent (amúgy az R betű kódja). Ha ilyen adatszerkezetünk van, akkor nem kell keresgélnünk egy tárolóban a jelsorozatot, hanem ahogy érkezik, folyamatosan járjuk be a fát, és mire vége a sornak, épp ott állunk benne, ahol kell.

Ilyen dekódoló fákat alkalmaznak például a tömörítőprogramok is (ZIP).

33. Adatszerkezetek – összefoglalás

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)

A sorozattárolók megőrzik az elemek sorrendjét. Vagyis nem csak az elemeket tárolják, hanem hozzájuk tartozóan egy sorrendet is: ezeknek van eleje, vége, van első elem, utolsó elem, és mindegyik adat ott lesz, ahova tesszük.

Mint láttuk, a tömb egy összefüggő memóriaterület, ezért az elejébe, közepébe beszúrni új adatot csak a többi elem megmozgatásával lehet. A láncolt listánál ez könnyebben megy, csak pár referenciát át kell állítani – ott viszont nem tudunk egy tetszőleges elemre ugrani, csak egyesével lehet lépkedni az adatokon.



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

Az asszociatív tárolók nem őrzik meg az elemek sorrendjét: ezekben nem tudjuk megmondani utólag, hogy milyen sorrendben kerültek be az elemek. Ilyen értelemben sorrendről se lehet ezeknél beszélni; nincs első és nincs utolsó elem sem. Az adatokat úgy rendezik, hogy utána valamilyen szempont szerint könnyű, gyors legyen bennük a keresés. Ezt a szempontot nevezzük a keresés kulcsának.

A bináris fa építéséhez az kell, hogy az elemeket a keresés szempontja szerint növekvő sorba tudjuk állítani: melyik a kisebb, melyik a nagyobb. Ahhoz viszont, hogy hatékony legyen a fánk, bonyolultabb algoritmusok kellenek az itt bemutatottaknál, ugyanis figyelni kell a kiegyensúlyozásra.

A hash táblánál lényegében tömbbe tesszük az adatokat, de a tömbbeli indexet egy hash függvény határozza meg. Így bármelyik elemről azonnal, O(1) meg tudjuk mondani, hol a helye. A hash táblák hatékonysága leromlik akkor, ha nagyon tele vannak, és az átméretezésük, nyújtásuk költséges művelet. Erről az Algoritmusok és gráfok tárgyon volt szó, itt nem térünk rá ki külön.