Ako funguje binárne strom?

Binárne strom je dátová štruktúra vo forme stromu, kde každý uzol má najviac dva potomkov: ľavého a pravého.

Princípy fungovania:

• Koreň: Horný uzol stromu.
• Uzly: Obsahujú dáta a odkazy na potomkov.
• Listy: Uzly bez potomkov.
• Väzby: Smerované od rodičovského uzla k potomkom.

Hlavné operácie:

• Vkladanie: Nové uzly sa pridávajú na určené miesto v strome, zachovávajúc jeho štruktúru a pravidlá (napríklad, pre binárny vyhľadávací strom: menšie hodnoty vľavo, väčšie vpravo).
• Hľadanie: Prechádzanie uzlami za účelom nájdenia konkrétneho prvku. V binárnom vyhľadávacom strome je hľadanie efektívne vďaka zoradeniu dát.
• Vymazanie: Vymazanie uzla s prebudovaním štruktúry stromu.
• Prechádzanie: Návšteva všetkých uzlov stromu v určenom poradí:
  • Pre-order: Koreň, ľavé podstromy, pravé podstromy.
  • Post-order: Ľavé podstromy, pravé podstromy, koreň.
  • In-order: Ľavé podstromy, koreň, pravé podstromy (dáva zoradený zoznam prvkov).

Výhody:

• Efektívne hľadanie, vkladanie a vymazávanie (v vyvážených stromoch).
• Používa sa na reprezentáciu hierarchických dát.

Príklad štruktúry uzla v PHP:

<?php

class Node {
    public $data; // Dáta uzla
    public $left; // Ľavý potomok
    public $right; // Pravý potomok

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