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

Бинарное дерево — это иерархическая структура данных, в которой каждый узел (node) имеет не более двух потомков: левого и правого ребенка. Это фундаментальная структура, лежащая в основе многих эффективных алгоритмов.

Основные компоненты:

• Корень (Root): Самый верхний узел, от которого начинается дерево.
• Узел (Node): Элемент дерева, хранящий данные (ключ/значение) и ссылки на потомков.
• Лист (Leaf): Узел, не имеющий потомков.
• Поддерево (Subtree): Любой узел вместе со всеми его потомками.

Базовая реализация на PHP:

class BinaryNode {
    public $data;
    public $left;
    public $right;

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

// Создание простого дерева
$root = new BinaryNode(10);
$root->left = new BinaryNode(5);
$root->right = new BinaryNode(15);
$root->left->left = new BinaryNode(2);
$root->right->right = new BinaryNode(20);

Основные виды обхода (traversal):

1. In-order (центрированный): Левый потомок -> Узел -> Правый потомок. Для бинарного дерева поиска (BST) выводит узлы в отсортированном порядке.
2. Pre-order (прямой): Узел -> Левый потомок -> Правый потомок. Полезен для копирования структуры дерева.
3. Post-order (обратный): Левый потомок -> Правый потомок -> Узел. Используется для удаления дерева или вычисления выражений.

Пример in-order обхода:

function inOrderTraversal(?BinaryNode $node) {
    if ($node === null) return;

    inOrderTraversal($node->left); // Рекурсивно идем влево
    echo $node->data . " ";        // Обрабатываем текущий узел
    inOrderTraversal($node->right); // Рекурсивно идем вправо
}

inOrderTraversal($root); // Вывод: 2 5 10 15 20

Применение:

• Бинарные деревья поиска (BST): Для быстрого поиска, вставки и удаления элементов (в среднем O(log n)).
• Кучи (Heaps): Для реализации эффективных очередей с приоритетом и алгоритма Heapsort.
• Синтаксические деревья: Используются компиляторами и интерпретаторами для представления структуры кода.
• Деревья решений: В машинном обучении и алгоритмах классификации.

Важное замечание: Произвольное бинарное дерево может выродиться в связный список (когда каждый узел имеет только одного потомка), что ухудшит сложность операций до O(n). Для поддержания эффективности используются сбалансированные деревья (AVL, Красно-черные), которые автоматически регулируют свою структуру.