Объясните механизм работы структуры данных - бинарное дерево для быстрого поиска элементов.

Бинарное дерево поиска (Binary Search Tree, BST) — это структура данных, где каждый узел содержит ключ, а для каждого узла выполняется условие:

• Все ключи в левом поддереве меньше ключа узла.
• Все ключи в правом поддереве больше ключа узла.

Это упорядоченность позволяет быстро искать элементы, начиная с корня и переходя налево или направо в зависимости от сравнения ключа.

Механизм поиска:

1. Начинаем с корня дерева.
2. Сравниваем искомый ключ с ключом текущего узла.
3. Если ключ совпал — возвращаем узел.
4. Если искомый ключ меньше — переходим в левое поддерево.
5. Если больше — в правое поддерево.
6. Повторяем, пока не найдем элемент или не достигнем листа (элемента без детей).

В среднем поиск занимает O(log n) времени, если дерево сбалансировано.

Пример на Java:

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

class BST {
    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);
        else
            return search(root.right, key);
    }
}