🌳 Бинарное дерево поиска (BST) — кладём числа «как в огороде

🌳 Бинарное дерево поиска (BST) — кладём числа «как в огороде»

Садовник‑самурай сортирует бамбуковые палки по длине. Он втыкает первую палку в землю — это центр грядки. Любая короче идёт влево, длиннее — вправо. Для каждой новой палки правило повторяется: слева короче, справа длиннее. Через минуту получилась «живая диаграмма», в которой нужную длину легко найти. Вот это и есть бинарное дерево поиска.

Как оно работает на пальцах

1. Первый элемент — «корень».

2. Всё, что меньше, кладём слева; больше — справа.

3. Для любой «ветки» правило то же самое.

Так грядка растёт в ширину и глубину, а не в одну длинную цепочку. Поэтому поиск «есть ли палка 42 см?» занимает в среднем log₂(n) шагов, а не n, как при простом переборе.

Мини‑глоссарий

• Корень — первая палка.

• Ветвь/узел — любая палка с возможными «детьми» слева/справа.

• Лист — палка без детей.

Пример кода на PHP

// вставка в BST

function insert(?array &$tree, int $value): void {

if ($tree === null) { // пустое место — сажаем палку

$tree = ['v'=>$value,'l'=>null,'r'=>null];

return;

}

$branch = ($value < $tree['v']) ? 'l' : 'r';

insert($tree[$branch], $value); // рекурсивно дальше

}

Идея та же для поиска: идём влево или вправо, пока не найдём или не упремся в пустоту.

Плюсы

• Быстрый поиск/вставка при «хорошем» дереве — O(log n).

• Данные автоматически держатся упорядоченно.

Минусы

• Если вставлять уже отсортированные данные, дерево перекосится и станет медленным (O(n)).

• Нужно следить за балансировкой или брать готовые «самобалансирующиеся» варианты (AVL, Red‑Black).

Когда брать BST

✅ Нужно хранить и искать по числовому ключу.

✅ Хотите быстро выводить данные по возрастанию.

🚫 Приходят данные уже отсортированные — лучше хеш‑таблица или сбалансированное дерево.

Вопрос к читателям: встречали ли вы ситуацию, когда поиск «бинаркой» спас проект? Расскажите в комментах!

#алгоритмы #BST #кодСамурая