Как работи бинарното дърво?

Бинарното дърво е структура от данни във форма на дърво, където всеки възел има най-много два дъщерни възела: леви и десни.

Принципи на функциониране:

• Корен: Върховият възел на дървото.
• Възли: Съдържат данни и препратки към дъщерните възли.
• Листове: Възли без дъщерни възли.
• Връзки: Насочени от родителския възел към дъщерните.

Основни операции:

• Вмъкване: Нови възли се добавят на определено място в дървото, като се запазва неговата структура и правила (например, за двоично търсещо дърво: по-малките стойности наляво, по-големите надясно).
• Търсене: Обхождане на възлите за намиране на конкретен елемент. В двоичното търсещо дърво търсенето е ефективно благодарение на подредбата на данните.
• Изтриване: Изтриване на възел с пренареждане на структурата на дървото.
• Обхождане: Посещение на всички възли на дървото в определен ред:
  • Предварително (Pre-order): Корен, леви поддървета, десни поддървета.
  • Пост-ред (Post-order): Леви поддървета, десни поддървета, корен.
  • В-ред (In-order): Леви поддървета, корен, десни поддървета (дава сортиран списък с елементи).

Предимства:

• Ефективно търсене, вмъкване и изтриване (в балансирани дървета).
• Използва се за представяне на йерархични данни.

Пример за структура на възел в PHP:

<?php

class Node {
    public $data; // Данни на възела
    public $left; // Ляво поддърво
    public $right; // Дясно поддърво

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