1 of 97

Keresőfák�2022.10.25

2 of 97

Ismétlés

3 of 97

Az adatszerkezetek

​

​

Az adatszerkezet adatok tárolására és szervezésére szolgáló módszer (konstrukció), amely lehetővé teszi a(z adatokhoz való) hatékony hozzáférést és (a) módosításokat.

​

Tanult absztrakt adatszerkezetek:

  • Lista
  • Verem
  • Sor
  • Prioritás sor
  • Kupac

4 of 97

Láncolt listák

​

​

Minden elem egy adatból és egy (vagy több) mutatóból áll.

A mérete futás során módosítható.

5 of 97

Verem

​

​

  • A verem egy LIFO (last in, first out) adatszerkezet
  • Két műveletet támogat:
    • push: egy elemet hozzáadunk az eddigiekhez úgy, hogy a verem tetejére tesszük
    • pop: az utoljára beszúrt elemet veszi ki a veremből (a tetejéről)

6 of 97

Sor

​

​

A sor egy FIFO (first in, first out) adatszerkezet.

Két műveletet támogat:

  • enqueue: egy új elemet adunk hozzá úgy, hogy a sor végére szúrjuk be
  • dequeue: az első elemet töröljük a sorból

7 of 97

Prioritási sor

​

​

Absztrakt adatszerkezet, melyben az elemeket prioritásuk szerint tároljuk

​

Három műveletet támogat:

  • insert: beszúr egy elemet
  • pop: kiveszi a legkisebb prioritású elemet
  • min: a legkisebb prioritású elemet adja vissza (pl. int-ek esetén minimumot)

​

8 of 97

Feladat

​

​

A kupac (heap) egy hatékony megvalósítása a prioritási sor absztrakt adatszerkezetnek.

​

A kupac egy bináris fa, amelynek minden csúcsa legalább akkora, mint gyerekei → maximális elem a gyökérben van

​

​

​

9 of 97

Kupac

Beszúrás

​

13

10 of 97

Kupac

Beszúrás

​

13

11 of 97

Kupac

Beszúrás

​

43

12 of 97

Kupac

Beszúrás

​

43

13 of 97

Kupac

Beszúrás

​

31

43

14 of 97

Kupac

Beszúrás

​

31

42

43

15 of 97

Kupac

Törlés

​

44

16 of 97

Kupac

Törlés

​

44

44

14

17 of 97

Kupac

Törlés

​

44

44

14

18 of 97

Kupac

Törlés

​

44

14

?

?

19 of 97

Kupac

Törlés

​

44

42

14

20 of 97

Kupac

Törlés

​

44

42

?

?

14

21 of 97

Kupac

Törlés

​

44

42

33

14

22 of 97

Kupac

Törlés

​

44

42

33

14

?

?

23 of 97

Kupac

Törlés

​

44

42

33

26

14

24 of 97

Kupac

Időigény

​

O(1) max/min keresés

O(log n) beszúrás

O(log n) törlés

25 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

26 of 97

Kupac

Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

15

17

12

5

3

24

18

2

7

15

3

12

5

17

7

2

18

24

27 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

15

17

12

5

3

24

18

2

7

15

3

12

5

17

7

2

18

24

28 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

15

17

12

5

3

24

18

2

7

15

3

12

5

17

7

2

18

24

?

?

29 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

15

17

12

24

3

5

18

2

7

15

3

12

24

17

7

2

18

5

24

5

30 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

15

17

12

24

3

5

18

2

7

15

3

12

24

17

7

2

18

5

?

?

31 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

15

17

12

24

3

5

18

2

7

15

3

12

24

17

7

2

18

5

?

?

32 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

15

17

12

3

24

5

18

2

7

15

24

12

3

17

7

2

18

5

24

3

33 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

15

17

12

3

24

5

18

2

7

15

24

12

3

17

7

2

18

5

?

?

34 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

15

17

12

18

24

5

3

2

7

15

24

12

18

17

7

2

3

5

18

3

35 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

15

17

12

18

24

5

3

2

7

15

24

12

18

17

7

2

3

5

?

?

36 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

24

17

12

18

15

5

3

2

7

24

15

12

18

17

7

2

3

5

37 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

24

17

12

18

15

5

3

2

7

24

15

12

18

17

7

2

3

5

?

?

38 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

24

17

12

15

18

5

3

2

7

24

18

12

15

17

7

2

3

5

39 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

24

17

12

15

18

5

3

2

7

24

18

12

15

17

7

2

3

5

40 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

24

17

12

15

18

5

3

2

7

24

18

12

15

17

7

2

3

5

41 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

5

17

12

15

18

24

3

2

7

5

18

12

15

17

7

2

3

24

24

5

42 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

5

17

12

15

18

24

3

2

7

5

18

12

15

17

7

2

3

24

43 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

5

17

12

15

18

24

3

2

7

5

18

12

15

17

7

2

3

24

?

?

44 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

18

17

12

15

5

24

3

2

7

18

