Деревья: бинарное дерево поиска — туториал

Бинарное дерево поиска (BST, Binary Search Tree) — одна из базовых структур данных в IT. Его часто спрашивают на собеседованиях, используют в алгоритмах и изучают как фундамент для понимания более сложных деревьев: AVL, Red-Black Tree, B-Tree.

Что такое бинарное дерево поиска

Это дерево, где у каждого узла не более двух потомков:

• левый содержит значения меньше текущего узла
• правый содержит значения больше текущего узла

Пример:

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

Такое правило позволяет быстро искать элементы без полного перебора массива.

Основные операции в BST 🔎

• Поиск: сравниваем значение с текущим узлом и идём влево или вправо
• Вставка: ищем подходящее пустое место по тому же правилу
• Удаление: самая сложная операция, зависит от числа потомков у узла

Сложность операций

В среднем:

• поиск — O(log n)
• вставка — O(log n)
• удаление — O(log n)

В худшем случае, если дерево “выродилось” в список:

• поиск / вставка / удаление — O(n) ⚠️

Это происходит, например, если вставлять данные по возрастанию: 1, 2, 3, 4, 5.

Как работает поиск

• Ищем число 6:
• 6 < 8 → идём влево
• 6 > 3 → идём вправо
• нашли 6 ✅

Как работает вставка

• Добавим 5:
• 5 < 8 → влево
• 5 > 3 → вправо
• 5 < 6 → влево
• 5 > 4 → вправо
• пусто → вставляем

Удаление узла 🧩

Есть 3 случая:

• нет потомков → просто удаляем
• один потомок → “поднимаем” потомка на место узла
• два потомка → заменяем узел на следующий по порядку элемент (минимум в правом поддереве)

Почему BST важны

• развивают алгоритмическое мышление
• помогают понять рекурсию и обходы дерева
• лежат в основе сбалансированных деревьев и индексов

Обходы дерева

Самый популярный для BST — in-order:

• левое поддерево
• текущий узел
• правое поддерево

Для BST такой обход выводит элементы по возрастанию 📈

Когда использовать BST

• подходит, если нужно хранить данные в отсортированном виде
• быстро искать, вставлять и удалять
• делать range query — например, получить все значения в диапазоне

Главный минус

Обычный BST не гарантирует баланс. Поэтому на практике часто используют сбалансированные варианты, где сохраняется хорошая скорость даже на больших объёмах данных ⚙️

Итог: бинарное дерево поиска — это фундаментальная структура данных, которую важно понимать каждому разработчику, особенно для собеседований, алгоритмов и backend-задач.

👀 Ниже стоит посмотреть подборку каналов про IT — там ещё больше полезных разборов, практики и материалов для роста.

🗣 Подборки каналов
🧠 Каталог ботов и приложений
🗺 Навигация