Čo je to strom?

Strom je abstraktná dátová štruktúra, ktorá sa používa na reprezentáciu hierarchických vzťahov medzi objektmi.

Každý prvok má jeden alebo viac podradenných prvkov a maximálne jeden nadradený prvok.

        A
      / | \
     B  C  D
    / \
   E   F

Strom vs Graf

  • Strom je špeciálny prípad grafu bez cyklov.
  • Každý uzol (okrem koreňa) má práve jedného rodiča.

Definícia stromu ako grafu bez cyklov:

Nech G = (V, E) je neorientovaný graf. G je strom, ak platí:

  1. G je súvislý (existuje cesta medzi každými dvoma uzlami),
  2. G neobsahuje cykly (žiadna cesta sa nevracia späť do rovnakého uzla).

Obrázok: Strom vs Graf

         A          A
      /  | \      / | \
     B - C  D    B  C  D
    / \ /        / \
   E   F        E   F

Aplikácie stromov

Organizačné štruktúry

Hierarchia zamestnancov vo firme:

Riaditeľ
├── Ekonomické oddelenie
├── IT oddelenie
└── Personálne oddelenie

Súborové systémy

Adresárová štruktúra operačných systémov prirodzene vytvára strom.

C:
├── Dokumenty
│   ├── škola.docx
│   └── projekt.pdf
├── Obrázky
└── Hudba

Každý adresár môže obsahovať ďalšie podadresáre a súbory.

DOM strom

HTML dokument je reprezentovaný stromovou štruktúrou.

<html>
    <body>
        <h1>Nadpis</h1>
        <p>Text</p>
    </body>
</html>

prehliadač premení HTML dokument na DOM (document object model) :

html
└── body
    ├── h1
    └── p

Parsovanie matematických výrazov

Výraz (a + b) * (c - d):

          *
         / \
        +   -
       / \ / \
      a  b c  d

Strom vyjadruje hierarchiu operácií a ich poradie.

Kompilátory

Pri preklade programu vznikajú syntaktické stromy.

Výraz a + b * c je reprezentovaný ako:

      +
     / \
    a   *
       / \
      b   c

Pri preklade programu sa uzly menia na inštrukcie

Príklad na parsovanie – syntaktický strom (AST)

import ast
tree = ast.parse("a + b * c")
print(ast.dump(tree))

matematický výraz sa premení na:

Assign
├── name: x
└── BinaryOp (+)
    ├── Literal(3)
    └── Literal(4)

Rozhodovacie stromy

sa používajú pri:

  • klasifikácii dát,
  • predikcii výsledkov,
  • strojovom učení.

Rozhodovacie stromy - Príklad

Je vek > 18?
├── Áno → Dospelý
└── Nie → Dieťa
Má > 5 rokov praxe?
├── Áno → Zamestnanec
└── Nie
    ├── Je študent?
    │   ├── Áno → Študent
    │   └── Nie → nezamestnaný
    └── Nie → nezamestnaný

Databázové systémy

Databázy používajú stromové indexy (B-stromy, B+ stromy) na rýchle vyhľadávanie údajov.

Bez stromov by vyhľadávanie v miliónoch záznamov bolo výrazne pomalšie.

Strom pozostáva z uzlov a hrán.

Uzol - dáta tkoré ukladáme

hrana - vzťah podriadenosti medzi uzlami

        A
      / | \
     B  C  D
    / \
   E   F

Typy uzlov

Každý uzol má najviac jedného rodiča, ale môže mať ľubovoľný počet potomkov.

        A           <- koreň (root)
      / | \
     B  C  D       <- B, C, D sú synovia (children) A
    / \      \
   E   F      H    <- E, F, H sú listy (leaves) – nemajú potomkov

koreň – uzol bez rodiča

listový uzol – uzol bez potomkov

nelistový uzol – uzol s aspoň jedným potomkom

Hĺbka, výška a podstrom

        A
      / | \
     B  C  D
    / \
   E   F
  • hĺbka uzla – počet hrán od koreňa k uzlu
    • hĺbka A je 0, hĺbka E je 2
  • hĺbka stromu – dĺžka najdlhšej cesty od koreňa k listu
    • hĺbka stromu je 2
  • úroveň – množina uzlov s rovnakou hĺbkou
  • podstrom – uzol spolu so všetkými jeho potomkami

Binárny strom

Najznámejším a najjednoduchším špeciálnym prípadom stromu je binárny strom.

Binárny strom je strom, v ktorom môže mať každý uzol najviac dvoch potomkov:

  • ľavého potomka,
  • pravého potomka.

Príklad:

        A
       / \
      B   C
     / \   \
    D   E   F

Naivná implementácia binárneho stromu

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

root = Node("A")
root.left = Node("B")
root.right = Node("C")
root.left.left = Node("D")
root.left.right = Node("E")
root.right.right = Node("F")

