Какими основными свойствами обладает бинарное дерево поиска (Binary Search Tree — BST)?

Бинарное дерево поиска (BST) — это упорядоченная древовидная структура данных со следующими ключевыми свойствами:

1. Структурное свойство:

• Каждый узел имеет не более двух потомков: левого и правого.

2. Свойство упорядоченности (главное свойство):

• Для любого узла X:
  • Все значения в левом поддереве узла X меньше значения самого узла X.
  • Все значения в правом поддереве узла X больше или равны значению узла X (зависит от реализации, допускающей дубликаты).
• Это свойство должно выполняться рекурсивно для всех поддеревьев.

3. Следствия свойств (операции):

• Поиск, вставка, удаление в сбалансированном BST выполняются в среднем за O(log n), где n — количество узлов.
• Обход inorder (левый-узел-правый) посещает узлы в отсортированном порядке.

Визуализация и пример кода:

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

Пример реализации поиска в BST на Java:

class Node {
    int key;
    Node left, right;
    public Node(int item) { key = item; }
}

public class BinarySearchTree {
    Node root;

    // Рекурсивный поиск ключа
    Node search(Node root, int key) {
        // Базовый случай: узел пуст или ключ найден
        if (root == null || root.key == key) {
            return root;
        }
        // Ключ меньше значения корня -> ищем в левом поддереве
        if (key < root.key) {
            return search(root.left, key);
        }
        // Ключ больше -> ищем в правом поддереве
        return search(root.right, key);
    }
}

Важное предупреждение о производительности: В худшем случае (например, когда элементы добавляются в отсортированном порядке: 1, 2, 3, 4...), дерево вырождается в связный список, и сложность операций падает до O(n). Для гарантированной логарифмической сложности используются самобалансирующиеся деревья (AVL, Красно-черные).