Vyhľadávací strom

Vyhľadávací strom

Zovšeobecnenie spojkového zoznamu, kde jeden prvok má viacero smerníkov.

  • Každý uzol má nula alebo viac podradených uzlov (synov).
  • Uzol, ktorý nemá nadradený uzol, sa nazýva koreň stromu.
  • Uzol, ktorý nemá podradené uzly, sa nazýva list.
  • Každý uzol je zároveň koreňom podstromu.

Prvok binárneho vyhľadávacieho stromu

  • kľúč
  • hodnota
  • smerníky na ďalšie prvky:
    • ľavý syn
    • pravý syn

Príklad na (binárny) vyhľadávací strom

struct binary_tree {
    int data;
    struct binary_tree* left;
    struct binary_tree* right;
};

Ako to vyzerá v pamäti?

              left     +------+   right
                  +--- |  5   | ----+
                  |    +------+     |
                  v                 V
          left +------+          +------+
          +----|  3   |          |  10  |
          |    +------+          +------+
          |
          V
      +------+
      |  1   |
      +------+

Demo BST

https://www.cs.usfca.edu/~galles/visualization/BST.html

Aritmetický výraz ako strom

        Matematický výraz:  3 * (5 + 6)

              left     +------+   right
                  +--- |  *   | ----+
                  |    +------+     |
                  v                 V
          left +------+          +------+
          +----| +    |---+      |   3  |
          |    +------+   |      +------+
          V               V
      +------+         +------+
      |  5   |         |  6   |
      +------+         +------+

Inorder

Naľavo, hodnota, napravo

3 * 5 + 6

Pozor na zátvorky!

Preorder

hodnota, naľavo, napravo

* + 5 6 3

Postorder

naľavo, napravo, hodnota

5 6 + 3 *

Reprezentácia hierarchických štruktúr

  • matematické výrazy
  • DOM (Document Object Model)
    • HTML stránka
    • Office dokument
  • AST (Abstract Syntax Tree)
    • preklad jazyka C do strojového kódu

Asociatívne pole

pomocou binárneho vyhľadávacieho stromu

  • Každá hodnota sa tam nachádza maximálne raz (nemôžu sa opakovať).
  • Je definovaná operácia čiastočného usporiadania (hodnoty môžeme zoradiť a porovnať).
  • Všetky hodnoty v ľavom podstrome sú menšie ako hodnota v uzle a všetky hodnoty v pravom podstrome sú väčšie.

info

Triedenie pomocou BST

  • Vložíme prvky do BST.
  • Vypíšeme prvky inorder.
  • Logaritmická zložitosť vyhľadávania.

Prechádzanie BST

Akým spôsobom vieme strom zapísať do jedného riadku?

  • Inorder
  • Preorder
  • Postorder

Načítanie do stromu

Ak máme zadaný zápis v jednom riadku, akým spôsobom ho môžeme uložiť do stromu?

  • infixná notácia
  • prefixná notácia
  • postfixná notácia (reverzná poľská notácia)

Vyhľadávanie v binárnom vyhľadávacom strome

(preorder)

  1. Pozrieme sa na koreň stromu.
  2. Ak sa hodnoty zhodujú, našli sme výsledok.
  3. Ak sa nezhodujú a hodnota, ktorú hľadáme, je menšia ako hodnota v uzle, hľadáme vľavo.
  4. Ak je hodnota väčšia, hľadáme vpravo.

Vymazanie z BST

  • Ak má nula potomkov: Vymažeme uzol.
  • Ak má jedného potomka: Nahradíme uzol za ďalší uzol a pôvodný uzol vymažeme.
  • Ak má dvoch potomkov:
    • Nájdeme jeho inorder potomka.
    • Vymeníme hodnotu v uzle za hodnotu jeho inorder nasledovníka.
    • Vymažeme inorder nasledovníka z pravého podstromu.

Vyhľadanie potomka (väčšieho prvku)

  • Ak má uzol X pravého syna, nasleduje najmenší prvok v pravom podstrome.
  • Ak uzol X nemá pravého syna a je ľavým synom svojho rodiča, potom nasleduje rodič.
  • Ak uzol X nemá pravého syna a je pravým synom svojho rodiča, hľadaj predka, ktorý je ľavým synom svojho rodiča. Tento rodič je nasledovník.
  • Inak prvok X nemá nasledovníka (je najväčší v strome).

info

Príklad: Počítadlo slov pomocou BST

  • Pomocou BST si vieme vytvoriť asociatívne pole.
  • Asociatívne pole bude stále zoradené podľa abecedy.
  • Bude mať možnosť vymazania niektorého slova.

Vyvážené vyhľadávacie stromy

Vlastnosti vyhľadávacieho stromu

  • Výška stromu: maximálny počet predkov listového uzla (koľko "poschodí" má strom).
  • Faktor vyváženia uzla: rozdiel výšky ľavého a pravého podstromu.

Nevyváženosť stromu

Vkladanie prvkov v určitom poradí môže spôsobiť, že strom sa stane nevyváženým.

UPOZORNENIE: Binárny strom sa môže zdegenerovať na spojkový zoznam. Operácia vyhľadávania bude mať lineárnu a nie logaritmickú zložitosť.

Zle vyvážený strom

Výška 3

              left     +-----+
                  +--- |  1  |
                  |    +-----+
                  v
          left +------+
          +----|  2   |
          |    +------+
          V
      +------+
      |  3   |
      +------+

Vyvážené vyhľadávacie stromy

  • Počas vkladania alebo vyberania prvkov sa strom vyvažuje.
  • Rotácia stromu: operácia, ktorá mení štruktúru stromu, aby sa zachovala vyváženosť.

Operácie na vyváženie binárneho stromu

To be continued....

Reload?