Binární strom

Binární strom

Binární strom je datová struktura složená z uzlů, kde každý uzel může mít maximálně dva potomky: levý a pravý. Každý uzel obsahuje hodnotu a ukazatele na své potomky.

Typy binárních stromů

1. Plný binární strom - každý uzel má buď žádné, nebo právě dva potomky.

2. Dokonalý binární strom - všechny listy jsou na stejné úrovni a každý rodič má dva potomky.

3. Vyvážený binární strom - rozdíl mezi hloubkami levého a pravého podstromu každého uzlu je maximálně jedna.

4. Binární vyhledávací strom - levý potomek obsahuje menší hodnoty než rodič, pravý potomek větší (nebo rovny).

Operace nad binárním vyhledávacím stromem

• Vložení uzlu – nový prvek se vloží na správné místo

• Vyhledání uzlu – hledáme, zda je ve stromu daná hodnota

• Odstranění uzlu

• Průchody stromem – preorder, inorder, postorder

• Hledání minima a maxima – minimum je nejlevější uzel, maximum nejpravější.

Kde se binární stromy využívají?

1. Vyhledávání dat – Binární vyhledávací stromy umožňují efektivní vyhledávání s časovou složitostí O(log n).

2. Zpracování dat – Používá se např. v parserech programovacích jazyků.

3. Kompresi dat – Huffmanovo kódování využívá binární stromy ke kompresi souborů.

4. Databázové indexy – B-stromy, vycházející z binárních stromů, se používají k efektivnímu indexování dat.

5. Umělá inteligence – Herní strom pro hledání optimální strategie.

6. Sítě a grafika – Hierarchické struktury v renderingu a organizaci scén.

Implementace binárního vyhledávacího stromu v C++

Vytvořte program v jazyce C++, který bude pracovat s binárním vyhledávacím stromem. Každý uzel stromu bude reprezentován strukturou obsahující:

• hodnotu celého čísla (int),

• ukazatel na levého potomka,

• ukazatel na pravého potomka.

Funkce

1. Vytvoření nové struktury uzlu

   • Definujte strukturu Node, která bude obsahovat hodnotu a ukazatele na levého a pravého potomka.

2. Vytvoření nového uzlu (Node* createNode(int value))

   • Implementujte funkci pro vytvoření nového uzlu.

3. Vkládání hodnoty do stromu (void insert(int value))

   • Implementujte funkci, která přidá nový uzel na správné místo podle pravidel binárního vyhledávacího stromu (menší hodnoty vlevo, větší vpravo).

4. Výpis hodnot ve stromu (inorder průchod) (void inorderTraversal(Node* node))

   • Implementujte funkci, která vypíše hodnoty ve stromu vzestupně.

5. Vyhledávání hodnoty ve stromu (bool search(int value))

   • Implementujte funkci, která zjistí, zda daná hodnota ve stromu existuje.

6. Odstranění uzlu (Node* deleteNode(Node* node, int value))

   • Implementujte funkci pro odstranění uzlu ze stromu se třemi případy:

     • Uzly bez potomků (přímo smažte).

     • Uzly s jedním potomkem (nahraďte potomkem).

     • Uzly se dvěma potomky (nahraďte nejmenší hodnotou z pravého podstromu).

Bonusové úkoly:

1. Implementujte funkci pro nalezení minimální a maximální hodnoty ve stromu.

2. Implementujte funkci pro určení výšky stromu.

3. Implementujte funkci pro iterativní vkládání prvků bez rekurze.