Stromy

Proč to potřebuji?

Stromy jsou jednou z nejdůležitějších struktur v teorii grafů i v informatice. Využívají se při návrhu datových struktur (binární vyhledávací stromy, haldy), síťových protokolů (kostry sítí), kompresních algoritmů (Huffmanův kód) nebo při organizaci hierarchických dat (souborové systémy, XML/HTML). Pochopení stromů je klíčové pro další témata, jako jsou kostry grafů nebo prohledávací algoritmy.

Předpoklady: Základní pojmy teorie grafů (graf, cesta, kružnice, souvislost, stupeň vrcholu).

Teorie

3.1 Definice stromu

Definice 3.1 — Strom, list, vnitřní vrchol

Strom: souvislý graf neobsahující kružnici (acyklický souvislý graf)
List: vrchol stupně 1 v netriviálním stromu
Vnitřní vrchol: vrchol stupně většího než 1

3.2 Věty o stromech

Věta 3.1 — Věta o listu / listech

Každý netriviální strom obsahuje list (vrchol stupně 1)
Každý netriviální strom má alespoň dva listy

Věta 3.2 — Ekvivalentní podmínky pro strom

Pro graf T s n vrcholy a m hranami jsou následující tvrzení ekvivalentní:

T je strom
Mezi libovolnými dvěma vrcholy existuje právě jedna cesta
T je souvislý a m = n - 1
T je souvislý a každá jeho hrana je most
T neobsahuje kružnici a m = n - 1
T neobsahuje kružnici a přidáním libovolné hrany vznikne právě jedna kružnice

Klíčový vztah

Strom s n vrcholy má vždy právě n - 1 hran

Toto je základní vlastnost, kterou používáme ve všech úlohách!

3.3 Les

Definice 3.2 — Les

Les je acyklický graf (graf bez kružnic). Každá komponenta lesa je strom.

Věta 3.3 — Vztah vrcholů a hran v lese

Les s k komponentami:

|V| = |E| + k neboli m = n - k

Příklad — Les

Les s 12 vrcholy a 8 hranami: k = 12 - 8 = 4 komponenty

3.4 Kořenový strom

Definice 3.3 — Kořenový strom

Kořenový strom (T, r): strom T s pevně zvoleným vrcholem r (kořen)
Předchůdce / následník: x je předchůdce y, když leží na cestě z kořene do y
Přímý předchůdce (otec) / přímý následník (syn, potomek): sousední předchůdce/následník
Vrstva k: všechny vrcholy ve vzdálenosti k od kořene
Hloubka stromu: největší číslo vrstvy, ve které leží list
Podstrom s kořenem v: podgraf obsahující v a všechny jeho následníky
Centrum stromu: opakovaným odebíráním listů nalezneme centrum (1 vrchol) nebo bicentrum (1 hrana)

Definice 3.4 — Uspořádaný (pěstovaný) strom

Kořenový strom, ve kterém je pro každý vrchol jednoznačně dáno pořadí jeho následníků zleva doprava.

3.5 Kód stromu

Definice 3.5 — Kód uspořádaného stromu

Sestavuje se rekurzivně z kódů všech podstromů kořene, uzavřených do páru 0 a 1.

Každému listu odpovídá kód 01
Vnitřní vrchol zdědí kódy svých potomků zleva doprava a uzavře je do 0...1

Definice 3.6 — Kreslení stromu podle kódu

0 = nakresli hranu dolů a nový vrchol
1 = vrať se k předchůdci

Příklad — Kód stromu

Kód: 000110010111

Kreslíme: 0(kořen)→0(syn)→0(syn)→1(zpět)→1(zpět)→0(syn)→0(syn)→1(zpět)→0(syn)→1(zpět)→1(zpět)→1(konec)

Definice 3.7 — Minimální kód

Jako obyčejný kód, ale před uzavřením do 0...1 se kódy potomků uspořádají lexikograficky (od nejmenších). Dva kořenové stromy jsou izomorfní ⇔ mají stejný minimální kód.

3.6 Binární strom

Definice 3.8 — Binární strom

Binární strom: kořenový strom, kde každý vrchol má nejvýše dva přímé následníky (levý a pravý syn)
Vrcholově ohodnocený binární strom: každý vrchol je ohodnocen reálným číslem

3.7 Binární vyhledávací strom (BVS)

Definice 3.9 — Binární vyhledávací strom

Binární vyhledávací strom: ohodnocený binární strom, kde pro každý vrchol v platí:

Všechny hodnoty v levém podstromu ≤ hodnota v
Všechny hodnoty v pravém podstromu ≥ hodnota v

Jak vkládat (insert)

Porovnáváme s aktuálním vrcholem: menší → jdi vlevo, větší → jdi vpravo. Opakujeme, dokud nenajdeme volné místo.

Jak odebírat

List: prostě smazat
1 potomek: nahradit potomkem
2 potomci: nahradit buď nejpravějším prvkem z levého podstromu nebo nejlevějším z pravého podstromu

Příklad — Vložení čísel 25,1,18,5,31,14,30 do BVS

25 je kořen. 1 < 25 → vlevo. 18 < 25 vlevo, 18 > 1 vpravo. 5 < 18 vlevo. Atd.

3.8 Preorder, Inorder, Postorder

Definice 3.10 — Tři způsoby průchodu binárním stromem

PREORDER	INORDER	POSTORDER
1. Zpracuj vrchol 2. Levý podstrom 3. Pravý podstrom	1. Levý podstrom 2. Zpracuj vrchol 3. Pravý podstrom	1. Levý podstrom 2. Pravý podstrom 3. Zpracuj vrchol
Prefixový zápis	Infixový zápis	Postfixový zápis

Příklad — Výraz (4*(8*1))+(((3-1)*5)/2)

          +
         / \
        *    /
       / \  / \
      4   * *   2
         / \ / \
        8  1 -  5
            / \
           3   1

INORDER: 4 * 8 * 1 + 3 - 1 * 5 / 2 (infixový zápis)

Výsledek: (4·(8·1)) + (((3-1)·5)/2) = 32 + 5 = 37

3.9 Halda

Definice 3.11 — Halda (min-heap)

Halda (min-heap): ohodnocený binární strom s pevnou strukturou, kde ohodnocení libovolného vrcholu není větší než ohodnocení kteréhokoliv z jeho následníků.

Struktura: všechny vrstvy jsou plné kromě poslední, která se plní zleva doprava.

Operace s haldou

Insert: vlož na další pozici (dole), pak probublávej nahoru (swap s otcem, dokud není splněna podmínka)
Odebrání kořene: nahraď kořen posledním prvkem, pak probublej dolů (swap s menším synem)

Příklad — Halda z čísel 25,1,18,5,31,14

Vložíme 25 → kořen. Vložíme 1 → levý syn, 1 < 25 ⇒ swap.

Kořen = 1 (nejmenší prvek). Při odebrání kořene nahradíme číslem 18, pak probubláme dolů.

Cvičení k procvičení

Cvičení 1 — Skóre stromu: Může být (1,1,1,1,2,3,3,4) skóre stromu?

1) Je to skóre grafu? ANO (ukázali jsme výše — dojdeme k samým nulám)

2) Může to být strom? Pro strom platí m = n - 1.

n = 8 (počet hodnot), m = (1+1+1+1+2+3+3+4)/2 = 16/2 = 8

m = n - 1? 8 = 8 - 1? 8 ≠ 7 ⇒ NE, nemůže to být skóre stromu

Cvičení 2 — Skóre stromu II: Může být (1,1,1,1,1,1,2,3,3,4) skóre stromu?

Je to skóre? ANO (ověřeno algoritmem).

n = 10, m = 18/2 = 9

m = n - 1? 9 = 10 - 1 = 9 ⇒ ANO, MŮŽE to být skóre stromu

Pozor: „může“ — existují i nestromy se stejným skóre!

Cvičení 3 — Les: Kolik komponent má les s 12 vrcholy a 8 hranami?

m = n - k ⇒ 8 = 12 - k ⇒ k = 4 komponenty

Cvičení 4 — Kód stromu: Ke kódu 00001011011011 nakreslete kořenový strom.

Čteme po znacích:

0 = kořen, 0 = syn, 0 = syn, 0 = syn, 1 = zpět, 0 = syn, 1 = zpět, 1 = zpět, 0 = syn, 1 = zpět, 1 = zpět, 0 = syn, 1 = zpět, 1 = zpět

    r
    |
    a
    |
    b
   / \
  c   d
  |
  e

(Přesná podoba záleží na konkrétní interpretaci — z kódu jasně vyplyne struktura)

Cvičení 5 — BVS a halda: Čísla 25, 1, 18, 5, 31, 14, 30, 31, 4, 40, 60 vložte do:
a) Binárního vyhledávacího stromu
b) Haldy (min-heap)
Pak z obou odeberte kořen.

a) BVS:

         25
        /    \
       1      31
        \    /  \
        18  30  31
       /          \
      5           40
     / \            \
    4  14           60

Odebrání kořene 25: nahradíme nejpravějším z levého podstromu (18) nebo nejlevějším z pravého (30).

b) Halda:

         1
       /    \
      4      14
     / \    /  \
    5  31  18  30
   / \  /
  31 25 40  60

Odebrání kořene 1: nahradíme posledním prvkem (60), pak probubláme dolů — swapujeme s menším synem, dokud není podmínka splněna.

Cvičení 6 — Procedury průchodu: Řešení výrazu (4*(8*1))+(((3-1)*5)/2) pomocí INORDER.

Strom výrazu viz příklad výše. Vyhodnotíme:

8 * 1 = 8, pak 4 * 8 = 32

3 - 1 = 2, pak 2 * 5 = 10, pak 10 / 2 = 5

32 + 5 = 37

Cvičení 7 — Počet hran: Strom s 10 vrcholy má kolik hran?

Strom s n vrcholy má vždy n - 1 hran. Pro n = 10: m = 10 - 1 = 9 hran.

Cvičení 8 — Insert do BVS: Jak funguje insert do BVS?

Porovnáváme: menší vlevo, větší vpravo, až najdeme volné místo. Nový prvek se vždy vkládá jako list.

Shrnutí

Klíčové pojmy a vztahy

Strom: souvislý acyklický graf
Počet hran: strom s n vrcholy má vždy n - 1 hran
Les: acyklický graf, m = n - k (k = počet komponent)
Kořenový strom: strom s vybraným kořenem — definuje předchůdce, následníky, vrstvy, hloubku
Kód stromu: 0 = nový syn, 1 = zpět k otci; minimální kód — lexikografické uspořádání potomků
BVS: levý podstrom ≤ vrchol ≤ pravý podstrom
Halda: otec ≤ synové, plnění po vrstvách zleva
Průchody: preorder (vrchol-levý-pravý), inorder (levý-vrchol-pravý), postorder (levý-pravý-vrchol)