Info2/2008tavasz/kuka

A lap 2008. március 21., 01:38-kori változata

5. előadás (2008-03-21)

Struktúrák igazítása

A 2/4/8 hosszú adatok (short/int/double/...) csak 2/4/8-cal osztható címen kezdődhetnek.

~/info2/igazit.c

/* megnézzük, hogy a struktúrában hogy történik az igazítás */
#include <stdio.h>

int main(void) {
  struct igazito {
    int a;
    char b;
    double d;
    char f;
    struct igazito *p;
  } ig={1, 'w', 3.4, 'f', &ig};

  printf("\n%d %p, %c %p, %f %p, %c %p\n%p %p\n", 
    ig.a, &ig.a, ig.b, &ig.b, ig.d, &ig.d, ig.f, &ig.f, ig.p, &ig.p);
  return 0;
}

Bináris keresőfák

Bináris fa

• csúcs
• él
• gyerek
• szülő
• bináris fa (ha minden csúcsnak 0, 1 vagy 2 gyereke van)
• gyökér
• belső csúcs (akinek van gyereke -- akár a gyökér is lehet belső csúcs)
• levél (akinek nincs gyereke -- akár a gyökér is lehet levél)
• bal részfa
• jobb részfa
• részfa gyökere

A bináris keresőfa olyan bináris fa, melynek minden csúcsában egy érték szerepel, és minden csúcsára igaz, hogy a bal részfában szereplő értékek mind legfeljebb akkorák, mint a csúcsban szereplő érték, és a jobb részfában szereplő értékek mind legalább akkorák, mint a csúcsban szereplő érték. Néha kikötik, hogy egy érték csak egyszer szerepelhet (ez egyszerűsíti a bináris fában végzett műveleteket).

Példa bináris keresőfára:

      0
     / \
    /   \
   -5    3
  / \     \
-10  -5    42
    / \
   -5  -2

Alapműveletek bináris keresőfákkal:

• keresés
• új érték beszúrása
• érték törlése

Egyéb művelet bináris keresőfákkal:

• kiegyensúlyozás: a fa átalakítása a benne levő értékek megtartásával úgy, hogy a magassága (jóval) kisebb legyen.

Példa kiegyensúlyozásra:

  1
 / \
0   2                          3
     \                        / \
      3                      /   \
       \            -->     /     \
        4                  1       5
         \                / \     / \
          5              0   2   4   6
           \
            6

Kiegyensúlyozott fa (ez egy nem túl precíz fogalom): olyan bináris fa, amelynek minden csúcsára igaz, hogy a bal részfában nagyjából ugyanannyi csúcs van, mint a jobb részfában.

Részfa magassága: a részfa gyökerétől egyik leveléig menő leghosszabb úton levő csúcsok száma.

AVL-fa (precíz fogalom, a kiegyensúlyozott fák egy fajtája): olyan bináris fa, melynek minden csúcsára igaz, hogy a bal részfa magassága és a jobb részfa magassága közti különbség -1, 0 vagy +1.

Keresés bináris keresőfában: A feladat az, hogy keressünk egy olyan csúcsot a fában, ahol az adott érték szerepel. Ha több ilyen csúcs is van, akkor bármelyik jó.

A bináris fában való keresés (rekurzív) algoritmusa:

1. A gyökértől indulunk.
2. Ha az aktuális csúcsban a kívánt érték szerepel, készen vagyunk.
3. Ha a bal részfa nem üres, és az aktuális csúcsban a kívánt értéknél nagyobb érték szerepel, a bal részfa gyökerével folytatjuk (a 2. lépéstől).
4. Ha a jobb részfa nem üres, és az aktuális csúcsban a kívánt értéknél kisebb érték szerepel, a jobb részfa gyökerével folytatjuk (a 2. lépéstől).
5. A keresést befejezzük, az adott érték nem található meg a fában.

Beszúrás bináris keresőfába: A feladat az, hogy szúrjunk be a fába egy új értéket úgy, hogy az továbbra is bináris keresőfa maradjon.

