Co je to binární strom?

Binární strom je datová struktura ve tvaru stromu, kde každý uzel má nejvýše dva potomky: levého a pravého.

Hlavní vlastnosti:

• Kořen (Root): Nejvyšší uzel stromu.
• Uzel (Node): Prvek stromu obsahující data a odkazy na jeho potomky.
• Potomek (Child): Uzl, který se nachází přímo pod jiným uzlem (rodičem).
• Rodič (Parent): Uzl, který má přímo pod sebou jedno nebo více potomků.
• List (Leaf): Uzl bez potomků.
• Větve (Branch): Cesta od kořene ke listu.
• Podstrom (Subtree): Strom složený z uzlu a všech jeho potomků.

Různé typy binárních stromů:

• Plný binární strom (Full Binary Tree): Každý uzel má buď 0 nebo 2 potomky.
• Dokonalý binární strom (Perfect Binary Tree): Všechny úrovně kromě poslední jsou plně zaplněny a na poslední úrovni jsou všechny uzly co nejvíce vlevo.
• Vyvážený binární strom (Balanced Binary Tree): Výška levého a pravého podstromu libovolného uzlu se liší nejvýše o 1. Příklad: AVL strom, červená-černá strom.
• Degenerovaný (rozpínavý) binární strom (Degenerate Binary Tree): Každý uzel má nejvýše jednoho potomka. V podstatě je to spojový seznam.

Používá se v různých algoritmech a datových strukturách, například v binárních vyhledávacích stromech, haldách, syntaktických stromech.