Dinamikus adatszerkezetek II. – Bináris fák

• Előnyük: nagyon gyors és egyszerű a méretüket megváltoztatni. Így alkalmasak dinamikusan változó számú adat kezelésére.

• Hátrányuk: csak lineáris keresés valósítható meg bennük.

Az ideális az lenne, ha olyan adatszerkezetünk lenne, ami

• gyorsan nyújtható, mint egy láncolt lista,
• gyors keresést biztosít, mint egy rendezett tömb (bináris keresé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.

typedef struct BinFa {

   …    // tetszőleges adat

   struct BinFa *bal, *jobb;
} BinFa;

A fa egy csúcsát egy struktúra írja le, amelyben az adatokon túl van két ugyanilyen struktúrára mutató pointer: a bal, illetve jobb gyermek címei.

Érdekesség: nyelvi szinten nem látszik a különbség egy duplán láncolt lista és egy bináris fa között. A különbség abban áll, hogy másra használjuk az adatok mellé tett két pointert.

BinFa *keres(BinFa *gyoker, int adat) {
   BinFa *mozgo = gyoker;
   while (mozgo != NULL && mozgo->adat != adat) {
      if (adat < mozgo->adat) mozgo = mozgo->bal;
      else mozgo = mozgo->jobb;
   }
   return mozgo;
}

a. megvan

b. üres fa

c. nincs benne

Az algoritmus

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.

void sorban_kiir(BinFa *gyoker) {
    if (gyoker == NULL)   // leállási feltétel
       return;
 
    sorban_kiir(gyoker->bal);     // 1
    printf("%d ", gyoker->adat);     // 2
    sorban_kiir(gyoker->jobb);    // 3
}

if (gyoker->bal != NULL)
    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).

Ha egy teljes fát szeretnénk felszabadítani, vigyázni kell: nehogy magunk alatt vágjuk a fát, azaz nehogy elveszítsük a hozzáférést elemekhez. Felszabadításkor mindig leveleket szabad csak törölni. Olyan bejárásra van szükség, amely először a leveleket járja be, majd azokat az elemeket, amik a korábbi levelek felszabadítása után levéllé válnak és így tovább.

1. Járjuk be az aktuális elem részfáit,
2. Szabadítsuk fel az aktuális elemet.

Csak leveleket szabad felszabadítani!

A törlés C-ben

Előbb a részfákat felszabadítjuk, utána mehet a gyökérelem is:

void felszabadit(BinFa *gyoker) {
    if (gyoker == NULL)   // leállási feltétel
        return;
    
    felszabadit(gyoker->bal);     // 1
    felszabadit(gyoker->jobb);       // 2
    free(gyoker);                 // 3
}

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!

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.