5

12

15

17

7

2

3

24

45 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

18

17

12

15

5

24

3

2

7

18

5

12

15

17

7

2

3

24

46 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

18

17

12

15

5

24

3

2

7

18

5

12

15

17

7

2

3

24

?

?

47 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

18

5

12

15

17

24

3

2

7

18

17

12

15

5

7

2

3

24

48 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

18

5

12

15

17

24

3

2

7

18

17

12

15

5

7

2

3

24

49 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

18

5

12

15

17

24

3

2

7

18

17

12

15

5

7

2

3

24

50 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

3

5

12

15

17

24

18

2

7

3

17

12

15

5

7

2

18

24

51 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

3

5

12

15

17

24

18

2

7

3

17

12

15

5

7

2

18

24

?

?

52 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

17

5

12

15

3

24

18

2

7

17

3

12

15

5

7

2

18

24

53 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

17

5

12

15

3

24

18

2

7

17

3

12

15

5

7

2

18

24

?

?

54 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

17

5

12

3

15

24

18

2

7

17

15

12

3

5

7

2

18

24

55 of 97

Kupac

  • Hogyan működik a Kupacrendezés eljárás az A = 15, 3, 12, 5, 17, 7, 2, 18, 24 tömbön?

​

​

17

5

12

3

15

24

18

2

7

17

15

12

3

5

7

2

18

24

56 of 97

Kupac

  • Mennyi a futási ideje a kupacrendezésnek n hosszúságú növekvően rendezett tömbön?

​

1

2

3

4

5

6

7

8

9

57 of 97

Kupac

  • Mennyi a futási ideje a kupacrendezésnek n hosszúságú növekvően rendezett tömbön?

​

1

2

3

4

5

6

7

8

9

N elem * a törlés (újra rendezés) idő

​

n*log n

Hasonló mint a BST

58 of 97

Keresőfák

59 of 97

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

​

60 of 97

Fák számítógépes reprezentációja

  • csúcsokat és éleiket reprezentáljuk
  • maga a fa egy mutató a gyökérre

gyerek éllista

első fiú, apa, testvér

bináris fa

…

szülő

gyerek1

gyerekk

apa

első fiú

testvér

szülő

bal

jobb

61 of 97

Keresőfák

Bináris fa: minden csúcsnak legfeljebb 2 gyereke van

62 of 97

Keresőfák

• Teljes (full) bináris fa: olyan bináris fa, ahol minden szint teljesen ki van töltve

• Majdnem teljes (complete) bináris fa: olyan bináris fa, ahol maximum a legalsó szint nincs teljesen kitöltve, csak balról jobbra haladva kitöltött néhány elemig

63 of 97

Keresőfák

Bináris fa: minden csúcsnak legfeljebb 2 gyereke van

• Kiegyensúlyozott bináris fa: olyan fa, ahol minden csúcs gyerekeinek részfáinak magassága maximum eggyel tér el.

64 of 97

Keresőfák

Hány éle van egy fának, ha n csúcsa van?

65 of 97

Keresőfák

A fa egy tulajdonságai:

  • N node - elem
  • N-1 link(edge) - él
  • Mélység – az élek száma gyökértől az „n.” elemig
  • Magasság – a leghosszabb útvonal n.-pontból a levelekig
  • Fa magassága valójában a gyökér magassága

​

1

3

8

4

5

6

7

2

9

10

11

Mélység:

​

1

​

​

​

2

​

​

​

3

A 3. elem magassága: 2

66 of 97

Keresőfák

Elemi műveletek keresőfákban (példák később):

Keres

Min/max

Következő (nagyság szerint)

Beszúr

Töröl (levél, egy gyerek, két gyerek)

Fontos: fa magassága!!!

​

1

67 of 97

Keresőfák

1

68 of 97

Keresőfák

1

69 of 97

Bináris keresés�

Probléma:

  • Adott egy rendezett tömb
  • Nevezzük ezt a tömböt „a”-nak, mely 9 elemből áll
  • Megszeretnénk tudni, hogy egy „x” szám megtalálható-e a tömbben és ha igen akkor hol?
  • Például:
      • x=81 Igen(7)
      • x=25 nem
      • x=21 Igen(3)

​

​

​

​

​

70 of 97

Bináris keresés�

  • Megismételjük az iménti lépést az alsó résztömbön
    • x=a[1]
    • x<a[1]
    • x>a[1]

​

​

​

​

71 of 97

Bináris keresőfa�

  • Bináris fák elérési ideje : O(log n)

​

​

72 of 97

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

73 of 97

Bináris kereső fa felbejárása

https://visualgo.net/en/bst

74 of 97

Legkisebb legnagyobb elem

Melyik a fa minimális, maximális eleme?

75 of 97

Legkisebb legnagyobb elem

  • A BTS legnagyobb előnye, hogy eleve rendezettek, így ha például a legkisebb vagy a legnagyobb elemet akarjuk megtalálni, akkor ez nem jár túl sok költséggel.

