Kako funkcioniše binarno stablo?

Binarsko drvo je struktura podataka u obliku stabla, gde svaki čvor ima najviše dva potomka: levog i desnog.

Principi funkcionisanja:

• Korenski čvor: Gornji čvor stabla.
• Čvorovi: Sadrže podatke i reference na potomke.
• Listovi: Čvorovi bez potomaka.
• Veze: Usmerene od roditeljskog čvora ka potomcima.

Glavne operacije:

• Ubacivanje: Novi čvorovi se dodaju na određeno mesto u stablu, čuvajući njegovu strukturu i pravila (npr., za binarno pretraživačko stablo: manje vrednosti levo, veće desno).
• Pretraživanje: Prolazak kroz čvorove radi pronalaženja određenog elementa. U binarnom pretraživačkom stablu, pretraživanje je efikasno zahvaljujući redosledu podataka.
• Brisanje: Brisanje čvora sa preuređenjem strukture stabla.
• Obilazak: Poseta svim čvorovima stabla u određenom redosledu:
  • Pre-order: Korenski, levno podstablo, desno podstablo.
  • Post-order: Levo podstablo, desno podstablo, koren.
  • In-order: Levo podstablo, koren, desno podstablo (daje sortiranu listu elemenata).

Prednosti:

• Efikasno pretraživanje, ubacivanje i brisanje (u uravnoteženim stablima).
• Koristi se za prikazivanje hijerarhijskih podataka.

Primer strukture čvora u PHP-u:

<?php

class Node {
    public $data; // Podaci čvora
    public $left; // Levi potomek
    public $right; // Desni potomek

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