Jak funguje 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.

Principy fungování:

• Kořen: Horní uzel stromu.
• Uzel: Obsahuje data a odkazy na potomky.
• Listy: Uzel bez potomků.
• Vazby: Směřují od rodičovského uzlu k potomkům.

Hlavní operace:

• Vložení: Nové uzly jsou přidávány na určité místo ve stromu, zachovávají jeho strukturu a pravidla (například, pro binární vyhledávací strom: menší hodnoty vlevo, větší vpravo).
• Hledání: Procházení uzlů za účelem nalezení konkrétního prvku. V binárním vyhledávacím stromu je hledání efektivní díky řazení dat.
• Odstranění: Odstranění uzlu s přestavbou struktury stromu.
• Procházení: Návštěva všech uzlů stromu v určitém pořadí:
  • Pre-order: Kořen, levý podstrom, pravý podstrom.
  • Post-order: Levý podstrom, pravý podstrom, kořen.
  • In-order: Levý podstrom, kořen, pravý podstrom (dává seřazený seznam prvků).

Výhody:

• Efektivní hledání, vkládání a odstraňování (v vyvážených stromech).
• Používá se k reprezentaci hierarchických dat.

Příklad struktury uzlu v PHP:

<?php

class Node {
    public $data; // Data uzlu
    public $left; // Levý potomek
    public $right; // Pravý potomek

    public function __construct($data) {
        $this->data = $data;
        $this->left = null;
        $this->right = null;
    }
}