Что такое двоичное дерево поиска (Binary Search Tree, BST)

Двоичное дерево поиска (BST) — это древовидная структура данных на основе узлов, где каждый узел имеет не более двух дочерних элементов (левого и правого потомка).

Главное его предназначение — быстрый поиск, вставка и удаление элементов.

Ключевые свойства

Для любого узла N в дереве должны выполняться следующие условия:

1. Все значения в левом поддереве узла N меньше, чем значение в N.
2. Все значения в правом поддереве узла N больше, чем значение в N.
3. Оба — левое и правое — поддеревья также являются двоичными деревьями поиска.

Производительность

Благодаря этим свойствам, операции поиска, вставки и удаления в сбалансированном дереве выполняются в среднем за логарифмическое время O(log n).

• Средний случай: O(log n)
• Худший случай: O(n). Происходит, когда дерево вырождается в связный список (например, при последовательной вставке отсортированных элементов).

Пример реализации на Python

# Класс для представления узла дерева
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

# Функция для поиска значения в дереве
def search(root, key):
    # Базовые случаи: корень пуст или ключ найден
    if root is None or root.val == key:
        return root

    # Ключ больше значения в корне -> ищем в правом поддереве
    if root.val < key:
        return search(root.right, key)

    # Ключ меньше значения в корне -> ищем в левом поддереве
    return search(root.left, key)

Для решения проблемы худшего случая используют самобалансирующиеся деревья, такие как АВЛ-деревья или Красно-чёрные деревья.