Info2/2008tavasz/kuka

A MathWikiből
(Változatok közti eltérés)
98. sor: 98. sor:
  
 
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'')).
 
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'')).
 
C nyelvben a bináris fák kezeléséhez struktúrákat használunk. A kapcsolódó fogalmak:
 
 
* struktúra (struct)
 
* mező
 
* struktúra mérete
 
* mező kezdőcíme a struktúrában
 
* bájtra igazítás (alignment)
 
 
PC (i386, x86) architektúrán az igazítások:
 
 
* char esetén 1
 
* short esetén 2
 
* double esetén 8
 
* minden más (pl. int, long, float, struktúra és mutató) esetben 4
 
 
Példa struktúra definiálására:
 
 
struct pelda {
 
  int a, b;
 
  char c;
 
  double d;
 
};
 
 
A példa struktúra mérete igazítás nélkül 4+4+1+8 bájt lenne, igazítással viszont 4+4+1+3+8 bájt, mivel a double típusú változónak 4-gyel osztható címen kell kezdődnie, így 4+4+1 helyett a 4+4+1+3 címen kezdődik.
 
 
Példa struktúra használatára:
 
 
struct pelda egyik, masik;
 
egyik.a=5; egyik.b=6; egyik.c='x', egyik.d=egyik.a/2.0;
 
masik=egyik; /* minden mezőt lemásol */
 
masik.a=egyik.b; masik.b=egyik.a;
 
 
Vettük még előadáson a mutató (pointer) fogalmát. A mutató egy adott típusú érték kezdőcímét tartalmazza. Mutató deklarálásához a változónév elé tegyünk egy csillagot:
 
 
* <code>int p;</code>: a p változó egy int értéket tartalmaz
 
* <code>int *p;</code>: a p változó egy int értékre mutató mutatót tartalmaz
 
* <code>int **p;</code>: a p változó egy int értékre mutató mutatóra mutató mutatót tartalmaz
 
* <code>char **argv;</code>: az argv változó egy char értékre mutató mutatóra mutató mutatót tartalmaz
 
* <code>struct pelda *oda;</code>: az oda változó egy pelda típusnevű struktúrára mutató mutatót tartalmaz
 
 
Egy adott változó kezdőcíméhez a változónév elé tegyünk egy <code>&</code> jelet (ésjelet):
 
 
* <code>int a, *p; p=&a;</code>: a p mutató az a (int típusú) változó kezdőcímét tartalmazza
 
* <code>int t[5], *p; p=&t[3];</code>: a p mutató a t (int típusú elemekből álló) tömb 3-adik elemédik kezdőcímét tartalmazza
 
* <code>struct pelda egyik; int *p; p=&egyik.b;</code>; a p mutató az ''egyik'' (pelda típusnevű) struktúra ''b'' mezőjének kezdőcímét tartalmazza
 
 
A fordított művelethez, tehát egy mutató által mutatott memóriaterület értékéhez a mutató elé tegyünk csillagot:
 
 
* <code>int a=5, *p; *p=&a; a=20; *p+=22; printf("%d", *p);</code>: az a-t először 5-ről 20-ra változtatja, majd megnöveli 22-vel, majd kiírja (a 42-t)
 
* <code>struct pelda egyik; char *p=&egyik.c; *p=5;</code>: az ''egyik'' (pelda típusnevű) struktúra ''c'' mezőjének értékét 5-re változtatja
 
 
Speciális mutató a NULL (<code>#include <stdlib.h></code> kell neki), ami nem mutat érvényes memóriaterületre. Példa használatára:
 
 
* <code>int a, *p=NULL; a=*p;</code>: a második értékadás ''Segmentation fault''-ot (Szegmens hiba) okoz, a program futása megszakad. Megjegyzés: ''Segmentation fault'' más programokban máshogy is előállhat.
 
 
Vegyük észre, hogy a függvényeknél megtanult cím szerinti paraméterátadásnál mutató átadása történik (pl. a törtösszeadós példában <code>egyszerusit(&as,&es);</code>), és a függvényen belül a kód csak a mutatót követi (pl. <code>*s/=c;</code>).
 
  
 
A bináris fa egy csúcsát struktúraként definiáljuk:
 
A bináris fa egy csúcsát struktúraként definiáljuk:
164. sor: 107. sor:
 
  };
 
  };
  
Példa a fenti bináris fa azon részfájának létrehozására, ami a 3-ból indul lefele (~/szimp2/fapelda1.p):
+
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 */
 
  #include <stdlib.h> /* a NULL miatt */
183. sor: 126. sor:
 
Célunk, hogy meg tudjuk írni a bináris keresőfába való beszúrás algoritmusát.
 
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 (rekurzív) algoritmusa:
+
A bináris keresőfába való beszúrás algoritmusa:
  
 
# A gyökértől, pontosabban a gyökér kezdőcímétől indulunk.
 
# A gyökértől, pontosabban a gyökér kezdőcímétől indulunk.

A lap 2008. március 21., 00: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;
}
Személyes eszközök