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
Definícia stromu ako grafu bez cyklov:
Nech G = (V, E) je neorientovaný graf. G je strom, ak platí:
Obrázok: Strom vs Graf
A A
/ | \ / | \
B - C D B C D
/ \ / / \
E F E F
Hierarchia zamestnancov vo firme:
Riaditeľ
├── Ekonomické oddelenie
├── IT oddelenie
└── Personálne oddelenie
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.
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
Výraz (a + b) * (c - d):
*
/ \
+ -
/ \ / \
a b c d
Strom vyjadruje hierarchiu operácií a ich poradie.
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
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)
sa používajú pri:
Je vek > 18?
├── Áno → Dospelý
└── Nie → Dieťa
Má > 5 rokov praxe?
├── Áno → Zamestnanec
└── Nie
├── Je študent?
│ ├── Áno → Študent
│ └── Nie → nezamestnaný
└── Nie → nezamestnaný
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.
Uzol - dáta tkoré ukladáme
hrana - vzťah podriadenosti medzi uzlami
A
/ | \
B C D
/ \
E F
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
A
/ | \
B C D
/ \
E F
A je 0, hĺbka E je 2Najzná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:
Príklad:
A
/ \
B C
/ \ \
D E F
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")
implementácia množiny a slovníka
rozhodovací strom
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
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)
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
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
Vkladaním hodnôt do BST môže vzniknúť degenerovaný strom. Preto sa používajú samovyvážené binárne vyhľadávacie stromy.
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
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
A
/ \
B C
/ \ \
D E F
A → B → D → E → C → FD → B → E → A → C → FD → E → B → F → C → Adef 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ň
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
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)
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
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 stromu znamená systematicky navštíviť všetky jeho uzly.
DFS – Depth-First Search
BFS – Breadth-First Search
Používa sa rad (queue).
A
/ \
B C
/ \ \
D E F
Výstup: A → B → C → D → E → F
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)
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
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])
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
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
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:
B+-strom – údaje sú len v listoch, listy sú prepojené → efektívny range query.
Samovyvážený binárny vyhľadávací strom. Každý uzol je červený alebo čierny.
Pravidlá:
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: