← Zpět na obsah

Kapitola 13: Pokročilé struktury – Vektory a Stromy

▶ Sledovat video lekci QR kód video lekce

Doposud jsme pracovali se seznamy, které jsou jako dlouhá nitka korálků. Ale svět není plochý. Svět je 3D prostor, hierarchie a vztahy. Soubory ve vašem počítači jsou organizovány ve stromech (složky ve složkách). Rodokmeny jsou stromy. Hry se odehrávají v prostoru se souřadnicemi. Prolog umí tyto složité struktury reprezentovat velmi elegantně a přirozeně.

Binární strom
Obrázek 13.1: Binární strom. Kořen je nahoře, menší čísla vlevo, větší vpravo.

13.1 Vektory a Souřadnice – Balíme data do krabiček

Vektory nebo body v prostoru v Prologu reprezentujeme pomocí struktur. Už jsme se s nimi setkali (např. kniha(...)). Teď je použijeme pro geometrii. Bod ve 2D prostoru můžeme zapsat jako bod(X, Y).

STRUKTURA (STRUCTURE) Složený term, který má jméno (funktor) a obsahuje další termy (argumenty). Umožňuje nám seskupit související data dohromady.

Příklad: Je úsečka vodorovná?
Úsečka je definována dvěma body. Je vodorovná, pokud mají oba body stejnou souřadnici Y.

% usecka(Bod1, Bod2)
vodorovna(usecka(bod(X1, Y), bod(X2, Y))).

Všimněte si kouzla unifikace. Použili jsme proměnnou Y na obou místech. Tím jsme Prologu řekli: "Nezajímá mě, jaká je to hodnota, ale musí být na obou místech stejná."

13.2 Binární stromy – Rozděl a hledej

Stromy jsou základem efektivního vyhledávání. Představte si Binární vyhledávací strom (BST). Má jeden kořen a dvě větve. Pravidlo je jednoduché: Všechno, co je menší než kořen, jde doleva. Všechno, co je větší, jde doprava.

BINÁRNÍ STROM (BINARY TREE) Datová struktura, kde každý uzel má nanejvýš dva potomky: levý a pravý podstrom.

V Prologu strom zapíšeme jako strukturu: strom(Hodnota, LevyPodstrom, PravyPodstrom). Prázdný strom (list) označíme jako nil.

% Strom z obrázku:
strom(5,
    strom(3, nil, nil),  % Vlevo je 3
    strom(8, nil, nil)   % Vpravo je 8
).
Infografika ke kapitole 13

Řešené příklady: Hledání v lese dat

Příklad 13.1: Hledání v BST
Díky pravidlu "menší vlevo, větší vpravo" najdeme cokoliv bleskově rychle. Nemusíme prohledávat celý strom, v každém kroku zahodíme polovinu možností!

% 1. Našli jsme to! Hodnota v uzlu je to, co hledáme.
najdi(X, strom(X, _, _)).

% 2. Hledané X je menší než kořen -> Jdi doleva.
najdi(X, strom(Koren, Levy, _)) :-
    X < Koren,
    najdi(X, Levy).

% 3. Hledané X je větší než kořen -> Jdi doprava.
najdi(X, strom(Koren, _, Pravy)) :-
    X > Koren,
    najdi(X, Pravy).

Klíčový koncept: Pattern Matching (Vzory)

Prolog je geniální v tom, jak umí rozebrat složité struktury přímo v hlavičce pravidla. Místo abychom psali "Vezmi první argument, zkontroluj jestli je to bod...", prostě napíšeme vzor bod(X, Y) a Prolog se postará o zbytek. Tomu se říká Pattern Matching.

Otázky k zamyšlení

  1. Jak by vypadal strom, který reprezentuje matematický výraz (2 + 3) * 4? (Kořen je násobení, vlevo je sčítání...).
  2. Proč je hledání v binárním stromu rychlejší než v seznamu? Představte si telefonní seznam seřazený podle jmen vs. náhodnou hromadu vizitek.
  3. Nakreslete na papír strom, který odpovídá zápisu: t(a, t(b, nil, nil), t(c, nil, nil)).

🧪 Laboratoř: Stavíme a počítáme

← Zpět na obsah