Kihagyás

1. gyakorlat

Default infók

  • Gyakvez: Varga Henrik
  • Idő: Hétfő 14:15-15:45
  • Maximális szorgalmi pont: 20 (egy jegy)
  • Minimum 2-es mind két ZH-n
  • ~~Nincsenek~~ Vannak (/s?) kötelező heti kvízek :letsfuckinggoooooo:

Online jegyzetek, vizualizációk

Egyéb vizualizációk

Ásványi jegyzetek

Olyan anyagra, amire nem tudja az választ, arra lehet szorgalmi pontot szerezni, ha mi megtaláljuk (algoritmusok és adatszerkezetek 2-vel kapcsolatban).

AVL fa

  • A világ legjobb adatszerkezetei a fák (bináris fák, to be exact) (ez egy faktoid, ez benne lesz a ZH-ban)

A bináris fa lehet nem valami szép is. Ha NAGYON nem valami szép, akkor basically egy láncolt lista.

A fánkat rendbe kéne rakni.

  • A bináris fa minden művelet után rendeződik
  • Azt akarjuk megtartani hogy mindig logaritmikus idő legyen

Az AVL fák magasság szerint kiegyensúlyozott bináris keresőfák

AVL fa feltétele:

  • Minden belső csúcs jobb és bal részfájának magassága közötti különbség \(\leq 1\), avagy \(|h(p \rightarrow right)-h(p \rightarrow left)| \leq 1\)

Minden beszúrásnál ellenőrizzük, hogy ez a feltétel teljesül-e.

Minden csúcs egyensúlyát (az előbb kiszámolt \(h(p \rightarrow right)-h(p \rightarrow left)\) értéket) eltároljuk. A követelmény miatt az értéke csak \(-1, 0, 1\) lehet.

\(p \rightarrow b \in \{ -1, 0, 1 \}\)

Forgatási sémák

1-es távolságú eltérések gyakorian előfordulnak, a forgatást előidéző event az első 2-es távolságú eltérés megjelenése, aminek eredményeként vagy egyenlőség, vagy egyes eltérés fog csak maradni a fában

  • -: A fa magassága balra 1-gyel nagyobb, mint jobbra
  • +: A fa magassága jobbra 1-gyel nagyobb, mint jobbra
  • --: A fa magassága balra 2-vel nagyobb, EZT kell megszüntetni

  • ++: A fa magassága jobbra 2-vel nagyobb, EZT kell megszüntetni

  • \((++,+) (--,-) (++,-) (--,+)\)

  • \((++,+)\text{ séma tükörképe a } (--,-)\)

  • \((++,-)\text{ séma tükörképe } (--,+)\)

  • ++ +: A fa jobbra húz, és a jobb részfa IS jobbra húz

  • -- -: A fa balra húz, és a bal részfa Is balra húz
  • ++ -: A fa jobbra húz, de a jobb részfa balra
  • -- +: A fa balrara húz, de a bal részfa jobbra

Megoldás: Úgy "forgatni" a csúcsokat, hogy az továbbra is rendezőfa maradjon (?), de a ++/-- egyensúlyok eltűnjenek.

Vizualizáció

Törlés esetén lehetséges egyéb sémák:

  • (--, =): (--, -) basically
  • (++, =): (++, +) basically

Illetve, itt már lehetséges több forgatás is.

Törlésnél jobb részfa minimumával cserélünk, ha a jelenlegi csúcs nem levél

remMin: like bináris fánál