Что такое бинарное дерево поиска?

# Бинарное дерево поиска (Binary Search Tree, BST)

Бинарное дерево поиска — это фундаментальная структура данных, которая комбинирует эффективность поиска со структурой дерева.

Определение

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

Для каждого узла N:
  - Все значения в левом поддереве < значение N
  - Все значения в правом поддереве > значение N

Визуализация

       50
      /  \
    30    70
   /  \  /  \
  20  40 60  80

Свойства:
- 30 < 50 (левое поддерево)
- 70 > 50 (правое поддерево)
- 20 < 30, 40 > 30
- 60 < 70, 80 > 70

Реализация узла

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

Основные операции

1. Поиск (Search)

public class BinarySearchTree {
    private TreeNode root;
    
    // Рекурсивный поиск
    public boolean search(int value) {
        return searchHelper(root, value);
    }
    
    private boolean searchHelper(TreeNode node, int value) {
        // Базовый случай: узел не найден
        if (node == null) {
            return false;
        }
        
        // Нашли значение
        if (node.value == value) {
            return true;
        }
        
        // Ищем в левом поддереве (если value меньше)
        if (value < node.value) {
            return searchHelper(node.left, value);
        }
        
        // Ищем в правом поддереве (если value больше)
        return searchHelper(node.right, value);
    }
    
    // Итеративный поиск
    public boolean searchIterative(int value) {
        TreeNode current = root;
        
        while (current != null) {
            if (current.value == value) {
                return true;
            } else if (value < current.value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        
        return false;
    }
}

Сложность: O(log n) в среднем, O(n) в худшем случае (разбалансированное дерево)

2. Вставка (Insert)

public void insert(int value) {
    root = insertHelper(root, value);
}

private TreeNode insertHelper(TreeNode node, int value) {
    // Пустое место для вставки
    if (node == null) {
        return new TreeNode(value);
    }
    
    // Не вставляем дубликаты
    if (value == node.value) {
        return node;
    }
    
    // Вставляем в левое поддерево
    if (value < node.value) {
        node.left = insertHelper(node.left, value);
    }
    // Вставляем в правое поддерево
    else {
        node.right = insertHelper(node.right, value);
    }
    
    return node;
}

Пример вставки:

Вставляем: 50, 30, 70, 20, 40, 60, 80

После 50:
    50

После 30 (30 < 50, влево):
    50
   /
  30

После 70 (70 > 50, вправо):
    50
   /  \
  30   70

После 20 (20 < 50 → 20 < 30 → влево):
    50
   /  \
  30   70
 /
20

3. Удаление (Delete)

Это самая сложная операция с тремя случаями:

public void delete(int value) {
    root = deleteHelper(root, value);
}

private TreeNode deleteHelper(TreeNode 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 {
        // Нашли узел для удаления
        
        // Случай 1: Листовой узел (нет детей)
        if (node.left == null && node.right == null) {
            return null;
        }
        
        // Случай 2: Один ребёнок
        if (node.left == null) {
            return node.right;
        }
        if (node.right == null) {
            return node.left;
        }
        
        // Случай 3: Два ребёнка
        // Найдём минимальное значение в правом поддереве (inorder successor)
        TreeNode minRight = findMin(node.right);
        node.value = minRight.value;
        node.right = deleteHelper(node.right, minRight.value);
    }
    
    return node;
}

private TreeNode findMin(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

Пример удаления узла с двумя детьми:

Удаляем 30 (имеет двух детей):

До:
    50
   /  \
  30   70
 /  \
20  40

Находим successor (минимум в правом поддереве = 40)
Заменяем значение 30 на 40
Удаляем узел с 40 из правого поддерева

После:
    50
   /  \
  40   70
 /
20

Обход дерева

// In-order (левое → узел → правое) - ОТСОРТИРОВАНО!
public void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    System.out.print(node.value + " ");
    inOrder(node.right);
}

// Pre-order (узел → левое → правое)
public void preOrder(TreeNode node) {
    if (node == null) return;
    System.out.print(node.value + " ");
    preOrder(node.left);
    preOrder(node.right);
}

// Post-order (левое → правое → узел)
public void postOrder(TreeNode node) {
    if (node == null) return;
    postOrder(node.left);
    postOrder(node.right);
    System.out.print(node.value + " ");
}

// Level-order (BFS)
public void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.value + " ");
        
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

Пример обхода дерева:

Дерево:
       50
      /  \
    30    70
   /  \  /  \
  20  40 60  80

In-order:    20, 30, 40, 50, 60, 70, 80 (ОТСОРТИРОВАНО!)
Pre-order:   50, 30, 20, 40, 70, 60, 80
Post-order:  20, 40, 30, 60, 80, 70, 50
Level-order: 50, 30, 70, 20, 40, 60, 80

Полная реализация

public class BinarySearchTree {
    private TreeNode root;
    
    public void insert(int value) {
        root = insertHelper(root, value);
    }
    
    public boolean search(int value) {
        return searchHelper(root, value);
    }
    
    public void delete(int value) {
        root = deleteHelper(root, value);
    }
    
    public void inOrderTraversal() {
        inOrder(root);
        System.out.println();
    }
    
    // ... все методы выше
    
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        
        // Вставляем элементы
        bst.insert(50);
        bst.insert(30);
        bst.insert(70);
        bst.insert(20);
        bst.insert(40);
        bst.insert(60);
        bst.insert(80);
        
        // Поиск
        System.out.println("Поиск 40: " + bst.search(40)); // true
        System.out.println("Поиск 100: " + bst.search(100)); // false
        
        // Обход
        System.out.print("In-order: ");
        bst.inOrderTraversal(); // 20, 30, 40, 50, 60, 70, 80
        
        // Удаление
        bst.delete(30);
        System.out.print("После удаления 30: ");
        bst.inOrderTraversal(); // 20, 40, 50, 60, 70, 80
    }
}

Сложность операций

Когда дерево разбалансировано?

Хорошее (сбалансированное):
       50        высота = 3
      /  \
    30    70
   /  \  /  \
  20  40 60  80

Плохое (разбалансированное):
    10
      \
       20
         \
          30      высота = 10
            \
             40
               \
                50
                  \
                   ...

Преимущества и недостатки

Преимущества:

• Быстрый поиск (в среднем O(log n))
• Автоматически отсортированы (in-order обход)
• Эффективнее, чем отсортированный массив для вставки/удаления

Недостатки:

• Может разбалансироваться (худший случай O(n))
• Требует больше памяти (указатели на детей)
• Неявный порядок элементов

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

• Часто вставляем/удаляем элементы с поиском
• Нужны отсортированные данные
• Требуется O(log n) средний случай

Для гарантии O(log n) в худшем случае используйте AVL дерево или Red-Black дерево.

Вывод

Бинарное дерево поиска — это мощная структура данных, комбинирующая быстрый поиск с гибкой вставкой/удалением. Это основа для более сложных структур, таких как AVL деревья и Red-Black деревья, используемые в TreeMap и TreeSet в Java.