Látható, hogy a keresés legfeljebb annyi lépésből áll, amennyi a fa magassága. AVL-fánál (és sok egyéb kiegyensúlyozott fánál is) egy n csúcsot tartalmazó fa magassága O(log n), tehát a keresés gyors. Szélsőséges esetben, például ha a fa csúcsainak csak jobboldali gyerekük van, az egész fát be kellhet járni (O(n)).

A bináris fa egy csúcsát struktúraként definiáljuk:

struct csucs {
  int ertek;
  struct csucs *bal;
  struct csucs *jobb;
};

Példa a fenti bináris fa azon részfájának létrehozására, ami a 3-ból indul lefele:

#include <stdlib.h> /* a NULL miatt */

int main(int argc, char**argv) {
  struct csucs a, b;
  a.ertek=3;
  a.bal=NULL;
  a.jobb=&b;
  b.ertek=42;
  b.bal=NULL;
  b.jobb=NULL;
  return 0;
}

Célunk, hogy meg tudjuk írni a bináris keresőfába való beszúrás algoritmusát.

A bináris keresőfába való beszúrás algoritmusa:

1. A gyökértől, pontosabban a gyökér kezdőcímétől indulunk.
2. Paraméterként kapjuk az aktuálisan vizsgálandó részfa gyökerének címét. (Üres fa esetén van lényeges különbség: az üres fa gyökere ugyanis NULL, az üres fa gyökerének címe pedig az a memóriaterület, ahol a NULL-t majd átírjuk másra.)
3. Ha az aktuális gyökér NULL, akkor cseréljük le a beszúrandó csúcsra: a csúcs értéke a beszúrandó érték legyen, a bal és jobb mutatók pedig NULL-ok legyenek.
4. Ha a beszúrandó érték megegyezik az aktuális gyökérben található értékkel, és az aktuális gyökérnek nincs bal gyereke, folytassuk a jobb részfával (a 3. lépéstől). (Az algoritmus e lépés nélkül is jól működne.)
5. Ha a beszúrandó érték legfeljebb akkora, mint az aktuális gyökérben található érték, akkor folytassuk a bal részfával (a 3. lépéstől).
6. Folytassuk a jobb részfával (a 3. lépéstől).

Programban:

~/info2/fabeolv.c

#include <stdio.h>
#include <stdlib.h>

struct csucs {
  int ertek;
  struct csucs *bal;
  struct csucs *jobb;
};

/* Beszúrja a gyoker részfába az uj csúcsot levélként (és egyben NULL-t tesz
 * az uj csúcs bal és jobb mutatóiba.
 */
void beszur(struct csucs **gyoker, struct csucs *uj) {
  while (*gyoker != NULL) {
    if (uj->ertek <= (*gyoker)->ertek) {
      gyoker = &(*gyoker)->bal;
    } else {
      gyoker = &(*gyoker)->jobb;
    }
  }
  *gyoker = uj;
  uj->bal = NULL;
  uj->jobb= NULL;
}

void kirajzol(struct csucs *gyoker, int nszokoz) {
  int i;
  for (i=nszokoz; i>0; i--) putchar(' ');
  if (gyoker!=NULL) {
    printf("%d\n", gyoker->ertek);
    kirajzol( gyoker->bal,  nszokoz+2);
    kirajzol( gyoker->jobb, nszokoz+2);
  } else printf("-\n");
}

int main(void) {
  int i, csucsoksz=0;
  struct csucs *gyoker=NULL;
  struct csucs *fa;

  printf("Hány csúcsa lesz a fának? ");
  scanf("%d", &csucsoksz);
  fa = (struct csucs*) malloc(csucsoksz*sizeof(struct csucs));
  if(fa == NULL) {
    printf("Nincs eleg memoria!");
    return 0;
  }
  for(i=0; i<csucsoksz; i++) {
    printf("%d. csúcs értéke? ", i+1);
    scanf("%d",&fa[i].ertek);
    beszur(&gyoker, &fa[i]);
  } 
  kirajzol(gyoker,1);
  return 0;
}