STUDIJNÍ TEXT (Teorie)
V minulé lekci jsme řešili grafy, kde byly občas nějaké cykly. Dnes se podíváme na speciální, „čistý“ typ grafu, který je základem pro organizaci dat v počítači i evoluci v přírodě.
1. Co je to Strom (Tree)?
Strom je graf, který je souvislý a nemá žádné cykly.
Představte si rodokmen nebo organizační strukturu firmy. Cesta z bodu A do bodu B je vždy jen jedna. Nemůžete „obejít“ někde kolem přes C.
Hlavní znaky stromu:
- Kořen (Root): Hlavní uzel, ze kterého vše začíná (např. složka C:\ je „společný předek“ složek „Dokumenty“ a „Hudba“, nebo „LUCA“ strom – last universal common ancestor, vědecký pojem pro posledního univerzálního společného předka všech organismů na Zemi).
- Listy (Leaves): Uzly na konci větví, které nemají žádné další potomky (koncové soubory ve složkách, nebo např. strom života a dnes žijící druhy ve vazbě na „LUCA“).
- Rodič & Potomek (Parent & Child): Hierarchický vztah (nadřízený → podřízený).
Obr. 1: Ukázka stromového grafu s popisem uzlů a vztahů.
2. Měření ve stromu (Metriky)
V grafu můžeme měřit vzdálenosti, což je užitečné pro chemiky, biology, informatiky a další.
- Vzdálenost (Distance): Počet hran (čar), které musíme projít na cestě z jednoho uzlu do druhého.
- V biologii: Čím větší vzdálenost ve stromu života, tím méně jsou si druhy příbuzné.
- Hloubka stromu (Depth/Height): Počet pater od kořene k nejvzdálenějšímu listu.
Obr. 2: Ukázka stromového grafu s vyznačením hloubky stromu a vzdálenosti mezi kořenem a listem 1.
3. Binární stromy a síla rozhodování
V informatice jsou klíčové Binární stromy, kde má každý uzel maximálně dva potomky (levý a pravý) viz obr. 1 a obr. 2.
Proč? Protože to umožňuje neuvěřitelně rychlé hledání.
- Lineární hledání: Hledáte jméno v seznamu jedno po druhém.
U milionu jmen to trvá dlouho. - Binární hledání (půlení): Seřadíte jména. Otevřete seznam uprostřed. Je jméno v první, nebo ve druhé polovině?
- V první polovině? → Zahodíte celou druhou polovinu.
- Zbyde vám jen polovina. Znovu ji rozpůlíte.
- Tímto způsobem najdete cokoliv v milionu položek na pouhých 20 dotazů!
(220 ≈ 1 000 000)
