Cum funcționează un arbore binar?

Un copac binar este o structură de date în formă de copac, unde fiecare nod are cel mult două noduri fiice: stânga și dreapta.

Principii de funcționare:

• Rădăcină: Nodul superior al copacului.
• Noduri: Conțin date și referințe către nodurile fiice.
• Frunze: Noduri fără noduri fiice.
• Legături: Direcționate de la nodul părinte către nodurile fiice.

Operații principale:

• Inserare: Nodurile noi sunt adăugate într-un anumit loc în copac, păstrând structura și regulile sale (de exemplu, pentru un copac binar de căutare: valori mai mici la stânga, valori mai mari la dreapta).
• Căutare: Traversarea nodurilor pentru a găsi un element specific. Într-un copac binar de căutare, căutarea este eficientă datorită ordonării datelor.
• Ștergere: Ștergerea unui nod cu reestructurarea structurii copacului.
• Parcurgere: Vizitarea tuturor nodurilor copacului într-o anumită ordine:
  • Pre-ordine: Rădăcină, sub-arsenal stâng, sub-arsenal drept.
  • Post-ordine: Sub-arsenal stâng, sub-arsenal drept, rădăcină.
  • In-ordine: Sub-arsenal stâng, rădăcină, sub-arsenal drept (pentru un copac binar de căutare, oferă o listă sortată de elemente).

Avantaje:

• Căutare, inserare și ștergere eficiente (în copaci echilibrați).
• Este folosit pentru a reprezenta date ierarhice.

Exemplu de structură a unui nod în PHP:

<?php

class Node {
    public $data; // Datele nodului
    public $left; // Nod fiu stâng
    public $right; // Nod fiu drept

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