Vyhľadávací strom

Strom

Typ grafu:

  • uzol: dáta
  • hrana: orientované spojenie medzi uzlami
  • Z koreňového uzla existuje práve jedna cesta do každého ostatného uzla
  • Z listového uzla nejde žiadna cesta.

Reprezentácia hierarchických štruktúr

  • asociatívne pole
  • matematické výrazy
  • DOM (Document Object Model)
    • html stránka
    • office dokument
  • AST (Abstract Syntax Tree)
    • preklad jazyka C do strojového kódu

Reprezentácia hierarchických štruktúr

Matematický výraz:  3 * (5 + 6)
        left     +------+   right
            +--- |  *   | ----+
            |    +------+     |
            v                 V
    left +------+          +------+
    +----| +    |---+      |   3  |
    |    +------+   |      +------+
    V               V
+------+         +------+
|  5   |         |  6   |
+------+         +------+

Rýchle vyhľadávanie

Bisekcia:

            5
          /   \
         3     8
        / \   / \
       2   4 7   9
      /     /     \
     1     6      10
1 2 3 4 5 6 7 8 9 10

Vyhľadávací strom

Zovšeobecnenie spojkového zoznamu, kde jeden prvok má viac 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 podradeného stromu.

Prvok vyhľadávacieho stromu

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

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

Prechádzanie BST

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

  • Inorder
  • Preorder
  • Postorder

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 *

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)

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

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

Vyhľadávanie vo vyhľadávacom strome

(pre-order)

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

Vymazanie z BST

Vyhľadáme prvok so zadanou hodnotou.

  • Ak má nula potomkov
    • Vymažeme
  • Ak má jedného potomka:
    • Nahradíme za potomka a vymažeme
  • Ak má dvoch potomkov:
    • Nájdeme k nemu "ďalší prvok".
    • Vymeníme hodnoty.
    • Z väčšieho podstromu vymažeme "ďalší prvok".

Triedenie s pomocou BST

  • Vložíme prvky do BST
  • Vypíšeme prvky INORDER

Bibliografia

Reload?