В чем разница между бинарным поиском и двоичным деревом поиска

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

Ключевые различия:

1. Структура: бинарный поиск работает с массивами, BST — с узлами (нодами).
2. Вставка/удаление: в массиве O(n), в BST — O(log n) (в среднем).
3. Память: массив использует непрерывную память, BST — динамическую.

Пример BST:

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

// Поиск в BST
Node search(Node root, int key) {
    if (root == null || root.key == key) return root;
    return (key < root.key) ? search(root.left, key) : search(root.right, key);
}