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

Сложность поиска объекта в дереве

Сложность поиска в дереве зависит от типа дерева. Это один из важных аспектов выбора структуры данных.

Бинарное дерево поиска (BST) — O(log n) в среднем

Идеальный случай — сбалансированное дерево:

// Дерево с 7 элементами:
//           4
//         /   \
//        2     6
//       / \   / \
//      1   3 5   7

// Поиск элемента 5:
// Шаг 1: 5 > 4 → идём вправо
// Шаг 2: 5 < 6 → идём влево
// Шаг 3: 5 == 5 → найдено!
// Сложность: O(log 7) ≈ 3 операции

Код поиска:

public class BST<T extends Comparable<T>> {
    private Node root;
    
    private class Node {
        T value;
        Node left;
        Node right;
        
        Node(T value) {
            this.value = value;
        }
    }
    
    // Поиск — O(log n) при сбалансированном дереве
    public boolean search(T value) {
        return searchHelper(root, value);
    }
    
    private boolean searchHelper(Node node, T value) {
        if (node == null) {
            return false;  // Не найдено
        }
        
        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);  // Справа
        }
    }
}

Как работает O(log n):

Дерево с 1,000,000 элементов:
  Высота = log2(1,000,000) ≈ 20
  В худшем случае проверяем 20 элементов
  
  Уровень 1: 1 элемент
  Уровень 2: 2 элемента
  Уровень 3: 4 элемента
  ...
  Уровень 20: ~500,000 элементов
  
  Каждое сравнение исключает половину оставшихся элементов!

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

Если дерево вырождается в список:

// Несбалансированное дерево (как связный список!)
//        1
//         \
//          2
//           \
//            3
//             \
//              4
//               \
//                5

// Поиск элемента 5:
// Шаг 1: 5 > 1 → идём вправо
// Шаг 2: 5 > 2 → идём вправо
// Шаг 3: 5 > 3 → идём вправо
// Шаг 4: 5 > 4 → идём вправо
// Шаг 5: 5 == 5 → найдено!
// Сложность: O(n) = 5 операций!

Это может произойти, если вставлять отсортированные элементы:

BST<Integer> tree = new BST<>();
tree.insert(1);
tree.insert(2);
tree.insert(3);
tree.insert(4);
tree.insert(5);
// Результат: список, не дерево!
// Поиск: O(n)

Red-Black Tree (автобалансирующееся) — O(log n) ГАРАНТИРОВАННО

Red-Black Tree гарантирует O(log n):

// TreeSet и TreeMap в Java используют Red-Black Tree
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(10);
treeSet.add(5);
treeSet.add(15);
treeSet.add(3);

// contains() — O(log n) ВСЕГДА
boolean found = treeSet.contains(7);  // O(log n)

// Не зависит от порядка вставки!
// Дерево автоматически балансируется при insert/delete

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

Правила Red-Black Tree:
1. Каждый узел либо красный, либо чёрный
2. Корень всегда чёрный
3. Листья (NIL) чёрные
4. Если узел красный, его дети чёрные
5. Все пути от узла до листьев имеют одно количество чёрных узлов

Эти правила гарантируют:
  Max height = 2 * log(n+1)
  Поэтому O(log n) гарантирован!

Сравнение типов деревьев

Практические примеры из Java

TreeMap (Red-Black Tree):

Map<Integer, String> treeMap = new TreeMap<>();
treeMap.put(10, "ten");
treeMap.put(5, "five");
treeMap.put(15, "fifteen");

// Поиск — O(log n)
String value = treeMap.get(7);  // null, O(log n)

// Но если нужна O(1) поиск
Map<Integer, String> hashMap = new HashMap<>();
String value2 = hashMap.get(7); // O(1)

Навигация по TreeMap:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "ten");
map.put(5, "five");
map.put(15, "fifteen");

// Благодаря O(log n) структуре
// можем эффективно делать range операции

// Элементы от 5 до 15
SortedMap<Integer, String> range = map.subMap(5, 15);
// Сложность: O(log n + k), где k = размер результата

// Найти меньше 10
Integer floorKey = map.floorKey(10);  // O(log n)

// Найти больше 10
Integer ceilingKey = map.ceilingKey(10);  // O(log n)

Визуальное сравнение

Сбалансированное (O(log n)):

          10
        /    \
       5      15
      / \    /  \
     3   7 12   20
    /   / \      \    
   1   6   8     25
   
Высота: 4
Элементов: 9
Мах операции для поиска: 4

Несбалансированное (O(n)):

          1
           \
            2
             \
              3
               \
                ...
                 \
                  9

Высота: 9
Элементов: 9
Мах операции для поиска: 9

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

Используй TreeSet/TreeMap (O(log n)):

// Нужен отсортированный порядок
Set<String> users = new TreeSet<>();

// Нужны range запросы
Map<Date, Event> events = new TreeMap<>();
SortedMap<Date, Event> thisWeek = events.subMap(monday, sunday);

// Нужны floor/ceiling операции
navigableSet.floor(value);
navigableSet.ceiling(value);

Используй HashSet/HashMap (O(1)):

// Просто быстро проверить наличие
Set<String> activeUsers = new HashSet<>();
if (activeUsers.contains(userId)) { ... }  // O(1)

// Частые lookup операции
Map<Long, User> userCache = new HashMap<>();
User user = userCache.get(userId);  // O(1)

Практический бенчмарк

int size = 1_000_000;

// TreeSet
Set<Integer> treeSet = new TreeSet<>();
for (int i = 0; i < size; i++) treeSet.add(i);

long treeStart = System.nanoTime();
for (int i = 0; i < 100_000; i++) {
    treeSet.contains(i * 10);
}
long treeTime = System.nanoTime() - treeStart;

// HashSet
Set<Integer> hashSet = new HashSet<>();
for (int i = 0; i < size; i++) hashSet.add(i);

long hashStart = System.nanoTime();
for (int i = 0; i < 100_000; i++) {
    hashSet.contains(i * 10);
}
long hashTime = System.nanoTime() - hashStart;

System.out.println("TreeSet: " + treeTime/1_000_000 + "ms");
System.out.println("HashSet: " + hashTime/1_000_000 + "ms");
// TreeSet медленнее в ~10 раз

Итог

Сложность поиска в дереве:

• Несбалансированное BST: O(1) best, O(log n) average, O(n) worst
• Сбалансированное (Red-Black, AVL, B-Tree): O(log n) всегда
• Hash Table: O(1) average, O(n) worst

Java использует автобалансирующиеся деревья (Red-Black) в TreeSet/TreeMap, поэтому O(log n) гарантирован.