Ответ
Это принципиально разные сущности: алгоритм vs структура данных.
| Аспект | Бинарный поиск (Binary Search) | Бинарное дерево поиска (Binary Search Tree, BST) |
|---|---|---|
| Сущность | Алгоритм поиска. | Динамическая структура данных. |
| Условие работы | Применяется к отсортированному массиву (или подобному контейнеру с произвольным доступом). | Структура строится по правилу: для любого узла X, все ключи в левом поддереве < ключа X < всех ключей в правом поддереве. |
| Сложность поиска | O(log n) (гарантировано, т.к. массив отсортирован). | В среднем O(log n), в худшем случае (вырождение в цепочку) O(n). |
| Вставка/Удаление | В массиве: O(n) (требуется сдвиг элементов). | В среднем O(log n), в худшем O(n). |
| Память | Компактное хранение в непрерывной области памяти. | Динамическое выделение памяти под узлы, накладные расходы на указатели. |
Пример кода для сравнения:
Бинарный поиск в массиве:
int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
Поиск в BST:
class Node { int key; Node left, right; }
Node searchBST(Node root, int target) {
if (root == null || root.key == target) return root;
return (target < root.key) ? searchBST(root.left, target)
: searchBST(root.right, target);
}