Kihagyás

1. előadás

Pusztai Kinga

Weboldal

Felvételek lesznek Teams-en, private static Video felvetel;

e-mail: kinga@inf.elte.hu

AVL Fa

  • Bináris fa
    • Kisebb "balra"
    • Nagyobb "jobbra"
  • Magasság szerint kiegyensúlyozott, ha minden csúcsa kiegyensúlyozott
  • Egy fa egy (*p) kiegyensúlyozott, ha a csúcs (p->b) egyensúlyára (balance) |p->b| <= 1.

Adott csúcs egyensúlya:

p -> b = h(p -> right) - h(p->left);

Egy Node felépítése:

  • key : T (Generic)
  • b: -1,0,1 (balance, egyensúly tárolásra)
  • left: Node*
  • right: Node*

Tétel

Tetszőleges \(n\) csúcsú nem üres AVL fa magasságára (h) igaz:

\[ \lfloor\log n\rfloor \leq h \leq 1.45 \log n \]
\[ \Updownarrow \]
\[ h \in \Theta(\log n) \]

Egyensúly jelölése

fák írásban különböző zárojelekkel elválasztva {[2] 4 [(6) 8 (10)]}

AVL fáknál az egyensúlyt is jelöljük ({[2] 4+ [(6) 8o (10)]})

A leveleknél nem jelöljük, mert az alapból nulla

Jelölések

  • Görög kisbetűk: részfák (AVL)
  • Latin nagybetűk: csúcsok kulcsai

Forgatások

A \((++, -)\) és \((--, +)\) esetekben a forgatással előre nem defniált egyensúlyi állapotok állhatnak fel, így azokat függőlegesen felsorolva érdemes jelölni (rendre {+, 0, -}), eredményeik pedig pl.:(\(h, h, h-1\))

Balra forgatás: \([\alpha \; T \; (\beta \; R \; \gamma)] \to [(\alpha \; T \; \beta) \; R \; \gamma]\)

Tulajdonságok

  • A bináris keresőfa tulajdonságot a forgatások is megtartják
  • A részfák kiegyensúlyozása egy vagy két forgatással megoldható