2. tétel

Question 1

Verem(stack)

Answer 1

A verem egy LIFO (last-in, first-out) adatszerkezet, egy dinamikus set (halmaz). Hátránya, hogy sok időbe telik benne a keresés.

Alapvető műveletek
Egy vermet egy n elemű tömbként tudunk implementálni, ez legyen 𝐴[1. . 𝑛]. Legyen 𝑡𝑜𝑝[𝐴] az utoljára beillesztett elem indexe. (Tehát 𝐴[1] a verem alja, 𝐴[𝑡𝑜𝑝[𝐴]] pedig a verem teteje.)
Műveletei:
* Push: a veremhez hozzáfűzzük az új elemet, amely a veremnek lesz az új teteje. Ha a veremhez hozzá akarunk fűzni még egy elemet és a verem tele van, akkor a stack túlcsordult.
* Pop: az utolsó elem törlése, így a 𝑡𝑜𝑝[𝐴] − 1 elem lesz a verem új teteje. Ha egy üres stackből törölni szeretnénk, akkor azt mondjuk, hogy a stack alulcsordult.
* Empty: megvizsgálja, hogy a stack üres-e. Akkor üres, ha a 𝑡𝑜𝑝[𝐴] = 0. Ha a 𝑡𝑜𝑝[𝐴] > 𝑛, akkor a stack túlcsordult.

Question 2

Sor(queue)

Answer 2

A sorok is dinamikus setek a veremhez hasonlóan. FIFO (first-in, first-out) adatszerkezet. Előnye, hogy az egymás után beírt adatokat a beírás sorrendjében vehetjük ki. Hátránya, hogy sok időbe telik benne a keresés.

Alapvető műveletek
Egy sorban n-1 darab elemet egy n elemű tömbként tudunk implementálni, ez legyen 𝐴[1. . 𝑛]. Legyen ℎ𝑒𝑎𝑑[𝐴] a sor eleje és 𝑡𝑎𝑖𝑙[𝐴] a sor vége. (Tehát az elemek a következőképp helyezkednek el: ℎ𝑒𝑎𝑑[𝐴], ℎ𝑒𝑎𝑑[𝐴] + 1, … , 𝑡𝑎𝑖𝑙[𝐴] − 1.)
Műveletei:
* Enqueue: a sor végére beilleszti az új elemet. Amikor a ℎ𝑒𝑎𝑑[𝐴] = 𝑡𝑎𝑖𝑙[𝐴] + 1, a sor tele van és hozzá szeretnénk fűzni egy elemet, akkor a sor túlcsordul.
* Dequeue: a sor elejéről kiszedi a legelső elemet. Ha egy üres sorból szeretnénk kiszedni egy elemet, akkor a sor alulcsordul.
* Empty: ha a ℎ𝑒𝑎𝑑[𝐴] = 𝑡𝑎𝑖𝑙[𝐴], akkor a sor üres.

Question 3

Láncolt listák (Linked lists)

Answer 3

A láncolt lista egy olyan adatstruktúra, amelyben az elemek lineáris sorrendben vannak elrendezve. Az elemek sorrendjét a mutatók határozzák meg. A láncolt listák egy egyszerű és rugalmas megoldást nyújtanak dinamikus setek reprezentálására. Előnye, hogy nagyon gyors és egyszerű a méretüket megváltoztatni, így alkalmasak dinamikusan változó számú adatok kezelésére. Hátránya, hogy csak lineáris keresés valósítható meg bennük.

Question 4

Egyszeresen és kétszeresen láncolt listák

Answer 4

Egy kétszeresen láncolt listában minden elem egy objektumként képzelhető el, mely tartalmaz egy kulcsot és két mutatót (prev, next). A 𝑛𝑒𝑥𝑡[𝑥] a következő elemre mutat, míg a 𝑝𝑟𝑒𝑣[𝑥] az előzőre. Ha x az utolsó elem, akkor a 𝑛𝑒𝑥𝑡[𝑥] = 𝑁𝐼𝐿. Ha x az első elem, akkor a 𝑝𝑟𝑒𝑣[𝑥] = 𝑁𝐼𝐿. A ℎ𝑒𝑎𝑑[𝐿] mutat a lista első elemére. Ha a ℎ𝑒𝑎𝑑[𝐿] = 𝑁𝐼𝐿, akkor a lista üres.