void fajlba_kiir(BinFa *gyoker, FILE *ki) {
    if (gyoker == NULL)   // leállási feltétel
        return;
    
    fprintf(ki, "%d ", gyoker->adat); // 1
    fajlba_kiir(gyoker->bal, ki);         // 2
    fajlba_kiir(gyoker->jobb, ki);    // 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 (NULL pointert 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.

int elemszam(BinFa *gyoker) {
    if (gyoker == NULL) return 0; // 1
    
    return elemszam(gyoker->bal)  // 2
         + elemszam(gyoker->jobb)    // 3
         + 1;                     // 4
}

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

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

1. Ha üres a fa (NULL pointert kaptunk), térjünk vissza 0-val!
2. Ha az aktuális elem levél, térjünk vissza 1-gyel!
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, térjünk ezzel vissza!

int levelszam(BinFa *gyoker) {
    if (gyoker == NULL) return 0;          // 1
    
    if (gyoker->bal == NULL && gyoker->jobb == NULL) // 2
        return 1;
    
    return levelszam(gyoker->bal)          // 3
         + 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.

int szint_elemei(BinFa *gyoker, int szint) {
    if (gyoker == NULL) return 0;   // 1
    if (szint == 0) return 1;   // 2
    
    return szint_elemei(gyoker->bal,  szint-1)  // 3
         + szint_elemei(gyoker->jobb, szint-1);
}

A fontos mozzanat itt az, hogy ennek a függvénynek nem csak, hogy van egy paramétere, de 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. Az ő gyökerükhöz képest negyedik szinten!

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 szintre visszaszámlálással jutunk, amikor a szint értéke 0, akkor regisztráljuk, hogy 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. Ott is a mellékhatás volt a lényeg, hogy változik a lista, és itt is az: változik a fa. 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.

BinFa *gyoker = NULL;

gyoker = beszur(gyoker, 5);
gyoker = beszur(gyoker, 3);
gyoker = beszur(gyoker, 8);

Megoldás: térjünk vissza vele, mint a listáknál.

BinFa *beszur(BinFa *gyoker, int adat) {
    if (gyoker == NULL) {                        // üres?
        BinFa *uj = (BinFa*) malloc(sizeof(BinFa));
        uj->bal = uj->jobb = NULL;    /* levél lesz */
        uj->adat = adat;
        return uj;     /* vissza kell térni vele! */
    }

    if (adat < gyoker->adat)                // kisebb?
        gyoker->bal = beszur(gyoker->bal, adat);
    else if (adat > gyoker->adat)                // nagyobb?
        gyoker->jobb = beszur(gyoker->jobb, adat);
    else
        ; /* benne van */

    return gyoker;
}

gyoker = beszur(gyoker, 5);

gyoker = beszur(gyoker, 5);

gyoker->bal = 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 fájl szavain; 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:

typedef struct SzoStat {
    char szo[51];
    int db;
    struct SzoStat *bal, *jobb;
} SzoStat;

A szabványos bemeneten érkező szöveg statisztikájának az elkészítése az alábbi főprogrammal oldható meg. Ebben kihasználjuk, hogy a scanf %s whitespace-ig olvas:

int main(void) {
    SzoStat *fa = NULL; // üres fa
    char szo[51];
    
    while (scanf("%s", szo) == 1)
        fa = beszur(fa, szo);
    
    kiir(fa);
    felszabadit(fa);
    
    return 0;
}

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, és strcmp()-vel kell végezni a sztringek összehasonlítását.

SzoStat *beszur(SzoStat *gyoker, char *szo) {
    if (gyoker == NULL) {
        SzoStat *uj = (SzoStat*) malloc(sizeof(SzoStat));
        strcpy(uj->szo, szo);
        uj->db = 1;
        uj->bal = uj->jobb = NULL;
        return uj;     /* vissza kell térni vele! */
    }
    
    int er = strcmp(szo, gyoker->szo);
    if (er < 0)
        gyoker->bal = beszur(gyoker->bal, szo);
    else if (er > 0)
        gyoker->jobb = beszur(gyoker->jobb, szo);
    else
        gyoker->db++;

    return gyoker;
}

A teljes program letölthető innen: szostat.c.

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 majd az Algoritmuselmélet nevű tárgy fogja bemutatni.

Kettős indirekcó

C-ben csak érték szerinti paraméterátadás van. A függvények a paraméterek másolatát kapják. A cím szerinti paraméterátadást ezért pointerrel oldjuk meg.

A cím szerinti paraméterátadás megoldható pointerrel:

void novel(int *p) {
    (*p)++;       // a mutatott integert
}


int x = 5;
novel(&x);         // x-re mutat

printf("%d", x);

void csere(VALAMI *p1, VALAMI *p2) {
    VALAMI temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

void int_csere(int *p1, int *p2) {
    int temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

int x = 29;
int y = 17;
int_csere(&x, &y);

void ptr_csere(int **p1, int **p2) {
    int *temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

int *px = ...;
int *py = ...;
ptr_csere(&px, &py);

A listás, fás algoritmusaink megváltoztatják a lista eleje, fa gyökere mutatót. Ötlet: azt ugyanígy kellene átadni!

Eddig a listák építésekor a visszaadott mutatót bemásoltuk a változóba:

ListaElem *eleje = NULL;

eleje = elore_beszur(eleje, 2);
eleje = elore_beszur(eleje, 3);

A mostani tervünk: adjuk át cím szerint, rábízva a változtatást!

ListaElem *eleje = NULL;

elore_beszur_ptr(&eleje, 2);
elore_beszur_ptr(&eleje, 3);

A nagy előny: így nem lehet kifelejteni az értékadást!

ListaElem *elore_beszur(ListaElem *eleje, int adat) {
    ListaElem *uj = (ListaElem*) malloc(sizeof(ListaElem));
    uj->adat = adat;
    uj->kovetkezo = eleje;
    return uj;
}

A függvénynek meg kell tudnia változtatni a lista eleje mutatót:

void elore_beszur_ptr(ListaElem **peleje, int adat) { // !
    ListaElem *uj = (ListaElem*) malloc(sizeof(ListaElem));
    uj->adat = adat;
    uj->kovetkezo = *peleje; // *peleje – az első elem címe
    *peleje = uj;
}

Beszúrás lista végére, és az „eleje” mutató címének átvétele:

void vegere(ListaElem **peleje, int adat) {
    ListaElem *uj = (ListaElem*) malloc(sizeof(ListaElem));
    uj->adat = adat;
    uj->kov = NULL;
    
    if (*peleje == NULL) {
        *peleje = uj;     // eleje ptr változik
    } else {
        ListaElem *iter;
        iter = *peleje;
        while (iter->kov != NULL)
            iter = iter->kov;
        iter->kov = uj;  // az utolsó „következő”-je változik
    }
}

Vegyük észre: van valahol egy ListaElem* mutató, amit be kell állítani. Vagy az utolsó elemben (az egyik listaelemen belül), vagy kívül, a hívónál (nem listaelemben)!

Egy lehetséges módosított algoritmushoz az előző felismerés adja az ötletet – nevezetesen az, hogy a lista végére szúrás azt jelenti, hogy meg kell keresni a lista végén azt a NULL pointert, amelyik lezárja azt. Mindegy, hogy ez a lista végi elemben van, vagy a lista eleje pointer a NULL (üres lista esetén) – a feladat az, hogy felülírjuk azt a mutatót az új elem címével.

void vegere(ListaElem **peleje, int adat) {
    ListaElem **mozgo = peleje;        // pointer megkeresése
    while (*mozgo != NULL)
       mozgo = &(*mozgo)->kov; // !
    
    ListaElem *uj = (ListaElem*) malloc(sizeof(ListaElem));
    uj->adat = adat;
    uj->kov = NULL;
    *mozgo = uj;           // a megtalált NULL pointer felülírása
}

A függvény elején a ciklus ezért ezt teszi: megkeresi azt a NULL pointert. A mozgo pointer ennek a pointernek a címét tárolja. Először a lista eleje pointerre mutat, utána pedig minden lépésben a mutatott listaelem következő pointerére állítjuk át. Fontos az indirekciók számában a különbség: a mozgo pointer itt nem a listaelemre mutató pointer, hanem a listaelemre mutató pointerre mutató pointer. Vagyis a listaelem címét tároló változó címe. Így először a hívó eleje pointerének címét tárolja, utána az első listaelem kov pointerének címét stb. Ezért van szükség a címképző operátorra is a ciklustörzsben: *mozgo a listaelemre mutató pointer, (*mozgo)->kov az abban tárolt „következő” pointer, &((*mozgo)->kov) pedig annak a címe. Mivel a nyíl operátor magasabb precedenciájú, ebből a külső zárójel lehagyható. Így születik meg a fenti kódban látható &(*mozgo)->kov kifejezés.

A keresőfába beszúráshoz meg kell keresni azt, hogy hol kell legyen a beszúrandó elemre mutató pointer. Ha a fa üres lenne, akkor a legfelső, azaz a gyökérpointert kellene úgy módosítani, hogy az az új elemre mutasson. Ha a 0-t szeretnénk beszúrni, akkor az 1-es csomópont bal pointerét (amely jelenleg NULL pointer) kell úgy módosítani, hogy az az új elemre mutasson. Ha a 4-est keressük, az benne van a fában – a 3-as csomópont jobb pointere az, amely rá mutat, és ilyenkor a beszúráshoz nem kell tenni semmit.

Azt keressük, hogy hol az a pointer, amely majd mutat rá.
Ez valamelyik csomópont bal/jobb pointere, vagy a gyökér pointere.

Ha van egy ilyen keresőalgoritmusunk, amely nem a keresett elemre mutató pointert adja vissza, hanem a keresett elemre mutató pointer címét, akkor könnyű a beszúrás. Ha nincs meg a keresett elem, ez akkor is értékes választ ad: a visszaadott pointer egy olyan pointerre mutat, amely értéke NULL, de ott kellene legyen a keresett elemre mutató pointer. A beszúrás:

/* új csomópontot szúr a keresőfába.
 * A gyökerpointert cím szerint veszi át. */
void beszur(BinFa **pgyoker, int adat) {
    /* megkeresi a helyét */
    BinFa **ptr = beszurashoz_keres(pgyoker, adat);
    
    if (*ptr == NULL) {                   // ha még nincs
        BinFa *uj = (BinFa*) malloc(sizeof(BinFa));
        uj->adat = adat;
     
        uj->bal = uj->jobb = NULL;
        *ptr = uj;                        // beszúrás
    }
}

BinFa *gyoker = NULL;
beszur(&gyoker, 5);

A kettős indirekció a keresésben:

/* Megkeresi az adott elem (leendő) helyét a fában.
 * A leendő elem címének helyét adja vissza (NULL),
 * vagy a megtalált elem címét (nem NULL). */
BinFa **beszurashoz_keres(BinFa **pgyoker, int adat) {
    BinFa **mozgo = pgyoker;
   
    while (*mozgo != NULL && (*mozgo)->adat != adat) {
        if (adat < (*mozgo)->adat)
            mozgo = &(*mozgo)->bal;
        else
            mozgo = &(*mozgo)->jobb;
    }
   
    return mozgo;
}

Mivel mutatók címével tér vissza, azok értékét felül tudjuk írni.

BinFa *keres(BinFa *gyoker, int adat) {
    BinFa *mozgo = gyoker;
 
    while (mozgo != NULL && mozgo->adat != adat) {
        if (adat < mozgo->adat)
            mozgo = mozgo->bal;
        else
            mozgo = mozgo->jobb;
    }
 
    return mozgo;
}

Hash táblák

Hogyan lehetne Θ(1) lépésben keresni?

Honnan tudjuk, hogy hol keressük? Onnan, hogy tudjuk, hova raktuk!

A hash táblázatok (hash table) ötlete az, hogy foglalunk egy nagy tömböt, amelybe az adatokat tesszük, és kitalálunk egy olyan függvényt, amely a tárolandó adatokat (értékek, pl. telefonszám) a keresés kulcsa (pl. név) szerint szétszórja a tömbben (to hash = összekever, összezagyvál). Így bármikor, ha adott a kulcs, akkor a függvény megmondja a tömbindexet, és egyből, keresés nélkül látjuk is az elemet.

Láthatóan így a hash() függvény gyorsaság fogja meghatározni a keresés idejét: ha az visszatért, onnan már csak egy tömbindexelés van hátra, és megtaláltuk az adatot.

A használat elve:

Adat hash_tabla[MERET]; // a hash tábla: tömb

printf("Telefon: %s\n", hash_tabla[hash("Taz")].telszam);

A kulcsot le kell képezni a 0 … MÉRET-1 tartományra. Példa hash függvények (nem túl jók):

int egesz_hash(int i) {
    return i % MERET;
}

int sztring_hash(char *nev) {
    return ((nev[0]-'A')*26 + (nev[1]-'a')) % MERET;
}

Ütközések: ha két kulcs ugyanoda „hashelődik”:

kulcs % MÉRET == (kulcs + MÉRET) % MÉRET

Pl. a fenti függvénnyel Taz és Tapsi Hapsi.

Az ütköző adatokat egymás után helyezhetjük el a táblában.

Ez az ún. nyílt címzés. Így viszont az adatok elcsúszhatnak a helyükről. Az egymás utániaknál, ahol nem üres, lineárisan kell keresünk. Ez a törlésnél problémás: meg kell maradnia a törölt elemnek (különben megállna a keresés az üres elemnél), így nem szabad törölni, csak megjelölni, hogy törölt az elem. A tábla így szép lassan töredezetté válik, és időnként karbantartást igényel.

Az ütköző elemeket láncolt listába is tehetjük. Kevés ütköző elem → néhány elem a listákban. Gyors keresés! C kód

typedef struct ListaElem {
    char nev[51];
    char telefonszam[20];
    struct ListaElem *kovetkezo;
} ListaElem;

ListaElem *hashtabla[MERET];  /* listák tömbje */

char keresett[] = "Tapsi Hapsi";
index = hash(keresett);
talalt = listakeres(hashtabla[index], keresett);
if (talalt != NULL)
    printf("Telefonszáma: %s\n", talalt->telefonszam);
else
    printf("Nincs ilyen név!\n");

Ez pedig az ún. vödrös hash. Vödröknek nevezzük a láncolt listákat, amelyekben az ütköző elemek gyűlnek.