1 of 85

Adatszerkezetek�2022.10.18

2 of 85

Ismétlés

3 of 85

Keresőfák

Fa: összefüggő, körmentes gráf, melyre igaz, hogy:

- (Általában) egy gyökér csúcsa van, melynek 0 vagy több részfája van

- Pontosan egy út vezet bármely két csúcsa között

- A gyökéren kívül minden csúcsnak pontosan egy szülője van

​

4 of 85

Bináris kereső fa felépítése

  • Minden root elemnél kisebb balra, még a nagyobb elem jobbra helyezkedik el
  • A bináris fánk ágai további „kicsi” bináris fára bonthatók
  • Ezt addig tesszük még a levelekhez nem érünk

5 of 85

Bináris kereső fa felbejárása

https://visualgo.net/en/bst

6 of 85

Elem törlése a BST-ből

  • Adott egy binársi fánk, hogyan törölnénk belőlle egy elemet?
  • Hogyan törlnénk belőlle a 29-es elemet?
  • Könnyű ezt megtennünk egy “levéllel”, de mi történik ha a fa közepéből törlök?

​

​

​

7 of 85

Törlés a fából

​

  • Egy megoldás, hogy megkeressük a jobboldali részfa legkisebb vagy a baloldali részfa legnagyobb elemét és annak értékével helyettesítjük a törlendő elemet.
  • Vagyis az inorder bejárás szerint előtte vagy utána lévő elemet.

8 of 85

Hasító táblázatok

9 of 85

Hasító táblázatok

  • Keressük meg a 8-as számot egy tömben

​

​

10 of 85

Hasító táblázatok

  • Lineáris keresés nagyon időigényes
  • Bináris keresés log n , viszont időt vesztünk a tömb rendezésével (első lépésben rendezni kell)

​

​

11 of 85

Hasító táblázatok

  • Azt szeretnénk elérni, hogy a keresés időigénye O(1), konstans legyen
  • Hogy ezt elérjük különböző technikákat dolgoztak ki

​

​

12 of 85

Hasító táblázatok

  • Itt jön a képbe a Hasító táblázat technika…..

​

​

13 of 85

Hasító táblázatok

  • Amennyiben adott egy lista az értékekről és egy tömb a tárolásra
  • Ebben az esetben az értékeket az indexeik alapján tároljuk

​

​

14 of 85

Hasító táblázatok

  • Amennyiben adott egy lista az értékekről és egy tömb a tárolásra
  • Ebben az esetben az értékeket az indexeik alapján tároljuk

​

​

15 of 85

Hasító táblázatok

  • Az így eltárolt adatokat könnyen megtalálhatjuk a tömbünkben
  • Amennyiben a kulcs benne van a táblában, akkor visszakapjuk annak értékét, egyébként NIL
  • Az elemek elérése(keresése) O(1)

​

​

16 of 85

Hasító táblázatok

  • Azonban akad egy probléma….
  • Mi van akkor ha, egy új elem értéke nagyobb a tömb méreténél?

​

​

17 of 85

Hasító táblázatok

  • Ha megnövelem a tömböt akkor sok felesleges helyet hagyok ki.

​

​

?

18 of 85

Hasító táblázatok

  • Hogy ezt megoldjuk, HASH függvények gondolatát vezettük be

​

​

?

19 of 85

Hasító táblázatok

  • Nézzünk egy példát a Hash függvények alkalmazására

​

​

Tárolandó elemek

Tárolási hely

20 of 85

Hasító táblázatok

  • Egy nagyon primitív megoldásban a már előzőekben megismert függvény is alkalmazható lenne

​

​

Tárolandó elemek

Tárolási hely

21 of 85

Hasító táblázatok

  • Viszont ha egy új 50-es értéket adunk a halmazunknak, akkor azzal nem tudunk mit kezdeni

​

​

Tárolandó elemek

Tárolási hely

22 of 85

Hasító táblázatok

  • Mielőtt továbbmennénk, le kell tisztáznunk, hogy van ONE-ONE és MANY-ONE típusú függvény

​

​

Tárolandó elemek

One-One

H(x) = x

23 of 85

Hasító táblázatok

  • Ahhoz, hogy megoldjuk a problémát, át kell írnunk a módosító függvényt valami jobb megoldásra

Tárolandó elemek

Tárolási hely

24 of 85

Hasító táblázatok

  • A megoldás:

Hash tábla mérete

25 of 85

Hasító táblázatok

  • Teszteljük a megoldást
  • Egy pár számig jól működik az elgondolás

26 of 85

Hasító táblázatok

  • Azonban előbb, vagy utóbb ütközés áll fent

Many-One

H(x) = x%size

27 of 85

Hasító függvények

• A hash táblák alapja a „megfelelően” megválasztott hash függvény.

