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

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

Это две разные концепции в информатике, часто путаемые из-за слова "бинарный"/"двоичный". Давайте разберёмся, что это такое и чем они отличаются.

Бинарный поиск (Binary Search) — алгоритм поиска

Бинарный поиск — это алгоритм поиска элемента в отсортированном массиве путём многократного деления массива пополам.

Как это работает:

1. Выбираем средний элемент массива
2. Если он равен искомому — нашли!
3. Если искомый больше — ищем в правой половине
4. Если искомый меньше — ищем в левой половине
5. Повторяем, пока не найдём или массив не закончится

Характеристики:

• Временная сложность: O(log n)
• Требование: массив должен быть отсортирован
• Что хранится: элементы в отсортированном массиве
• Структура данных: массив или список
• Динамические операции: вставка/удаление — медленно

Пример реализации:

public class BinarySearch {
  public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
      int mid = left + (right - left) / 2;
      
      if (arr[mid] == target) {
        return mid;  // Найден
      } else if (arr[mid] < target) {
        left = mid + 1;  // Ищем в правой половине
      } else {
        right = mid - 1;  // Ищем в левой половине
      }
    }
    
    return -1;  // Не найден
  }
  
  public static void main(String[] args) {
    int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    System.out.println(binarySearch(arr, 7));   // 3
    System.out.println(binarySearch(arr, 100)); // -1
  }
}

Двоичное дерево поиска (Binary Search Tree, BST) — структура данных

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

Характеристики:

• Временная сложность (в среднем): O(log n) для поиска, вставки, удаления
• Временная сложность (в худшем случае): O(n) если дерево несбалансировано
• Структура: дерево (граф без циклов)
• Динамические операции: вставка/удаление — быстро
• Требование: отсортированность не требуется для входных данных

Свойство BST:

       5
      / \
     3   7
    / \ / \
   2  4 6  8

Для узла 5:
- Левое поддерево (3, 2, 4) — все < 5
- Правое поддерево (7, 6, 8) — все > 5

Пример реализации:

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

public class BinarySearchTree {
  private Node root;
  
  // Поиск элемента
  public boolean search(int value) {
    return searchHelper(root, value);
  }
  
  private boolean searchHelper(Node node, int value) {
    if (node == null) {
      return false;
    }
    
    if (value == node.value) {
      return true;
    } else if (value < node.value) {
      return searchHelper(node.left, value);
    } else {
      return searchHelper(node.right, value);
    }
  }
  
  // Вставка элемента
  public void insert(int value) {
    root = insertHelper(root, value);
  }
  
  private Node insertHelper(Node node, int value) {
    if (node == null) {
      return new Node(value);
    }
    
    if (value < node.value) {
      node.left = insertHelper(node.left, value);
    } else if (value > node.value) {
      node.right = insertHelper(node.right, value);
    }
    
    return node;
  }
  
  // Удаление элемента
  public void delete(int value) {
    root = deleteHelper(root, value);
  }
  
  private Node deleteHelper(Node node, int value) {
    if (node == null) {
      return null;
    }
    
    if (value < node.value) {
      node.left = deleteHelper(node.left, value);
    } else if (value > node.value) {
      node.right = deleteHelper(node.right, value);
    } else {
      // Узел с одним потомком или без них
      if (node.left == null) {
        return node.right;
      } else if (node.right == null) {
        return node.left;
      }
      
      // Узел с двумя потомками
      Node minRightSubtree = findMin(node.right);
      node.value = minRightSubtree.value;
      node.right = deleteHelper(node.right, minRightSubtree.value);
    }
    
    return node;
  }
  
  private Node findMin(Node node) {
    while (node.left != null) {
      node = node.left;
    }
    return node;
  }
}

Прямое сравнение

Когда использовать

Бинарный поиск:

• Когда данные уже отсортированы в массиве
• Когда нужны только операции поиска
• Когда дополнительная память не критична
• Когда данные не меняются часто
• Пример: поиск в словаре, поиск по диапазону дат

Двоичное дерево поиска:

• Когда нужны частые вставки и удаления
• Когда требуется динамически обновляемое отсортированное хранилище
• Когда нужна быстрая работа со всеми тремя операциями (поиск, вставка, удаление)
• Пример: реализация приоритетной очереди, индексирование в БД, кэши

Улучшенные варианты BST

Для гарантии O(log n) даже в худшем случае используют сбалансированные деревья:

• AVL дерево — автоматически балансируется при вставке/удалении
• Red-Black дерево — менее строгая балансировка, но проще в реализации
• B-дерево — для дисковых структур данных

Вывод: бинарный поиск — это алгоритм для массивов, двоичное дерево поиска — это структура данных для динамических коллекций. Обе решают задачу быстрого поиска, но применяются в разных контекстах.