Adatszerkezetek 2. 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
3
Bináris fák, példa root
alma
szőlő
korte
barack
szilva
dió
4
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.
5
Példa root
5
Input: 5
6
Példa root
5
Input: 5 3
3
7
Példa root
Input: 5 3 9
5
3
9
8
Példa root
Input: 5 3 9 4
5
9
3
4
9
Példa root
Input: 5 3 9 4 1
5
9
3
1
4
10
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! 11
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 12
Bejárási példa root
5
9
3
1
4
6
Eredmény: 1 13
Bejárási példa root
5
9
3
1
4
6
Eredmény: 1 3 14
Bejárási példa root
5
9
3
1
4
6
Eredmény: 1 3 4 15
Bejárási példa root
5
9
3
1
4
6
Eredmény: 1 3 4 5 16
Bejárási példa root
5
9
3
1
4
6
Eredmény: 1 3 4 5 6 17
Bejárási példa root
5
9
3
1
4
6
Eredmény: 1 3 4 5 6 9 (ZH kérdés)
18
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
19
Egyensúlyozás • Alapművelet a „forgatás”
balra
jobbra
20
Forgatás Max szintek száma: 5
Max szintek száma: 4
(ZH kérdés)
21
Mélységi keresé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: lásd előző bejárási példa Másik módszer: Szélességi keresés 22
Szélességi keresé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
23
Példa szélességi keresésre root
5
Lista: 5 9
3
1
4
6
Eredmény: 24
Példa szélességi keresésre root
5
Lista: 3 9
3
1
4
9
6
Eredmény: 5 25
Példa szélességi keresésre root
5
Lista: 9 9
3
1
1 4
4
6
Eredmény: 5 3 26
Példa szélességi keresésre root
5
Lista: 1 9
3
1
4 6
4
6
Eredmény: 5 3 9 27
Példa szélességi keresésre root
5
Lista: 4 9
3
1
4
6
6
Eredmény: 5 3 9 1 28
Példa szélességi keresésre root
5
Lista: 6 9
3
1
4
6
Eredmény: 5 3 9 1 4 29
Példa szélességi keresésre root
5
Lista: 9
3
1
4
6
Eredmény: 5 3 9 1 4 6 30
Bináris fa Művelet Keresés Beillesztés Törlés Kiválasztás Rendezés
Átlagos eset O(log N) O(log N) O(log N) O(N) O(N)
Legrosszabb eset O(N) O(N) O(N) O(N) O(N)
31
Gráfok • A legelvontabb adattípus, de fontos több szempontból is • Példa: – Vegyük az európai országokat, minden ország egy csomópont – Húzzunk vonalat két ország (csomópont) közé, ha van közös határuk
32
Példa 18
17
19 16 35
15 8
33
14
32
20
13 5
7
4 11
36
21
12 3
10 6
22
37 24
9
23
25 26
31 27 29
1
28
34
2 30
33
Eredmény
9
34
Eredmény
35
Gráf • • • • •
Csomópontok (V) Élek (E) csomópontok + élek = gráf (G) G=(V,E) Gráfok: Objektumok, helyek, emberek, ... közötti valamilyen kapcsolatot írnak le
36
Irányított élek • Élek – Irányítottság nélküli él A
B
A
B
A
B
– Egyirányú él
– Kéirányú él
37
Súlyozott élek • Számot rendelünk az élekhez • Például – Ellenállás – Hossz – Egyéb jellemző
Legrövidebb út A-ból D-be? A
2
B
5
3 C
2 D
3
• Csomópontok is lehetnek súlyozottak 38
Gráfok ábrázolása 1
Szomszédsági lista A ponttal szomszédos pontokat tároljuk egy listában
2 3
5
4 Pontok 1 listája 2 3 4
2
5
1
3
2
4
2
3
5
5
1
2
4
4
5
39
Gráfok ábrázolása 1
Szomszédsági mátrix (csúcsmátrix)
2
⎧1, ha (i, j) ∈ E aij = ⎨ ⎩0, külkönben
3 5
4 1
Irányítatlan gráf esetén:
2
AT = A
3 4 5
1
2
3
4
5
0 1 0 0 1
1 0 1 1 1
0 1 0 1 0
0 1 1 0 1
1 1 0 1 0
40
Teljes gráf • Minden csomópont minden csomóponttal össze van kötve
41
Izomorf • G1 és G2 gráf izomorf, ha van közöttük egy-egy értelmű megfeleltetés. A B
E B
H
C
G D
F E
H
G
C D
F A 42
Utak és körök • A G=(V,E) gráfban az u csúcsot az u’ csúccsal összekötő út, amely a csomópontok véges sorozata, [u0, u1, ..., un], ahol u0 = u és un = u’ és (ui-1,ui) eleme E-nek. • Az út hossza az élek száma • Az út egy kör, ha az [u0, u1, ..., un] utban u0 = un
43
Euler féle gráf • Minden élen úgy végig lehet menni, hogy minden élen csak egyszer megyünk át
44
Gráf éleinek összege • N csomópontú gráf • Egy csúcsba befutó élek száma: fokszám (T) P1
P2
P1,
P2,
T(P1), T(P2),
…
Pn
…
T(Pn)
P3
Pn
1 E= 2
n
∑ ρ (P ) i
i =1
45
Königsbergi hidak problémája
Be lehet-e járni a várost úgy, hogy minden hídon csak egyszer megyünk át? 46
Königsbergi hidak problémája C A csúcsok nem páros fokúak.
D
A
„Tétel”: ha páros fokúak a csúcsok, akkor körül lehet járni és Euler gráf
B
47
Hamilton kör • Egy irányítatlan gráfban olyan „kör” mely a gráf minden pontján pontosan egyszer megy végig.
Dodekaéder gráf reprezentációja
48
Utazó ügynök probléma • Travelling salesman problem (TSP) • Egy ügynöknek n várost kell meglátogatnia tetszőleges sorrendben, de minnél kisebb utazási költség mellett. – Adott egy n csúcsú teljes gráf, melynek éle súlyozottak – A feladat olyan Hamilton-kör megtalálása, melynke összköltsége minimális (az élekhez rendelt számok összege)
49
Fák • A fa olyan gráf, amiben nincs kör • „Tétel”: ha n csúcsa van egy fának akkor n-1 éle
50
Laplace mátrix ρ (vi ) ha i = j ⎧ ⎪ aij = ⎨- 1 ha i ≠ j és vi és v j szomszédosak ⎪ 0 egyébként ⎩ 1
1
2
2 3 5
4
3 4 5
1
2
3
4
5
2 -1 0 0 -1
-1 4 -1 -1 -1
0 -1 2 -1 0
0 1 -1 3 -1
-1 -1 0 -1 3 51
Fiedler vektor • A Laplace mátrix második legkisebb saját vektora • Megadja hogyan kell a gráfot elvágni úgy, hogy – A lehető legkevesebb élet vágjuk el – A csomópontok száma a két al-gráfban egyenlő legyen
52
Gráfok, duális gráfok
53
Voronoi diagram • Egy pont halmaz közelségi diagramja • Felosztja a teret úgy, hogy a tartomány minden pontja közelebb van a tartomány pontjához mint bármelyik másik ponthoz 54
Delaunay háromszögelés • A Voronoi diagram duálisa egy háromszögelés • Matematikailag definiálható – A háromszögelés egyedi – A háromszögek köré írt kör üres!!!! – Maximalizálja a háromszögek minimális szögét – Kiterjeszthető n dimenzióba
• Felhasználása széleskörű
55
Felszín modellezés • 11,000,000 magassági mérés kombinálásából 130,000 pont és 260,000 háromszögből készített model
56
Véges elemes analízis
57
Delaunay háromszögelés
58
Eredmény
59
