Junior
Čo je binárne strom?
sobes.tech AI
Odpoveď od AI
Binárne strom je dátová štruktúra v tvare stromu, kde každý uzol má najviac dvoch potomkov: ľavého a pravého.
Hlavné vlastnosti:
- Koreň (Root): Najvyšší uzol stromu.
- Uzel (Node): Prvok stromu obsahujúci dáta a odkazy na jeho potomkov.
- Dieťa (Child): Uzol, ktorý sa nachádza priamo pod iným uzlom (rodičom).
- Rodič (Parent): Uzol, ktorý má priamo pod sebou jedného alebo viac potomkov.
- List (Leaf): Uzol bez potomkov.
- Väzba (Branch): Cesta od koreňa k listu.
- Podstrom (Subtree): Strom pozostávajúci z uzla a všetkých jeho potomkov.
Druhy binárnych stromov:
- Plný binárny strom (Full Binary Tree): Každý uzol má buď 0 alebo 2 potomkov.
- Dokonalý binárny strom (Perfect Binary Tree): Všetky úrovne okrem poslednej sú úplne zaplnené, a na poslednej úrovni sú všetky uzly čo najviac vľavo.
- Vyvážený binárny strom (Balanced Binary Tree): Výška ľavého a pravého podstromu akéhokoľvek uzla sa líši najviac o 1. Príklad: AVL strom, červená-čierna strom.
- Degenerovaný (rozpínavý) binárny strom (Degenerate Binary Tree): Každý uzol má najviac jedného potomka. V podstate je to prepojený zoznam.
Používa sa v rôznych algoritmoch a dátových štruktúrach, ako sú binárne vyhľadávacie stromy, haldy, syntaktické stromy.