Какие знаешь деревья в TreeSet?

Деревья в TreeSet: Red-Black Trees

TreeSet — это реализация интерфейса NavigableSet, основанная на структуре данных Red-Black Tree (красно-чёрное дерево). Это сбалансированное двоичное дерево поиска, гарантирующее логарифмическую сложность операций.

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

Red-Black Tree — это двоичное дерево поиска с дополнительными свойствами для автоматической балансировки.

Свойства Red-Black Tree:

1. Каждый узел окрашен либо в красный, либо в чёрный цвет
2. Корень всегда чёрный
3. Все листья (NIL) — чёрные
4. Красный узел не может иметь красного родителя (нет двух красных подряд)
5. Каждый путь от узла до листа содержит одинаковое количество чёрных узлов

Эти свойства гарантируют, что высота дерева O(log n).

// Структура узла Red-Black Tree (внутренняя)
class RBNode<T> {
    T value;
    RBNode<T> left;
    RBNode<T> right;
    RBNode<T> parent;
    Color color; // RED или BLACK
}

enum Color {
    RED,
    BLACK
}

TreeSet в Java

TreeSet автоматически использует Red-Black Tree для хранения элементов в отсортированном виде.

// Создание TreeSet
TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(3);
numbers.add(7);
numbers.add(1);

// Все операции выполняются за O(log n)
System.out.println(numbers); // [1, 3, 5, 7] — всегда отсортировано

// Поиск
boolean contains = numbers.contains(3); // O(log n)

// Удаление
numbers.remove(5); // O(log n)

// Размер
int size = numbers.size(); // O(1)

Операции TreeSet и их сложность

TreeSet<String> words = new TreeSet<>();
words.addAll(Arrays.asList("zebra", "apple", "mango", "banana"));

// O(log n) операции
words.add("cherry");           // Вставка с балансировкой
words.remove("apple");         // Удаление с балансировкой
boolean exists = words.contains("mango"); // Поиск

// O(1) операции
int size = words.size();
boolean isEmpty = words.isEmpty();

// Навигация — уникально для TreeSet
String first = words.first();   // "apple"
String last = words.last();     // "zebra"
String floor = words.floor("cherry");    // Наибольший элемент <= "cherry" → "banana"
String ceiling = words.ceiling("cherry"); // Наименьший элемент >= "cherry" → "cherry"
String lower = words.lower("cherry");    // Элемент < "cherry" → "banana"
String higher = words.higher("cherry");  // Элемент > "cherry" → "mango"

// Диапазонные операции — очень мощны
Set<String> subSet = words.subSet("apple", "mango"); // [apple, banana, cherry)
Set<String> headSet = words.headSet("cherry");       // [apple, banana]
Set<String> tailSet = words.tailSet("cherry");       // [cherry, mango, zebra]

// Итерация в порядке сортировки
for (String word : words) {
    System.out.println(word); // apple, banana, cherry, mango, zebra
}

// Итерация в обратном порядке
for (String word : words.descendingSet()) {
    System.out.println(word); // zebra, mango, cherry, banana, apple
}

Сравниватели в TreeSet

TreeSet использует Comparator (или natural order) для определения порядка элементов.

// Естественный порядок (сортировка по возрастанию)
TreeSet<Integer> ascending = new TreeSet<>();
ascending.addAll(Arrays.asList(5, 3, 7, 1));
System.out.println(ascending); // [1, 3, 5, 7]

// Кастомный компаратор (сортировка по убыванию)
TreeSet<Integer> descending = new TreeSet<>(
    (a, b) -> Integer.compare(b, a)
);
descending.addAll(Arrays.asList(5, 3, 7, 1));
System.out.println(descending); // [7, 5, 3, 1]

// Сортировка объектов
class Employee implements Comparable<Employee> {
    private int id;
    private String name;
    private double salary;
    
    @Override
    public int compareTo(Employee other) {
        return Integer.compare(this.id, other.id);
    }
}

TreeSet<Employee> employees = new TreeSet<>();
employees.add(new Employee(3, "Alice", 50000));
employees.add(new Employee(1, "Bob", 60000));
employees.add(new Employee(2, "Charlie", 55000));
// Всегда хранится отсортировано по ID

// Сортировка по зарплате вместо ID
TreeSet<Employee> bysalary = new TreeSet<>(
    Comparator.comparingDouble(Employee::getSalary)
);
bysal ary.addAll(employees);

Балансировка в Red-Black Tree

При вставке/удалении дерево может потерять свои свойства. Java автоматически выполняет ротации и перекраску.

// Пример: вставка нарушает свойство дерева
TreeSet<Integer> tree = new TreeSet<>();
tree.add(10);      // 10 (чёрный, корень)
tree.add(5);       // 5 (красный)
tree.add(15);      // 15 (красный) — нарушение: два красных подряд
// Java автоматически перебалансирует дерево

// Эта же операция в HashMap (кстати, тоже использует красно-чёрное дерево в buckets)
Map<Integer, String> map = new HashMap<>();
map.put(10, "ten");
map.put(5, "five");
map.put(15, "fifteen");

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

Пример 1: Поиск элемента в отсортированном диапазоне

TreeSet<Integer> scores = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50));

// Все оценки от 20 до 40
Set<Integer> rangeScores = scores.subSet(20, 41);
System.out.println(rangeScores); // [20, 30, 40]

// Оценки ниже 40
Set<Integer> belowForty = scores.headSet(40);
System.out.println(belowForty); // [10, 20, 30]

Пример 2: Поиск медианы в потоке данных

class MedianFinder {
    private TreeSet<Integer> all = new TreeSet<>();
    
    public void addNumber(int num) {
        all.add(num);
    }
    
    public double findMedian() {
        int size = all.size();
        if (size % 2 == 1) {
            // Нечётное количество
            int mid = size / 2;
            return all.stream().skip(mid).findFirst().orElse(0);
        } else {
            // Чётное количество
            int mid = size / 2;
            int lower = all.stream().skip(mid - 1).findFirst().orElse(0);
            int upper = all.stream().skip(mid).findFirst().orElse(0);
            return (lower + upper) / 2.0;
        }
    }
}

Пример 3: Отслеживание уникальных отсортированных значений

TreeSet<String> uniqueEvents = new TreeSet<>();

// Добавляем события
unique Events.add("login");
unique Events.add("logout");
unique Events.add("login");   // Дублирование
unique Events.add("error");

// Получаем в отсортированном виде без дубликатов
unique Events.forEach(System.out::println); // error, login, logout

TreeSet vs HashMap vs ArrayList

*amortized, **если вставлять в конец

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

• Нужны элементы в отсортированном порядке
• Нужны операции диапазона (subSet, headSet, tailSet)
• Нужно найти closest element (floor, ceiling, lower, higher)
• Нужны быстрые вставка/удаление с гарантией сортировки

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

• Только нужна быстрая вставка/удаление без сортировки → HashSet
• Нужна быстрая индексация → ArrayList
• Данные очень большие (много памяти) → HashSet

Вывод: Red-Black Tree в TreeSet — это идеальный баланс между быстротой операций (O(log n)) и гарантией отсортированности. Это одна из самых элегантных структур данных в информатике.