Fastruktúrak. Bejarasi algoritmusok. Halomrendezés. Rendezés rendezőfaval.

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 T₁₀ 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)

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 log₂n) (n=10⁴ 13,29

Megjegyzés: Buborék rendezés: O(n²) (n=10⁴ 10⁸)