Adatszerkezetek 7a. Dr. Iványi Péter
1
Fák • Fákat akkor használunk, ha az adatok között valamilyen alá- és fölérendeltség van. – Pl. könyvtárszerkezet gyökér (root)
Nincsennek hurkok!!!
2
Bináris fák • Azokat a fákat, amelyekben egy elemből csak két másik elembe mutat nyíl bináris fáknak nevezzük. • A bináris fa – Vagy üres fa – Vagy egy olyan fa amelynek a bal és jobb oldali mutatója egy-egy bináris fára mutat
• Ez egy rekurzív definíció
3
Bináris fák Rekord { adat bal jobb } Elem
4
Bináris fák, példa root
alma
szőlő
korte
barack
szilva
dió
5
Bináris kereső fa építése • Helyezzük el az első elemet. • Ha a következő elem kisebb, mint az előző akkor a gyökérelemtől balra helyezzük el, ha nagyobb akkor jobbra. • A bevitt elemeket bejárva, ha a csomópontnál kisebb akkor balra menjünk, egyébként jobbra.
6
Példa root
5
Input: 5
7
Példa root
5
Input: 5 3
3
8
Példa root
Input: 5 3 9
5
3
9
9
Példa root
Input: 5 3 9 4
5
9
3
4
10
Példa root
Input: 5 3 9 4 1
5
9
3
1
4
11
Példa root
Input: 5 3 9 4 1 6
5
9
3
• 3 szint 1
4
6
• Legnagyobb elem 2 lépésben található meg
Ha más sorrendben visszük be az elemeket más fát kapunk! 12
Példa root
Input: 1 3 4 5 6 9
1 3 4 5
6
• 6 szint
9
• Legnagyobb elem 6 lépésben található meg 13
Mélységi bejárás fákban 1. 2. 3. 4.
A gyökér csúcsból indulunk Addig megyünk lefelé amíg lehetséges Ekkor visszalépünk egyet Ha most nem a gyökérben állunk akkor visszaugrunk a 2. Lépésre
BACKTRACK technika (visszalépés) Másik módszer: Szélességi bejárás 14
Mélységi bejárás fákban Rekurzív függvénnyel a „legszebb” a megfogalmazás Függvény keres(bt) if bt == NIL return keres(bt->bal) nyomtat(adat) keres(bt->jobb) Függvény vége 15
Bejárási példa root
5
9
3
1
4
6
Eredmény: 1 16
Bejárási példa root
5
9
3
1
4
6
Eredmény: 1 3 17
Bejárási példa root
5
9
3
1
4
6
Eredmény: 1 3 4 18
Bejárási példa root
5
9
3
1
4
6
Eredmény: 1 3 4 5 19
Bejárási példa root
5
9
3
1
4
6
Eredmény: 1 3 4 5 6 20
Bejárási példa root
5
9
3
1
4
6
Eredmény: 1 3 4 5 6 9 (ZH kérdés)
21
Függvény 1. Függvény preorder(bt) if bt == NIL return /* csinálunk valamit */ preorder(bt->bal) preorder(bt->jobb) Függvény vége
22
Függvény 2. Függvény inorder(bt) if bt == NIL return inorder(bt->bal) /* csinálunk valamit */ inorder(bt->jobb) Függvény vége
23
Függvény 3. Függvény postorder(bt) if bt == NIL return postorder(bt->bal) postorder(bt->jobb) /* csinálunk valamit */ Függvény vége
24
Példa root
A G
B
C
D
E
F
Preorder: Inorder: Postorder:
A B C D E F G C B E D F A G C E F D B G A 25
Matematikai kifejezéseknél root
/ G
*
C
Postorder: C E F + * G / Preorder: / * C + E F G Inorder: ((C * (E + F)) / G)
+
E
F
26
Threaded Binary Tree root
A G
B
C
D
E
F
27
Threaded Binary Tree • Jobb mutató: a „sorrendben” (inorder) következő elemre mutat • Bal mutató: a „sorrendben” (inorder) előző, „felsőbb” elemre mutat • Gyorsabb, lineáris bejárást tesz lehetővé, nincs szükség rekurzióra • Olyan esetben ha limitált a verem (stack) terület
28
Threaded Binary Tree 1. root
A G
B
C
Jobb mutató: a „sorrendben” következő elemre mutat (inorder)
D
E
F
C
29
Threaded Binary Tree 2. root
A G
B
C
D
E
F
CB
30
Threaded Binary Tree 3. root
A G
B
C
D
E
F
CBE
31
Threaded Binary Tree 4. root
A G
B
C
D
E
F
CBED
32
Threaded Binary Tree 5. root
A G
B
C
D
E
F
CBEDF
33
Threaded Binary Tree 6. root
A G
B
C
D
E
F
CBEDFA
34
Threaded Binary Tree 7. root
A G
B
C
D
E
F
CBEDFAG
35
Bináris kereső fa • A bináris kereső fákba gyorsan lehet adatot beilleszteni és adatot keresni • Általában egy adat keresését egy N csomópontú fában log(N) idő alatt lehet végrehajtani • Mivel különböző sorrendű adatok esetén különböző fát kapunk, rosszabb esetben lassabb az algoritmus (rosszul egyensúlyozott bináris fák) • Egyensúlyozott fát kell létrehozni
36
Egyensúlyozás • Alapművelet a „forgatás”
balra
jobbra
37
Forgatás Max szintek száma: 6
Max szintek száma: 5
(ZH kérdés)
38
Szélességi bejárás • Fákban vagy gráfokban – Egy tetszőleges csomópontból indulunk – Minden lépésben a feldolgozandó csúcsokhoz hozzáadjuk a legutóbbi lépésben elért csúcsokat
39
Példa szélességi bejárásra root
5
Lista: 5 9
3
1
4
6
Eredmény: 40
Példa szélességi bejárásra root
5
Lista: 3 9
3
1
4
9
6
Eredmény: 5 41
Példa szélességi bejárásra root
5
Lista: 9 9
3
1
1 4
4
6
Eredmény: 5 3 42
Példa szélességi bejárásra root
5
Lista: 1 9
3
1
4 6
4
6
Eredmény: 5 3 9 43
Példa szélességi bejárásra root
5
Lista: 4 9
3
1
4
6
6
Eredmény: 5 3 9 1 44
Példa szélességi bejárásra root
5
Lista: 6 9
3
1
4
6
Eredmény: 5 3 9 1 4 45
Példa szélességi bejárásra root
5
Lista: 9
3
1
4
6
Eredmény: 5 3 9 1 4 6 46
Keresés, rekurzív Függvény keres(bt, k) if bt == NIL vagy bt->adat == k return bt if vége if k < bt->adat return keres(bt->bal, k) else return keres(bt->jobb, k) if vége Függvény vége
O(h) : ahol h a fa magassága 47
Keresés, iteratív Függvény keres(bt, k) while bt != NIL és k != bt->adat if k < bt->adat bt = bt->bal else bt = bt->jobb if vége while vége Függvény vége 48
Minimum keresés Függvény min_faban(bt, k) while bt->bal != NIL bt = bt->bal while vége return bt->adat Függvény vége
O(h) : ahol h a fa magassága 49
Bináris fa Művelet Keresés Beillesztés Törlés Rendezés
Átlagos eset O(log N) O(log N) O(log N) O(N)
Legrosszabb eset O(N) O(N) O(N) O(N)
50
Piros-fekete fák • „Önegyensúlyozó” bináris kereső fa • Rudolf Bayer 1972-ben • Hatékony, O(log N)
51
