Info2/2008tavasz/kuka
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'')). | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
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 | + | 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 | + | 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., 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:
- A gyökértől indulunk.
- Ha az aktuális csúcsban a kívánt érték szerepel, készen vagyunk.
- 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).
- 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).
- 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:
- A gyökértől, pontosabban a gyökér kezdőcímétől indulunk.
- 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.)
- 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.
- 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.)
- 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).
- 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; }