​

  • A legkisebb elemek mindig (leg)balról, még a legnagyobbak (leg)jobbról találhatóak.

​

76 of 97

Legkisebb legnagyobb elem

Feladat Szúrjuk be az előző keresőfába az 5 és 22 értékeket

​

77 of 97

Legkisebb legnagyobb elem

Feladat Szúrjuk be az előző keresőfába az 5 és 22 értékeket

​

78 of 97

Legkisebb legnagyobb elem

Feladat: Töröljük az előző feladatban beszúrások után kapott fából a 5,22, 6 elemeket

​

79 of 97

Legkisebb legnagyobb elem

Feladat: Töröljük az előző feladatban beszúrások után kapott fából a 5,22, 6 elemeket

​

80 of 97

Legkisebb legnagyobb elem

Feladat: Töröljük az előző feladatban beszúrások után kapott fából a 5,22, 6 elemeket

​

?

81 of 97

Legkisebb legnagyobb elem

Feladat: Töröljük az előző feladatban beszúrások után kapott fából a 5,22, 6 elemeket

​

82 of 97

Legkisebb legnagyobb elem

Feladat: Töröljük az előző feladatban beszúrások után kapott fából a 5,22, 6 elemeket

​

83 of 97

Legkisebb legnagyobb elem

Feladat: Töröljük az előző feladatban beszúrások után kapott fából a 5,22, 6 elemeket

​

84 of 97

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?

​

​

​

85 of 97

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

  • Úgy kell törölnünk, hogy a kiesett elem után megmaradjon a bináris fánk

​

  • Ez olyan esetekben amikor csak egy „gyerek” van igen egyszerűen megvalósítható

86 of 97

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

  • Eddig megoldottuk:
      • 1. eset: nincs gyerek
      • 2. eset: egy gyerek

​

  • Mi történik azonban akkor amikor nem csak egy elemet érint a törlésünk?
      • 3. eset: két gyerek

​

​

87 of 97

Törlés a fából

​

  • Nehézség csak akkor adódik, ha a törlendő elemnek két gyereke van, mivel ilyenkor az egyetlen törölt elem helyét nem foglalhatja el a két gyereke.

88 of 97

Törlés a fából

​

  • Egy másik 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.

89 of 97

Feladat

​

​

  • Határozzuk meg mi a minimum es maximum lehetséges magassága egy n elemű bináris keresőfának. Ehhez szúrjuk be egy fába a következő sorrendben a 25; 18; 47; 7; 20; 32; 56 elemeket és egy másikba a 7; 18; 20; 25; 32; 47; 56 sorrendben.

​

​

​

90 of 97

Feladat

​

​

  • Egy elem magassága valójában a leghosszabb útvonalat jelenti az elemtől a levelekig.

​

  • A fa magassága értelemszerűen a root magasságát jelenti.

​

​

​

91 of 97

Feladat

​

​

  • A fa mélysége alatt a root és az levelek közötti élek számát értjük.

​

  • A fa mélysége alatt a legnagyobb levélmélységet értjük.

​

​

92 of 97

A mélység megállapítása

  • Feladat:

​

  • Határozzuk meg mi a minimum es maximum lehetséges magassága egy n elemű bináris keresőfának.

​

  • Ehhez szúrjuk be egy fába a következő sorrendben a 25; 18; 47; 7; 20; 32; 56 elemeket és egy másikba a 7; 18; 20; 25; 32; 47; 56 sorrendben.

​

93 of 97

A mélység megállapítása

  • A fa magasságát rekurzív függvénnyel tudjuk megkeresni, ahol a részfák magasságát megkeresve jutunk el a végső megoldásig.
  • Minden egyes részfaképzés esetén 1-el megnöveljük a magasságot, még el nem jutunk a levelekig.

​

94 of 97

Elsőfiú-testvér ábrázolás

Adjunk olyan rekurzív függvényeljárást, amelyik kiszámítja a fa leveleinek számát! A fa elsőfiú-testvér ábrázolású! (Left-Child Right-Sibling Representation)

95 of 97

Elsőfiú-testvér ábrázolás

Adjunk olyan rekurzív függvényeljárást, amelyik kiszámítja a fa leveleinek számát! A fa elsőfiú-testvér ábrázolású! (Left-Child Right-Sibling Representation)

96 of 97

Kapcsolati tömb ábrázolás

97 of 97

Olvasni való

​

​

​

Fa rajzoló : http://btv.melezinek.cz/binary-search-tree.html

http://www.inf.u-szeged.hu/~rfarkas/Alga19/6_KeresoFak.pptx

http://www.inf.u-szeged.hu/~kgelle/sites/default/files/upload/alga-gyak-07_0.pdf

http://www.informatom.hu/sze/01/LGB_SZ001/Cormen-Lieserson-Rivest-Stein.-.Uj.algoritmusok.pdf

http://www.inf.u-szeged.hu/~tnemeth/jegyz/adatszerk_java.pdf

​

​

​

​