Какая сложность поиска у бинарного дерева?

Сложность поиска в бинарном дереве поиска (BST)

Время поиска элемента в бинарном дереве поиска (Binary Search Tree) зависит от структуры дерева и составляет O(log n) в среднем случае и O(n) в худшем случае.

Идеальный случай — сбалансированное дерево: O(log n)

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

public class BinarySearchTree<T extends Comparable<T>> {
    private Node<T> root;
    
    // Поиск в сбалансированном дереве: O(log n)
    public boolean search(T value) {
        return searchHelper(root, value);
    }
    
    private boolean searchHelper(Node<T> node, T value) {
        if (node == null) return false;  // O(1)
        
        int cmp = value.compareTo(node.value);
        if (cmp == 0) return true;       // Найдено
        else if (cmp < 0) {
            return searchHelper(node.left, value);   // Ищем в левом поддереве
        } else {
            return searchHelper(node.right, value);  // Ищем в правом поддереве
        }
    }
}

// Пример:
//        50
//       /  \
//      30   70
//     / \   / \
//    20 40 60 80
//
// Поиск 20: 50 -> 30 -> 20 (3 шагов, log₂8 ≈ 3)

Худший случай — вырожденное дерево: O(n)

Если дерево несбалансировано (например, похоже на связный список), поиск может потребовать просмотра всех n элементов:

// Вырожденное дерево (несбалансированное)
//    1
//     \
//      2
//       \
//        3
//         \
//          4
//           \
//            5
// Поиск 5: 1 -> 2 -> 3 -> 4 -> 5 (5 шагов = O(n))

// Код, создающий вырожденное дерево
BST<Integer> tree = new BSTTree<>();
for (int i = 1; i <= 5; i++) {
    tree.insert(i);  // Каждое число больше предыдущего
}  // Результат: O(n) поиск

Таблица сложности в разных случаях

Операция      | Сбалансированное | Вырожденное
--------------+------------------+-----------
Поиск         | O(log n)         | O(n)
Вставка       | O(log n)         | O(n)
Удаление      | O(log n)         | O(n)
Минимум       | O(log n)         | O(n)
Максимум      | O(log n)         | O(n)

Самобалансирующиеся деревья

Для гарантии O(log n) используются самобалансирующиеся структуры:

AVL дерево:

// Автоматически балансируется при вставке/удалении
// Гарантирует O(log n) для всех операций
public class AVLTree<T extends Comparable<T>> {
    private Node<T> root;
    
    public void insert(T value) {
        root = insertHelper(root, value);
    }
    
    private Node<T> insertHelper(Node<T> node, T value) {
        if (node == null) return new Node<>(value);
        
        if (value.compareTo(node.value) < 0) {
            node.left = insertHelper(node.left, value);
        } else if (value.compareTo(node.value) > 0) {
            node.right = insertHelper(node.right, value);
        }
        
        // Балансировка дерева (ротации)
        return balance(node);
    }
}

Red-Black дерево:

// Используется в TreeMap, TreeSet
public class RedBlackTree<K extends Comparable<K>, V> {
    // Гарантирует O(log n) для всех операций
    // Менее строгая балансировка, чем AVL
}

Практическое применение

// TreeMap использует Red-Black дерево
Map<String, Integer> tree = new TreeMap<>();
tree.put("apple", 1);      // O(log n)
tree.put("banana", 2);     // O(log n)
tree.put("cherry", 3);     // O(log n)

Integer value = tree.get("apple");  // O(log n)
tree.remove("banana");              // O(log n)

// Сравнение с HashMap
Map<String, Integer> hash = new HashMap<>();
hash.put("apple", 1);      // O(1) в среднем
hash.put("banana", 2);     // O(1) в среднем
Integer v = hash.get("apple");  // O(1) в среднем

Как определить баланс дерева

// Проверка, является ли дерево сбалансированным
public boolean isBalanced(Node<Integer> root) {
    return checkBalance(root).isBalanced;
}

private Result checkBalance(Node<Integer> node) {
    if (node == null) return new Result(true, -1);
    
    Result left = checkBalance(node.left);
    if (!left.isBalanced) return new Result(false, 0);
    
    Result right = checkBalance(node.right);
    if (!right.isBalanced) return new Result(false, 0);
    
    int height = Math.max(left.height, right.height) + 1;
    boolean balanced = Math.abs(left.height - right.height) <= 1;
    
    return new Result(balanced, height);
}

class Result {
    boolean isBalanced;
    int height;
    Result(boolean isBalanced, int height) {
        this.isBalanced = isBalanced;
        this.height = height;
    }
}

Выводы

✅ Сбалансированное BST → O(log n) ❌ Вырожденное BST → O(n) ✅ Используй TreeMap/TreeSet для гарантированного O(log n) ✅ Если нужна максимальная скорость без порядка → HashMap O(1)

Выбор правильной структуры данных критичен для производительности приложения.