====== Binární strom ======

**Binární strom** je nelineární datová struktura, ve které je každý prvek (uzel) spojen s nejvýše dvěma dalšími uzly, které označujeme jako **levý syn** a **pravý syn**. 

Tato struktura se používá pro efektivní vyhledávání, třídění dat, reprezentaci hierarchií nebo při kompresi dat (např. Huffmanovo kódování).

----

====== Základní terminologie ======

Abychom pochopili práci se stromy, musíme definovat jejich části:
  * **Kořen (Root):** Nejvyšší uzel stromu, od kterého vše začíná. Nemá žádného rodiče.
  * **Uzel (Node):** Prvek stromu obsahující data a ukazatele na své potomky.
  * **List (Leaf):** Uzel, který nemá žádné potomky (nachází se na úplném konci větve).
  * **Větev (Edge):** Spojnice mezi dvěma uzly.
  * **Hloubka (Výška):** Počet úrovní od kořene k nejvzdálenějšímu listu.



----

====== Typy binárních stromů ======

V praxi se setkáváme s různými variantami podle toho, jak jsou uzly uspořádány:

^ Typ ^ Charakteristika ^
| **Plný binární strom** | Každý uzel má buď 0, nebo 2 potomky (nikdy jen jednoho). |
| **Vyvážený strom** | Rozdíl výšek levého a pravého podstromu každého uzlu je minimální. Zajišťuje rychlé operace. |
| **Binární vyhledávací strom (BST)** | Pro každý uzel platí: všechny hodnoty v levém podstromu jsou menší a v pravém větší než hodnota uzlu. |

----

====== Binární vyhledávací strom (BST) ======

**BST** (Binary Search Tree) je nejpoužívanější formou binárního stromu díky své efektivitě při vyhledávání.

===== Jak funguje vyhledávání v BST: =====
Představte si, že hledáte číslo **15**:
  1. Začnete u kořene (např. číslo **20**).
  2. Protože 15 < 20, jdete do **levého** podstromu.
  3. Narazíte na uzel s hodnotou **10**.
  4. Protože 15 > 10, jdete do **pravého** podstromu.
  5. Narazíte na uzel **15** – prvek nalezen.

Díky tomuto principu se při každém kroku eliminujeme polovinu zbývajících dat (podobně jako u binárního vyhledávání v poli).



----

====== Průchod stromem (Traversal) ======

Abychom mohli se všemi daty ve stromu pracovat (např. je vypsat), musíme stromem "projít". Existují tři hlavní způsoby:
  * **In-order (Levý-Kořen-Pravý):** U BST vypíše data seřazená od nejmenšího po největší.
  * **Pre-order (Kořen-Levý-Pravý):** Vhodné pro kopírování stromu.
  * **Post-order (Levý-Pravý-Kořen):** Používá se například při mazání stromu (nejdříve se mažou potomci, pak rodič).

----

====== Výhody a nevýhody ======

**Výhody:**
  * **Rychlost:** Vyhledávání, vkládání a mazání je u vyvážených stromů velmi rychlé (logaritmická složitost).
  * **Flexibilita:** Strom se může dynamicky zvětšovat a zmenšovat.

**Nevýhody:**
  * **Degenerace:** Pokud vkládáme data již seřazená (1, 2, 3, 4...), strom se může změnit v "čáru" (seznam), čímž ztrácí svou rychlost. To řeší tzv. **samovyvažující se stromy** (např. AVL nebo Red-Black stromy).

----
//Související pojmy: B-strom, Indexování, Databáze, Algoritmus, Rekurze, Huffmanovo kódování.//