|  | ||||||||
|  | ||||||||
| | ||||||||
| | ||||||||
 |
kategória |  |
||||||||
|
|
||||||||||
 |
 |
|
|
|
|
|
||
|
|
Fastruktúrák. Bejárási algoritmusok. Halomrendezés. Rendezés rendezőfával.
A fa adatszerkezet
Bináris fa: minden csomópontnak 0,1 vagy 2 rákövetkezője (gyereke) lehet.
Példa
A gyökér(szülő) 0. szint
Bal oldali gyerek B
C Jobb oldali gyerek 1. szint
D E F G ág 2. szint
H J K levél 3. szint
Bal oldali részfa Jobb oldali részfa A fa mélysége: 4
Példa Kétoperandusos műveleteket tartalmazó algebrai kifejezés: E=(a-b)/((c*d)+e)
/
- +
a
b * e
c d
Teljes bináris fa: az utolsó szintet kivéve minden szinten a csomópontok száma maximális, az utolsó szinten baloldalról helyezkednek el a csomópontok.
Példa 1
2 3
4 5 6 7
8 9 10 T10 teljes fa
Megjegyzés: K csomópont bal rákövetkezője: 2*K
K csomópont jobb rákövetkezője: 2*K+1
K csomópont szülője: K/2
Kiterjesztett bináris fa (kettes fa): minden csomópontnak 0 vagy 2 gyereke van.
2 gyerekes csomópont: belső csomópont (O)
0 gyerekes csomópont: külső csomópont (
Példa
O O
O O O O
O O O O
O O
2. példa Kétoperandusos műveletek szemléltetése:
operandus: külső csomópont
operátor: belső csomópont
Bináris fák megvalósítása
1. módszer: láncolt listákkal
gyökérmutató
jobbmutató
balmutató A
B C
Æ D Æ E Æ G Æ H Æ
Æ F Æ Æ J Æ Æ K Æ
2. módszer: vektorban (szekvenciális ábrázolás)
|
A |
B |
C |
D |
E |
G |
H |
Æ |
Æ |
F |
Æ |
Æ |
Æ |
J |
K |
Megjegyzés: Szekvenciális ábrázolás hatékony, ha a fa teljes vagy csaknem teljes.
Bináris fák bejárása
I. Preorder bejárás (R gyökerű fáé)
1. gyökér feldolgozása
2. R bal oldali részfájának preorder bejárása
3. R jobb oldali részfájának preorder bejárása
A
B C Preorder
bejárás:
D E G H ABDEFCGHJK
F J K
II. Inorder bejárás
1. R bal oldali részfájának inorder bejárása
2. R gyökér feldolgozása
3. R jobb oldali részfájának inorder bejárása
Példa A fenti ábra inorder bejárása: DBFEAGCJHK
III. Posztorder bejárás
1. R bal oldali részfájának posztorder bejárása
2. R jobb oldali részfájának posztorder bejárása
3. R gyökér feldolgozása
Példa A fenti ábra posztorder bejárása: DFEBGJKHCA
E=(a-b)/((c*d)+e
/
Preorder bejárás: - + Posztorder
bejárás:
/-ab+*cde prefix jelölés a
b * e ab-cd*e+/ posztfix jelölés
c d
Preorder bejárás megvalósítása verem segítségével:
MUT: a feldolgozandó csomópontra mutat
VEREM: még feldolgozandó jobb csomópontokat tárolja
A 1. 2.
3.
B C C
C
D E F Æ Æ Æ
G H Mut: A Mut:B Mut: D
K
4. 5. 6. 7. 8.
H K
C C C C
Æ Æ Æ Æ Æ
Mut:
G Mut: H Mut: Mut: K Mut:
C
9. 10. 11.
F
Æ Æ
Mut: E Mut: F Mut: Æ eljárás vége
Halom, halomrendezés
Halom(piramis): Olyan teljes bináris fa, melynek minden csomópontjára igaz, hogy a csomópont értéke nagyobb, mint a csomópont gyermekeinek értéke.
Példa Piramis
88 95
66 55 95 48
66 35 48 55 62 77 25 38
18 40 30 28 24
Megjegyzés: Szekvenciálisan tároljuk.
Beszúrás halomba
1.lépés: Új elemet a halom végéhez csatoljuk,
hogy a teljes fa szerkezet megmaradjon
(halom nem feltétlenül).
2.lépés: Visszaállítjuk a halom szerkezetet.
Példa Az előbbi halomba beszúrjuk a 70-es elemet.
97 97 97 1. - halom végére tétel
88 88 2., 3.-
beemelés a halom
55 55 70 megfelelő
helyére
70 55
70 48 48
Megjegyzés: Sorozatból halmot építeni beszúrások sorozatával.
Példa 44,30,50,22,60
1. 2. 3. 4. 5. 6. 7. 8.
44 44 44 50 50 50 50 60
30 30 50 30 44 30 44
30 44 60 44 50 44
22 22 60 22 30 22 30
Halom gyökerének törlése
1. lépés: R gyökeret töröljük (értékül adjuk egy változónak)
2. lépés: gyökér helyére tesszük
az utolsó elemet
(megmarad a teljes fa
szerkezet, halom nem feltétlenül)
3. lépés: az új gyökeret a megfelelő helyre illesztjük a fában
Példa 95 15
85 70 85 70
55 33 30 65 55 33 30 65
15
1., 2.
85 85
15 70 55 70
55 33 30 65 15 33 30 65
3., 4.,
Halomrendezés
Rendezzük A tömb elemeit!
1. lépés: H halom felépítése A elemeiből.
2. lépés: H gyökerének ismételt törlése. (Más vektorba, vagy A vektor végére)
Műveleti igény: O(n log2n) (n=104 13,29
Megjegyzés: Buborék rendezés: O(n2) (n=104 108)
:
1879
