Čo je to strom?

  • hierarhické usporiadnie dát:

  • nadradený prvok

  • jeden alebo viac podradenných prvkov.

Aplikácie stromov

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.

Organizačné štruktúry

Hierarchia zamestnancov vo firme:

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

Webové stránky – DOM strom

HTML dokument je reprezentovaný stromovou štruktúrou.

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

DOM strom:

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

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.

Umelá inteligencia

Rozhodovacie stromy sa používajú pri:

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

Príklad:

Je vek > 18?
├── Áno → Dospelý
└── Nie → Dieťa

Kompilátory

Pri preklade programu vznikajú syntaktické stromy.

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

      +
     / \
    a   *
       / \
      b   c

Parsovanie matematických výrazov

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

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

Parsovanie programov – syntaktický strom (AST)

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

Python ast modul:

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

Reprezentácia dokumentov – Markdown strom

Document
├── Heading(level=1, text="Nadpis")
├── Paragraph(text="Nejaký text.")
├── List
│   ├── ListItem(text="položka 1")
│   └── ListItem(text="položka 2")
└── Heading(level=2, text="Podnadpis")

Rozhodovacie stromy v AI

Má > 5 rokov praxe?
├── Áno → Zamestnanec
└── Nie
    ├── Je študent?
    │   ├── Áno → Študent
    │   └── Nie → nezamestnaný
    └── Nie → nezamestnaný

Strom pozostáva z uzlov a hrán.

Uzol - dáta tkoré ukladáme

hrana - vzťah podriadenosti medzi uzlami

vťah nadradenosoti nie je definovaný.

        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

Základné pojmy

        A
      / | \
     B  C  D
    / \
   E   F
  • koreň – uzol bez rodiča, v príklade A
  • hrana – spojenie medzi dvoma uzlami
  • rodič – uzol priamo nad iným uzlom, napríklad B je rodič E
  • potomok – uzol priamo pod iným uzlom, napríklad E je potomok B
  • súrodenci – uzly s rovnakým rodičom, napríklad B, C, D
  • list – uzol bez potomkov, napríklad C, D, E, F
  • vnútorný uzol – uzol, ktorý má aspoň jedného potomka, napríklad A, B

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.

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
  • výška uzla – dĺžka najdlhšej cesty z uzla do listu
    • výška B je 1
    • výška A je 2
  • úroveň – množina uzlov s rovnakou hĺbkou
  • stupeň uzla – počet jeho priamych potomkov
  • 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

Implementácia v Pythone

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")

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

Špeciálnym prípadom binárneho stromu je Binary Search Tree.

Pre každý uzol platí:

ľavý podstrom < uzol < pravý podstrom

Príklad:

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

Výhody:

  • rýchle vyhľadávanie, vkladanie, mazanie,
  • pri vyváženom strome zložitosť O(log n).

Vyhľadávanie v BST

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ť závisí od výšky stromu:

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

Vkladanie do BST

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

Rovnako ako vyhľadávanie má zložitosť O(h).

DFS a BFS

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).

Prechody binárnym stromom

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

Pre strom:

        A
       / \
      B   C
     / \   \
    D   E   F

Preorder: Koreň → Ľavý → Pravý

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

Inorder: Ľavý → Koreň → Pravý

Pri BST získame prvky v usporiadanom poradí.

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

Postorder: Ľavý → Pravý → Koreň

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

Prechody binárnym stromom v Pythone

def preorder(node):
    if node is None:
        return
    print(node.value)
    preorder(node.left)
    preorder(node.right)

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.value)
    inorder(node.right)

def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.value)

Prechádzanie po úrovniach

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

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

Prechádzanie stromov – iteratívne prechádzanie

Rekurzívne prechádzanie je jednoduché, ale pre hlboké stromy môže dôjsť k pretečeniu zásobníka (stack overflow).

Iteratívne prechádzanie používa zásobník (stack) namiesto rekurzie.

Rekurzia aj iteratívny preorder používajú zásobník na ukladanie uzlov, ktoré ešte treba spracovať.

Volací rámec rekurzie je na zásobníku OS:

traverse(A)       # stack: [A]
  traverse(B)     # stack: [A, B]
    traverse(E)   # stack: [A, B, E]

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

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

Pre hlboký strom → RecursionError.

Iteratívny prístup → zásobník je na hromade (heap), nie vo volacom zásobníku (call stack).

Iteratívne preorder

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)

Výhody:

  • žiadne riziko stack overflow,
  • nižšia náročnosť na pamäť pri plytkých stromoch.

Bonus: Špeciálne typy stromov

V praxi sa používajú špecializované stromy optimalizované pre konkrétne úlohy.

  • B-stromy a B+-stromy – databázové indexy, súborové systémy
  • Red-Black stromy – samovyvážený BST (Java TreeMap, Linux kernel)
  • AVL stromy – prísne vyvážený BST
  • Merkle stromy – integrita dát (Git, blockchain)

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.

Mini cvičenia

  1. Určite preorder, inorder a postorder výstup pre zadaný binárny strom.
  2. Napíšte funkciu, ktorá spočíta počet uzlov v strome.
  3. Napíšte funkciu, ktorá vypočíta výšku stromu.
  4. Doplňte vkladanie hodnoty do BST.
  5. Upravte BFS tak, aby vrátil zoznam hodnôt namiesto výpisu.
Reload?