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

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

1. Все элементы левого поддерева меньше значения узла
2. Все элементы правого поддерева больше значения узла

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

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

class Node {
    int value;
    Node left, right;
    
    Node(int value) { 
        this.value = value; 
        left = right = null; 
    }
}

Пример дерева:

      8
    /   \
   3     10
  / \     \
 1   6     14

Средняя сложность операций — O(log n), но в худшем случае (вырожденное дерево) — O(n). Для балансировки используют AVL-деревья или красно-чёрные деревья.