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

Бинарное дерево – это структура данных, где каждый узел имеет максимум 2 потомка:
Левый потомок содержит меньшие значения.
Правый потомок содержит большие значения.

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

Каждый узел состоит из:
Значения (value) – данные в узле.
Ссылки на левый (left) и правый (right) потомки (или null, если потомка нет).

       8
      / \
     3   10
    / \    \
   1   6    14
      / \   /
     4   7 13

🚩Основные операции с бинарным деревом

🟠Вставка нового элемента
Если дерево пустое → создаём корневой узел.
Сравниваем значение с корнем:
- Если меньше → идём налево.
- Если больше → идём направо.
Повторяем, пока не найдём свободное место.

       8
      / \
     3   10
    / \    
   1   6  
      / \  
     4   7  
    /
   5  <-- новый элемент добавляется слева от 6

Код вставки в PHP

class Node {
    public int $value;
    public ?Node $left = null;
    public ?Node $right = null;

    public function __construct(int $value) {
        $this->value = $value;
    }
}

class BinaryTree {
    public ?Node $root = null;

    public function insert(int $value) {
        $this->root = $this->insertRec($this->root, $value);
    }

    private function insertRec(?Node $node, int $value): Node {
        if ($node === null) return new Node($value);
        if ($value < $node->value) $node->left = $this->insertRec($node->left, $value);
        else $node->right = $this->insertRec($node->right, $value);
        return $node;
    }
}

$tree = new BinaryTree();
$tree->insert(8);
$tree->insert(3);
$tree->insert(10);
$tree->insert(6);
$tree->insert(14);

🟠Поиск элемента в дереве
Алгоритм:
Начинаем с корня.
Если value == корень → найдено.
Если value < корень → ищем влево.
Если value > корень → ищем вправо.

1. 6 < 8 → идём влево к 3.
2. 6 > 3 → идём вправо к 6.
3. Нашли!

public function search(?Node $node, int $value): ?Node {
    if ($node === null || $node->value === $value) return $node;
    return ($value < $node->value)
        ? $this->search($node->left, $value)
        : $this->search($node->right, $value);
}

$foundNode = $tree->search($tree->root, 6);
echo $foundNode ? "Найдено: " . $foundNode->value : "Не найдено";

🟠Удаление элемента из дерева
Сложность:
1. Если узел – лист → просто удаляем.
2. Если у узла один потомок → заменяем его потомком.
3. Если два потомка → находим минимальный элемент в правом поддереве и заменяем им удаляемый узел.

Пример удаления 3 (у него есть два потомка 1 и 6):
1. Находим минимальный узел в правом поддереве → 4.
2. Заменяем 3 на 4.

       8
      / \
     3   10
    / \    
   1   6  
      / \  
     4   7  

После удаления 3

       8
      / \
     4   10
    / \    
   1   6  
      / \  
     5   7

Ставь 👍 и забирай 📚 Базу знаний