В чем разница между видами деревьев?

# Разница между видами деревьев (Binary Tree, BST, AVL, Red-Black Tree)

Контекст для Java разработчика

В контексте Java и структур данных (особенно TreeMap и TreeSet), речь идёт о сбалансированных деревьях поиска. Разберём основные типы:

1. Бинарное дерево поиска (BST — Binary Search Tree)

Определение:

• Каждый узел имеет не более 2 детей (левый и правый)
• Левое поддерево содержит значения < родителя
• Правое поддерево содержит значения > родителя

Структура:

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

Временные сложности:

• Поиск: O(log n) в среднем, O(n) в худшем (несбалансированное дерево)
• Вставка: O(log n) в среднем, O(n) в худшем
• Удаление: O(log n) в среднем, O(n) в худшем

Проблема:

// Вырождение в список!
BST tree = new BST();
tree.insert(1);
tree.insert(2);
tree.insert(3);
tree.insert(4);
// Результат — прямая линия, O(n) для поиска!
       1
        \
         2
          \
           3
            \
             4

2. AVL-дерево (Adelson-Velski-Landis)

Определение:

• Самобалансирующееся BST
• Поддерживает баланс высот поддеревьев
• Высота левого и правого поддеревьев отличается не более чем на 1

Balance Factor:

balanceFactor = height(left) - height(right)
// Допустимые значения: -1, 0, 1

Ротации при дисбалансе:

// Left rotation (правое дерево тяжелее)
    z                y
   / \              / \
  T1  y    -->    z   T4
      / \        / \
    T2  T3      T1  T2

// Right rotation (левое дерево тяжелее)
      z           y
     / \        / \
    y   T4  -> T1  z
   / \          / \
  T1  T2       T2  T3

Временные сложности:

• Поиск: O(log n) гарантирован
• Вставка: O(log n) с ротациями
• Удаление: O(log n) с ротациями
• Пространство: O(n) + O(log n) для хранения высот

Пример:

      10
     /  \
    5    15
   / \   / \
  2   7 12  20

// Дерево сбалансировано, height(left) - height(right) всегда в [-1, 1]

3. Красно-чёрное дерево (Red-Black Tree)

Определение:

• Самобалансирующееся BST, используется в TreeMap и TreeSet
• Каждый узел окрашен в красный или чёрный цвет
• Свойства:
  1. Корень чёрный
  2. Листья (NIL) чёрные
  3. Красный узел имеет только чёрных детей
  4. Все пути от узла к листьям содержат одинаковое количество чёрных узлов

Структура (упрощённо):

       [10]B
      /     \
   [5]R      [15]B
   / \       /   \
 [2]B [7]B [12]B [20]R

Временные сложности:

• Поиск: O(log n) гарантирован
• Вставка: O(log n) с ротациями и перекрашиванием
• Удаление: O(log n) с ротациями и перекрашиванием
• Пространство: O(n) + бит для цвета

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

• Меньше ротаций (AVL более строгий баланс требует больше ротаций)
• Лучше для частых вставок/удалений
• Используется в TreeMap, TreeSet, HashMap (для коллизий в Java 8+)

4. B-дерево (используется в БД)

Заметка: В Java обычно не используется прямо, но важно знать для общего развития.

• Каждый узел может содержать более 2 детей
• Все листья на одном уровне (идеально сбалансировано)
• Используется в файловых системах и БД

Временные сложности:

• Поиск: O(log n)
• Вставка: O(log n)
• Удаление: O(log n)

Использование в Java

TreeSet и TreeMap — Red-Black Tree

// Внутри используется красно-чёрное дерево
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(10);  // O(log n) и автоматическая балансировка
treeSet.add(5);
treeSet.add(15);

Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Alice", 25);  // O(log n)
treeMap.put("Bob", 30);

// Порядок сортировки
for (Integer num : treeSet) {
    System.out.println(num); // 5, 10, 15
}

// Поиск по диапазону
Set<Integer> subSet = treeSet.subSet(5, 15); // [5, 10)

HashMap — Red-Black Tree для коллизий (Java 8+)

// В Java 8+ при много коллизий в одной ячейке
// цепочка преобразуется в красно-чёрное дерево
// Это улучшает поиск с O(n) до O(log n)

Map<String, String> hashMap = new HashMap<>();
hashMap.put("key1", "value1");
hashMap.put("key2", "value2");
// Внутренняя структура: массив + цепочки (Node) или деревья (TreeNode)

Сравнительная таблица

Практический пример

public class TreeComparison {
    public static void main(String[] args) {
        // Red-Black Tree (TreeSet)
        Set<Integer> sorted = new TreeSet<>();
        long start = System.nanoTime();
        for (int i = 0; i < 1_000_000; i++) {
            sorted.add((int)(Math.random() * Integer.MAX_VALUE));
        }
        long treeTime = System.nanoTime() - start;
        
        // Hash Table (HashSet) — для сравнения
        Set<Integer> hashed = new HashSet<>();
        start = System.nanoTime();
        for (int i = 0; i < 1_000_000; i++) {
            hashed.add((int)(Math.random() * Integer.MAX_VALUE));
        }
        long hashTime = System.nanoTime() - start;
        
        System.out.println("TreeSet time: " + treeTime / 1_000_000 + "ms");
        System.out.println("HashSet time: " + hashTime / 1_000_000 + "ms");
        // HashSet обычно быстрее (O(1) vs O(log n))
        // Но TreeSet сохраняет сортировку
    }
}

Ключевые выводы

1. BST — базовая структура, может вырождаться в список
2. AVL — очень строгая балансировка, много ротаций
3. Red-Black Tree — оптимальный выбор для Java, используется в TreeMap/TreeSet
4. Выбор:
   • Нужна сортировка? → TreeSet/TreeMap (Red-Black)
   • Нужна максимальная скорость? → HashSet/HashMap
   • Нужен частый поиск без вставок? → BST или AVL
5. В Java обычно не нужно реализовывать деревья вручную — используй стандартные коллекции