​

- Irodalom tartalmaz jót és rosszat is

- Nincs univerzális megegyezés arról mi tekinthető jónak

- Rosszul választott függvény kulcs ütközéshez

(collision) vezet

​

28 of 85

Hasító függvények

• Kulcsok csoportosulása (clustering): Ebben az esetben annak a valószínűsége hogy több kulcs ugyanazt az indexet adja meg jóval nagyobb mintha egy véletlen szám generátor függvényt használtunk volna.

29 of 85

Hasító függvények

Függvény minősége:

​

  • Egyszerűség (forrás kódban a sorok száma)
  • Sebesség (időmérés, benchmark)
  • „Erő” mérése:
    • Statisztikai tesztek melyek megállapítják, hogy a hash függvény mennyiben különbözik a véletlen szám generáló függvénytől
    • Talán a legfontosabb mérési módszer a hash függvény jóságának a mérésére, hogy a függvényre jellemző-e az

„Avalanche” effektus

30 of 85

Hasító táblázatok

Ütközésfeloldásra a következő megoldásokat használjuk:

  • Zárt hashing
    • Láncolás (chaining)
  • Nyílt hashing
    • Lineáris kipróbálás (linear probing)
    • négyzetes kipróbálás (quadritic probing)
    • Dupla hasítás (double hashing)

31 of 85

Hasító táblázatok

Ütközésfeloldásra a következő megoldásokat használjuk:

  • Zárt hashing
    • Láncolás (chaining)
  • Nyílt hashing
    • Lineáris kipróbálás (linear probinh)
    • négyzetes kipróbálás (quadritic probing)
    • Dupla hasítás (double hashing)

32 of 85

Hasító táblázatok

Ütközésfeloldásra a következő megoldásokat használjuk:

  • Zárt hashing
    • Láncolás (chaining)
  • Nyílt hashing
    • Lineáris kipróbálás (linear probinh)
    • négyzetes kipróbálás (quadritic probing)
    • Dupla hasítás (double hashing)

Ha a kitöltési tényező kb. 0.7-re növekszik, mindegyik módszer meglassul.

33 of 85

Láncolás (chaining)

34 of 85

Láncolás (chaining)

  • Ennél a megoldásnál kulcsok létrehozásánál ugyan azt a függvényt használjuk.
  • A megoldáshoz azonban láncolt listákat használunk fel.

​

35 of 85

Láncolás (chaining)

  • Igazából nem az értéket rakjuk a tömbbe hanem a láncolt lista (első) elemét

​

36 of 85

Láncolás (chaining)

  • Ez a megoldás áthidalja az ütközés problémáját

​

37 of 85

Láncolás (chaining)

  • Ez a megoldás áthidalja az ütközés problémáját

​

38 of 85

Láncolás (chaining)

  • Ez a megoldás áthidalja az ütközés problémáját

​

39 of 85