Využitie binárnych stromov

implementácia množiny a slovníka

  • kľúč vieme vyhľadať a vložiť v logaritmickom čase
  • kľúče sú implicitne zotriedené

rozhodovací strom

  • otázky sú nelistové uzly
  • v prípade áno ideme doľava, v prípade nie doprava.
  • konečné odpovede sú listové uzly

Binárny vyhľadávací strom (BST)

Môžeme ho použiť na implementáciu množiny alebo slovníka.

Pre každý uzol platí:

ľavý podstrom < uzol < pravý podstrom

Príklad:

         50
       /    \
      30     70
     / \    / \
    20 40  60 80

Vyhľadávanie v BST

  • Ak je hľadaná hodnota menšia, ideme do ľava.
  • Ak je väčšia, ideme do prava
def search(node, value):
    if node is None:
        return False

    if node.value == value:
        return True

    if value < node.value:
        return search(node.left, value)

    return search(node.right, value)

Zložitosť vyhľadávania BST

závisí od výšky stromu:

  • vyvážený strom: O(log n)

  • degenerovaný strom: O(n)

  • Vkladanie už zotriedenej množiny produkuje degenerovaný strom

               10
              /   \
             5    11
                   \
                    12
                     \
                      13

Vkladanie do BST

  • Ak je hodnota menšia ako hodnota uzla, vložíme ju do ľavého podstromu.
  • Ak je väčšia, vložíme ju do pravého podstromu.
  • Ak je hodnota rovnaká, môžeme ju ignorovať (množina) alebo aktualizovať (slovník).
def insert(node, value):
    if node is None:
        return Node(value)

    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)

    return node

AVL Strom

Vkladaním hodnôt do BST môže vzniknúť degenerovaný strom. Preto sa používajú samovyvážené binárne vyhľadávacie stromy.

  • AVL strom je samovyvážený binárny vyhľadávací strom, v ktorom sa výška ľavého a pravého podstromu líši najviac o 1.
  • Pri vkladaní alebo odstraňovaní uzlov sa strom vyvažuje pomocou rotácií.
  • Zložitosť vyhľadávania, vkladania a odstraňovania je O(log n).
  • Vymyslel ho Adelson-Velsky a Landis v roku 1962.

Príklad na rotáciu do prava:

        30           20
       /  \        /    \
      20   40     10     30
     /                    \
    10                     40

Uzol naľavo (20) nazývame pivot (os). Po rotácii sa pivot stane koreňom podstromu.

def right_rotate(y):
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    return x

Prechody binárnym stromom

Prechádzanie stromu znamená systematicky navštíviť všetky jeho uzly.

V akom poradí navštívime uzly závisí od typu prechodu.

        A
       / \
      B   C
     / \   \
    D   E   F

Spôsoby prechodu binárnym stromom

        A
       / \
      B   C
     / \   \
    D   E   F
  • Preorder: Koreň → Ľavý → Pravý A → B → D → E → C → F
  • Inorder: Ľavý → Koreň → Pravý D → B → E → A → C → F
  • Postorder: Ľavý → Pravý → Koreň D → E → B → F → C → A

Prechody binárnym stromom

def preorder(node):
    if node is None:  # Najprv navštívime koreň
        return
    print(node.value)
    preorder(node.left) # Prejdeme do ľavého podstromu
    preorder(node.right) # Prejdeme do pravého podstromu

def inorder(node):
    if node is None:
        return
    inorder(node.left) # Prejdeme do ľavého podstromu
    print(node.value) # Navštívime koreň
    inorder(node.right) # Prejdeme do pravého podstromu

def postorder(node):
    if node is None:
        return
    postorder(node.left) # Prejdeme do ľavého podstromu
    postorder(node.right) # Prejdeme do pravého podstromu
    print(node.value)   # Navštívime koreň

Využitie prechodov

  • inorder – výpis hodnôt v zotriedenom poradí
  • preorder - zápis stromu do súboru - serializácia stromu
  • postorder - vymazanie stromu (najprv vymažeme potomkov, až potom koreň)

Prechádzanie stromov využíva zásovbník

  • každá rekurzia vytvorí nový kontext lokálnych premenných a starý uloží na interný zásobník (call stack).
  • pre hlboké stromy môže dôjsť k pretečeniu zásobníka (stack overflow).
traverse(A)       # call stack: [A]
  traverse(B)     # call stack: [A, B]
    traverse(E)   # calll stack: [A, B, E]

Python má limit rekurzie (zvyčajne 1000):

import sys
print(sys.getrecursionlimit())  # 1000

Iteratívne prechádzanie preorder

  • používa vlastný zásobník (stack) namiesto rekurzie.
def traverse_iterative(root):
    if root is None:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.value)
        for child in reversed(node.children):
            stack.append(child)

