Dinamikus adatszerkezetek II. – Bináris fák

A láncolt listák előnye: nagyon gyors és egyszerű a méretüket megváltoztatni (beszúrás/törlés), í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).

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

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 strukú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

c. üres fa

b. nincs benne

struct BinFa {
   int szam;
   struct BinFa *bal, *jobb;
};

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

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
}

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!=NULL)
   sorban_kiir(gyoker->bal);

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

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.

Csak leveleket szabad felszabadítani!

1. Járjuk be az aktuális elem bal részfáját,
2. Járjuk be az aktuális elem jobb részfáját,
3. Szabadítsuk fel az aktuális elemet.

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!

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 *fajl) {
   if (gyoker==NULL)   // leállási feltétel
      return;

   fprintf(fajl, "%d ", gyoker->adat); // 1
   fajlba_kiir(gyoker->bal, fajl);         // 2
   fajlba_kiir(gyoker->jobb, fajl);    // 3
}

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

• Hány eleme van? Hány levele van?
• Mekkora egy adott szintjén lévő elemek száma?
• Milyen magas?
• 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
}

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);
}

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 jobboldali részfában a negyedik szinten. Az ő gyökerükhöz képest negyedik szinten!

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!

BinFa *gyoker = NULL;

gyoker = beszur(gyoker, 5);
gyoker = beszur(gyoker, 2);
gyoker = beszur(gyoker, 7);

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

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

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

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:

int main() {
   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) {
    int er;

    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! */
    }
    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;
}

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ás mégis megoldható pointerrel:

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

int x=5;

novel(&x);  // x címe
printf("%d", x);

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

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); /* x=17, y=29 */

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

int *px=&x; int *py=&y;
ptr_csere(&px, &py); /* px=&y, py=&x */

A lista elejére beszúró függvény a múltkori módon:

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:

A másik változata, ami az „eleje” pointer címét veszi á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;
}

A múltkorinál a visszaadott mutatót be kellett másolni a változóba:

ListaElem *eleje=NULL;

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

A mostani függvény cím szerint kapja azt, ezért meg tudja tenni azt is:

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!

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 *mozog;
      for (mozog=*peleje; mozog->kov!=NULL; mozog=mozog->kov)
         ; /* üres ciklus */
      mozog->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, vagy kívül, a hívónál!

void vegere(ListaElem **peleje, int adat) {
   ListaElem **pmozgo, *uj;

   pmozgo=peleje;        // pointer megkeresése
   while (*pmozgo!=NULL)
      pmozgo=&(*pmozgo)->kov; // !

   uj=(ListaElem*) malloc(sizeof(ListaElem)); // új elem
   uj->adat=adat;
   uj->kov=NULL;
   *pmozgo=uj;           // a megtalált NULL pointer felülírása
}

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.

A függvény elején a ciklus ezért ezt teszi: megkeresi azt a NULL pointert. A pmozgo 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 pmozgo 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: *pmozgo a listaelemre mutató pointer, (*pmozgo)->kov az abban tárolt „következő” pointer, &(*pmozgo)->kov pedig annak a címe.

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. samely 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.
 * Egy olyan címet ad vissza, ahol a leendő elem címének
 * kell tárolódnia, vagy ahol a megtalált elem címe tárolódik. */
BinFa **beszurashoz_keres(BinFa **pgyoker, int adat) {
   BinFa **pmozgo=pgyoker;

   while (*pmozgo!=NULL && (*pmozgo)->adat!=adat) {
      if (adat < (*pmozgo)->adat)
         pmozgo=&(*pmozgo)->bal;
      else
         pmozgo=&(*pmozgo)->jobb;
   }

   return pmozgo;
}

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

Emlékeztetőül itt a kétszeres indirekció nélküli keresés. Érdemes összehasonlítani – lényegében annyi a különbség, hogy egyikben mindenhol mozgo van, másikban mindenhol *pmozgo. Ahol a lentiben konkrét érték van (mozgo), ott a fentiben cím, amelyet dereferálni kell (*pmozgo). Ahova a lentiben konkrét érték kerül (mozgo=), oda a fentiben cím kell (pmozgo=), ezért címet kell képezni (pmozgo=&...).

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

Elem megtalálása

• Rendezetlen tömbben lineáris keresés: O(n)
• Rendezett tömbben bináris keresés: O(log n)
• Listában: O(n)
• Keresőfában: O(log n)

Vajon lehet ennél jobbat?

O(1) lépésben

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

Kulcs → érték párok tárolása

• Viszonylag nagy tömböt foglalunk
• hash() függvény: kulcs→tömbindex (to hash = összekever, összezagyvál)

Jó hasító függvény?

• gyors,
• egyenletesen helyezi el az adatokat

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 helyezzük el a táblában.

• Így az adatok elcsúszhatnak a helyükről.
• Az egymás utániaknál, ahol nem üres, lineárisan keresünk
• Törlésnél problémás: meg kell maradnia a törölt elemnek, csak megjelöljük, hogy törölt
• A tábla így töredezetté válik, időnként karbantantartást igényel

Az ütköző elemeket láncolt listába tesszük:

Kevés ütköző elem → néhány elem a listákban. Gyors keresés!

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");

Google keresés?

• Kulcs: keresett szó
• Érték: weboldalak listája
• az ütközés természetes: egy szó több helyen megtalálható

Fájlcserélő: elosztott tábla

• Kulcs: fájl neve, érték: a fájl (vagy hivatkozás a fájlra)
• Hasító függvény kimenete: mely gépen tároljuk az adatot
• Pl. BitTorrentnél: fájl darabjai kinél találhatóak meg