Egy egyszeresen láncolt listában nincs prev pointer, ami mutatna az előző elemre.

Question 5

Cirkuláris és fejelemes listák

Answer 5

Egy cirkuláris listában a fejelemnek a prev pointere a legutolsó elemre mutat. Az utolsó elem next pointere pedig a fejelemre mutat. Amelyik lista nem cirkuláris, azt fejelemes listának nevezzük.

Question 6

Láncolt listák alapműveletei

Answer 6

• Insert: új elem beszúrása
• Delete: egy adott elem törlése
• Search: egy adott elem megkeresése

Question 7

Bináris keresőfák (Binary trees)

Answer 7

Egy láncolt adatstruktúraként reprezentálhatjuk a fákat, ennek a csomópontjait pedig egy objektumként. Minden csomópont tartalmaz egy kulcsot és több pointert, melyek a következő csomópontra mutatnak. Az alábbi pointereket különböztetjük meg:
* p: a szülőre mutató pointer. Ha 𝑝 = 𝑁𝐼𝐿, akkor gyökér elemről beszélünk.
* left: a bal oldali gyerekre mutató pointer. Ha 𝑙𝑒𝑓𝑡 = 𝑁𝐼𝐿, akkor nincs balra gyerek.
* right: a jobb oldali gyerekre mutató pointer. Ha 𝑟𝑖𝑔ℎ𝑡 = 𝑁𝐼𝐿, akkor nincs jobbra gyerek.
* root[T]: a gyökér elemre mutat. Ha 𝑟𝑜𝑜𝑡[𝑇] = 𝑁𝐼𝐿, akkor a fa üres.

Question 8

Bináris keresőfa bejárások

Answer 8

Bejárások:
* Inorder:
o Bal részfa, gyökér, jobb részfa.

• Preorder:
  o Gyökér, bal részfa, jobb részfa.
• Postorder:
  o Bal részfa, jobb részfa, gyökér.

Question 9

Bináris keresőfa alapműveletek

Answer 9

• Keresés: a legrosszabb idő Ο(ℎ), ahol h a fa szintjeinek száma.
• Minimum kiválasztás: a fa legbaloldalibb elemét keressük.
• Maximum kiválasztás: a fa legjobboldalibb elemét keressük.
• Beszúrás és törlés

Question 10

Kupac(heap)

Answer 10

Bináris fa szerkezetű, de tömbben is lehet ábrázolni. A fának minden csomópontja egy tömb egy elemének felel meg.
Alapvető műveletek
Legyen 𝑙𝑒𝑛𝑔𝑡ℎ[𝐴] a tömb elemeinek a száma és legyen ℎ𝑒𝑎𝑝 − 𝑠𝑖𝑧𝑒[𝐴] a tömbben lévő kupac elemeinek a száma. Ekkor ℎ𝑒𝑎𝑝 − 𝑠𝑖𝑧𝑒[𝐴] ≤ [𝑙𝑒𝑛𝑔𝑡ℎ[𝐴]]. Legyen 𝐴[1] a heap gyökér eleme és i a csomópontok indexe. Ekkor az i-edik elem szülőjének indexe = ⌊𝑖/2⌋, a hozzá balra lévő gyerek indexe = 2𝑖, és a tőle jobbra lévő gyerek indexe = 2𝑖 + 1.
Alapvető kupac műveletek:
* Heapify: kupaccá alakítás, Ο(log(𝑛)) futási idővel. A szülő elemnek nagyobbnak kell lennie a két gyerekénél.
* Build-heap: kupac építés, mely egy buttom-up módszer egy 𝐴[1. . 𝑛] tömb kupaccá alakítására. Az eljárás minden csomópontra meghívja a Heapify függvényt, így építve meg a kupacot.
* Heap-extract-max: a kupacban lévő maximális elemet adja vissza, Ο(log(𝑛)) futási idővel.
* Heapsort: kupacban lévő elemek rendezése, Ο(𝑛 log(𝑛)) futási idővel.
* Insert: beszúrás, Ο(log(𝑛)) futási idővel.