Dynamické datové struktury

• Co jsme dnes dělali?
  • Zásobník (datová struktura!!!) a fronta
  • Binární výhledávací strom

Co jsme dnes dělali?

Zásobník (datová struktura!!!) a fronta

• Dvě důležité obecné datové struktury, které se hojně používají
  • Není závislá na implementaci, respektive si ji můžeme naimplementovat, jak chceme
• Zásobník (stack)
  • Princip LIFO - last in, first out
  • Klasický příklad - představte si na sebe naskládané talíře. Abychom žádné nerozbili, můžeme buď přidávat talíře na vrch nebo odebírat talíře z vrchu.
  • Pro zásobník definujme (kromě inicializace) dvě operace
    • PUSH - přidaní na vrchol zásobníku
    • POP - odebrání a vrácení hodnoty z vrcholu zásobníku
  • Se zásobníkem se ještě potkáme, až se budeme zabývat vyhodnocováním aritmetického výrazu
  • Implementace polem (pokud budeme fixovat velikost), spojovým seznamem
• Fronta (queue)
  • Princip FIFO - first in, first out
  • Můžeme si ji představit, mno, jako frontu (lidí). Ti, co se do fronty zařadí dříve, přijdou dříve na řadu.
  • Pro frontu budeme definovat dvě operace
    • ENQUEUE - přidání na konec fronty
    • DEQUEUE - odebrání a vrácení hodnoty z konce fronty
  • Implementace stejná, jako u zásobníku

Jaké mají operace na zásobníku a ve frontě časovou složitost?

Binární výhledávací strom

• Binární strom je strom, kde každý vrchol má nejvýše dva potomky.
• Binární výhledávací strom (binary search tree) je binární strom, který splňuje pro každý vrchol následující podmínky:
  • Hodnoty v levém podstromu jsou menší než hodnota ve vrcholu
  • Hodnoty v pravém podstromu jsou větší než hodnota ve vrcholu
• Díky této vlastnosti můžeme efektivně vyhledávat hodnoty, a to v průměru v čase $\mathcal{O}(\log n)$, kde $n$ je počet vrcholů ve stromu.
• Pozor!!! V nejhorším případě (pokud je strom nevyvážený) může být časová složitost vyhledávání až $\mathcal{O}(n)$.
  • To nastane například, pokud do stromu přidáváme již seřazená data; strom musíme konstruovat pečlivě (jak na to?)
    • Jak zkonstruovat BVS tak, aby byl vyvážený?
  • Problém nastává při přidávání a odebírání hodnot, kdy musíme zajistit, aby strom zůstal vyvážený.
• Existují speciální druhy binárních výhledávacích stromů, takzvané samovyvažovací, které zajišťují, že strom zůstane vyvážený i po přidávání a odebírání hodnot.
  • Například AVL stromy, Červeno-černé stromy.
  • Více info o AVL stromech je zde a zde.
• Kde se AVL stromy používají?
  • Poznámka na začátek: všechny opreace v AVL stromu jsou $\mathcal{O}(\log n)$.
  • Problém 1: Najdi prvky v intervalu $[a, b]$.
    • Např. uvažme databázi incidentů. Chceme najít všechny incidenty, které se staly mezi dvěma daty.
    • Řešení: Uložme incidenty do AVL stromu, kde klíčem bude datum incidentu. Na velkém datasetu je logaritmická složitost velmi příjemná.
  • Problém 2: Seřazená hashmapa (slovník)
    • Slovníky (hashmapy) se obecně implementují pomocí hešování, což umožňuje velmi rychlý přístup k hodnotám na základě klíče.
    • Nejsou ale seřazené.
    • Řešení: Použijeme AVL strom, to nám dá bonus v podobě řešení problému 1.
      • Můžeme efektivně procházet klíče ve vzestupném pořadí.
      • Můžeme rychle najít minimální a maximální klíč.
      • Můžeme najít předchůdce a následníka daného klíče.