Iteratívne prechádzanie inorder

def inorder_iterative(root):
    stack = []
    current = root
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        print(current.value)
        current = current.right

Iteratívne prechádzanie postorder

def postorder_iterative(root):
    stack = []
    last_visited = None
    current = root
    while stack or current:
        if current:
            stack.append(current)
            current = current.left
        else:
            peek_node = stack[-1]
            if peek_node.right and last_visited != peek_node.right:
                current = peek_node.right
            else:
                print(peek_node.value)
                last_visited = stack.pop()

Prechádzanie po úrovniach

Prechádzanie stromu znamená systematicky navštíviť všetky jeho uzly.

DFS – Depth-First Search

  • ide čo najhlbšie do vetvy,
  • používa rekurziu alebo zásobník,
  • patrí sem preorder, inorder a postorder.

BFS – Breadth-First Search

  • prechádza strom po úrovniach,
  • používa rad (queue).

Prechádzanie po úrovniach navštevuje uzly zhora nadol a zľava doprava.

  • vyhľadávanie najkratšej cesty v grafe,
  • vyhľadávanie v stromoch,
  • vyhľadávanie v hierarchických štruktúrach (adresáre, DOM strom, organizačné štruktúry).

Používa sa rad (queue).

        A
       / \
      B   C
     / \   \
    D   E   F

Výstup: A → B → C → D → E → F

Prechádzanie po úrovniach v Pythone

from collections import deque

def level_order(root):
    if root is None:
        return

    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)

        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)

N-árne stromy

V mnohých praktických aplikáciách nestačia iba dvaja potomkovia. Preto používame n-árne stromy.

N-árny strom je strom, v ktorom môže mať každý uzol až n potomkov.

Príklad:

           A
        /  |  \
       B   C   D
     / | \     |
    E  F  G    H

Implementácia v Pythone

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

root = Node("A")
b = Node("B")
c = Node("C")
d = Node("D")

b.children.extend([Node("E"), Node("F"), Node("G")])
d.children.append(Node("H"))

root.children.extend([b, c, d])

Rekurzívny prechod n-árneho stromu

def traverse(node):
    if node is None:
        return
    print(node.value)
    for child in node.children:
        traverse(child)

Výstup: A → B → E → F → G → C → D → H

Prefixový strom (trie)

ktorý sa používa na efektívne vyhľadávanie reťazcov.

          root
         /    \
        c      b
       / \      \
      a   o      a
     /     \      \
    t       d      n
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

    def insert(self, word):
        node = self
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

Bonus: B-stromy a B+-stromy

Bežné binárne stromy nie sú vhodné pre databázové indexy – diskové operácie sú pomalé a strom by bol príliš hlboký.

B-strom – každý uzol má viac ako dvoch potomkov:

            [15]
          /   |   \
     [5,10]  [25]  [40]
    /  |  \  / \   /  \
   2   8 13 18 22 35  45

Vlastnosti:

  • každý uzol má maximálne m detí,
  • všetky listy sú na rovnakej úrovni,
  • operácie majú zložitosť O(log n).

B+-strom – údaje sú len v listoch, listy sú prepojené → efektívny range query.

Bonus: Red-Black stromy

Samovyvážený binárny vyhľadávací strom. Každý uzol je červený alebo čierny.

Pravidlá:

  1. Uzol je červený alebo čierny.
  2. Koreň je čierny.
  3. Červený uzol nemôže mať červeného rodiča.
  4. Každá cesta od uzla k listu má rovnaký počet čiernych uzlov.

Dôsledok: žiadna cesta nie je viac ako 2× dlhšia ako iná → strom je takmer vyvážený.

Operácie: O(log n). Použitie: Java TreeMap/TreeSet, Linux kernel.

Zhrnutie:

  • Strom je abstraktná dátová štruktúra, ktorá sa používa na reprezentáciu hierarchických vzťahov medzi objektmi.
  • Strom pozostáva z uzlov a hrán, pričom každý uzol má najviac jedného rodiča, ale môže mať ľubovoľný počet potomkov.
  • Binárny strom je špeciálny prípad stromu, kde každý uzol môže mať najviac dvoch potomkov. Binárne vyhľadávacie stromy (BST) umožňujú efektívne vyhľadávanie, vkladanie a odstraňovanie hodnôt.
  • Prechádzanie stromov môže byť realizované rôznymi spôsobmi, vrátane preorder, inorder, postorder a prechádzania po úrovniach. Prechádzanie môže byť implementované rekurzívne alebo iteratívne pomocou zásobníka alebo fronty.
  • Prefixové stromy (trie) sú špeciálne stromy používané na efektívne vyhľadávanie reťazcov, kde každý uzol reprezentuje znak a cesty od koreňa k listom reprezentujú slová.
Reload?