Láncolás (chaining)

  • Ha megakarok keresni egy értéket a HASH táblámban. Pl. key = 13, akkor ehhez használnom kell a hasító függvényt ( h(x) = x%size

40 of 85

Láncolás (chaining)

  • Ebben az esetben a 3. elem láncában kell keresni az elemet
  • Ez a megoldás nem O(1) , de jobb mint O(log n)

41 of 85

Lineáris kipróbálás

42 of 85

Lineáris kipróbálás

  • Ebben a megoldásban az ütközés esetén a következő szabad helyen próbáljuk meg eltárolni az elemünket

43 of 85

Lineáris kipróbálás

  • Ebben a megoldásban az ütközés esetén a következő szabad helyen próbáljuk meg eltárolni az elemünket

44 of 85

Lineáris kipróbálás

  • Nézzünk meg a képletet a key=13-ra

ÜTKÖZÉS

45 of 85

Lineáris kipróbálás

  • Nézzünk meg a képletet a key=13-ra

46 of 85

Lineáris kipróbálás

  • Nézzünk meg a képletet keresésre
  • Ismét visszavezettük arra az állapotra amikor az első vagy az őt követő helyen van az érték

47 of 85

Lineáris kipróbálás

  • Ha egy olyan számot keresünk ami nincs a táblában, az a következők szerint fog kinézni:
  • Keressük meg pl. a key=24-et

48 of 85

Lineáris kipróbálás

  • Ha egy olyan számot keresünk ami nincs a táblában, az a következők szerint fog kinézni:
  • Keressük meg pl. a key=24-et

Elértünk egy üres helyig, tehát nincs a táblában

49 of 85

Lineáris kipróbálás

  • Ennek a megoldásnak azonban az a baja, hogy egyhelyre pakolja az elemeket
  • E problémára nyújt megoldást a négyzetes kipróbálás

Clustering problem

50 of 85

Lineáris kipróbálás

Működés feltételei:

  • A lépésköz általában 1, bár lehet mást is használni
  • Működés feltételei:
    • A hash tábla mérete vagy prím szám legyen vagy a kettő hatványa
    • Ha a tábla mérete kettő hatványa akkor a lépésköz csak páratlan lehet

51 of 85

Négyzetes kipróbálás

52 of 85

Négyzetes kipróbálás

  • Az alap elgondolás megegyezik a lineáris kipróbálás műveletével, de az f(i)=i helyett f(i)= i2 -el számolunk

​

53 of 85

Négyzetes kipróbálás

  • Nézzük meg a használatát

​

54 of 85

Négyzetes kipróbálás

  • Nézzük meg a használatát

​

ÜTKÖZÉS

ÜTKÖZÉS

55 of 85

Négyzetes kipróbálás

  • Nem jön létre csoportosulás
  • Csak akkor garantált a működés ha:
    • A tábla maximum félig telik meg (félig üres)
    • A tábla mérete prím szám

56 of 85

Dupla hasítás

57 of 85

Dupla hasítás

  • A dupla hasítás elképzelése szerint nem egyszer, hanem kétszer hasítjuk a táblát

​

h(k, j) = (h'(k) + jh''(k)) mod m,

​

ahol h' és h'' kisegítő hasítófüggvények (dupla hasítás).

58 of 85

Dupla hasítás

  • Nézzük meg a használatát

​

59 of 85

Dupla hasítás

  • Nézzük meg a használatát

​

60 of 85

Dupla hasítás

  • Nézzük meg a használatát

​

61 of 85

Dupla hasítás

  • Key = 18 -> 5+ 0*3=5

​

h(k, j) = (h'(k) + jh''(k)) mod m,

​

62 of 85

Dupla hasítás

  • Key = 41 -> 2+ 0*1=2

​

h(k, j) = (h'(k) + jh''(k)) mod m,

​

63 of 85

Dupla hasítás

  • Key = 22 -> 9+ 0*6=9

​

h(k, j) = (h'(k) + jh''(k)) mod m,

​

64 of 85

Dupla hasítás

  • Key = 44 -> 5+ 0*5=5

​

ÜTKÖZÉS

h(k, j) = (h'(k) + jh''(k)) mod m,

​

65 of 85

Dupla hasítás

  • Key = 44 -> 5+ 1*5=10

​

h(k, j) = (h'(k) + jh''(k)) mod m,

​

66 of 85

Dupla hasítás

  • Működés feltételei:
    • h2 soha nem lehet nulla, mert végtelen ciklust kapnánk
    • A hash tábla mérete vagy prím szám legyen vagy kettő hatványa
    • Ha a tábla mérete kettő hatványa akkor a lépésköz csak páratlan lehet

67 of 85

Lineáris próba, törlés

68 of 85

Lineáris próba, törlés

  • A törlés problematikusabb
    • Ha valóban törlünk hibás működést kapnánk
    • Ha csak törlünk egy elemet, akkor a következő beillesztésnél a lináris próba idő előtt leállhat

69 of 85

Lineáris próba, törlés

A nyílt címzéses hasító táblázatokból való törlés kissé nehezebb.

Amikor töröljük az i-edik résben lévő kulcsot, nem elegendő a nil beírásával jelezni annak ürességét

70 of 85

Lineáris próba, törlés

Ha csak ezt tennénk, akkor lehetetlen lenne minden olyan kulcs visszakeresése, melynek beszúrása során az i-edik rést kipróbáltuk és foglaltnak találtuk.

Egy lehetséges megoldás az, hogy a töröltség jelölésére a nil helyett egy másik speciális értéket, a törölt-et használjuk.

71 of 85

Lineáris próba, törlés

  • A törlés

72 of 85

Feladatok

Adott egy nyílt címzéses, m = 11 hosszúságú (üres) hasító táblázat a h (k) = k mod m elsődleges hasító függvénnyel, s tekintsük a beszúrandó 10, 22, 31, 4, 15, 28, 17, 88, 59 kulcsokat.

Szemléltessük a beszúrás eredményét akkor, ha a lineáris kipróbálást, a c1 = 1 és c2 = 3 állandókat használó négyzetes kipróbálást, illetve a h2(k) = 1 + (k mod (m − 1)) másodlagos hasító függvényű dupla hasítási módszert alkalmazzuk.

73 of 85

Feladatok

74 of 85

Feladatok

75 of 85

76 of 85

Feladatok

77 of 85

Feladatok

78 of 85

Feladatok

79 of 85

Feladatok

„Csomósodás”

80 of 85

Feladatok

81 of 85

Feladatok

82 of 85

Feladatok

83 of 85

Feladatok

84 of 85

Feladatok

85 of 85

Olvasni /nézni való

​