Какие методы используеются для сортировки внутри TreeSet?

Механизм сортировки в TreeSet

TreeSet — это отсортированная коллекция, которая использует красно-чёрное дерево (Red-Black Tree) для хранения элементов в отсортированном порядке. Понимание механизма сортировки критично для правильного использования этой коллекции.

Основной принцип работы

TreeSet использует красно-чёрное дерево, где сортировка осуществляется во время вставки и удаления элементов. Для определения позиции каждого элемента используется сравнение.

Способ 1: Comparator (предпочтительный)

Передаём Comparator при создании TreeSet:

// Сортировка по естественному порядку (для Comparable)
TreeSet<String> set1 = new TreeSet<>();
set1.add("banana");
set1.add("apple");
set1.add("cherry");
System.out.println(set1); // [apple, banana, cherry]

// Кастомная сортировка через Comparator
TreeSet<String> set2 = new TreeSet<>((a, b) -> {
    // Обратный порядок
    return b.compareTo(a);
});
set2.addAll(set1);
System.out.println(set2); // [cherry, banana, apple]

Примеры кастомных Comparator'ов:

// 1. Сортировка по длине строки
TreeSet<String> byLength = new TreeSet<>((a, b) -> {
    int lenCompare = Integer.compare(a.length(), b.length());
    if (lenCompare != 0) return lenCompare;
    return a.compareTo(b); // Тай-брейкер
});

// 2. Сортировка объектов по нескольким полям
TreeSet<Person> people = new TreeSet<>((p1, p2) -> {
    int nameCompare = p1.getName().compareTo(p2.getName());
    if (nameCompare != 0) return nameCompare;
    return Integer.compare(p1.getAge(), p2.getAge());
});

// 3. Числовая сортировка с кастомной логикой
TreeSet<Integer> byAbsValue = new TreeSet<>((a, b) -> 
    Integer.compare(Math.abs(a), Math.abs(b))
);
byAbsValue.addAll(Arrays.asList(-5, 3, -2, 8, 1));
System.out.println(byAbsValue); // [-2, 1, 3, -5, 8]

Способ 2: Comparable (элемент сортирует сам себя)

Элемент реализует интерфейс Comparable:

public class Person implements Comparable<Person> {
    private String name;
    private int age;
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public int compareTo(Person other) {
        // Сравниваем по имени, потом по возрасту
        int nameCompare = this.name.compareTo(other.name);
        if (nameCompare != 0) return nameCompare;
        return Integer.compare(this.age, other.age);
    }
}

// Использование
TreeSet<Person> people = new TreeSet<>();
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 25));
people.add(new Person("Alice", 25));

people.forEach(p -> System.out.println(p.getName() + " " + p.getAge()));
// Вывод:
// Alice 25
// Alice 30
// Bob 25

Внутренний механизм работы TreeSet

TreeSet использует красно-чёрное дерево с методом compareTo() для поиска и вставки:

public class TreeSetInternals {
    public static void demonstrate() {
        TreeSet<Integer> set = new TreeSet<>();
        
        // Внутри происходит что-то вроде этого:
        // 1. Вставляем 50
        set.add(50);  // Становится корень
        
        // 2. Вставляем 30
        set.add(30);  // compareTo: 30 < 50, идём влево
        
        // 3. Вставляем 70
        set.add(70);  // compareTo: 70 > 50, идём вправо
        
        // 4. Вставляем 20
        set.add(20);  // compareTo: 20 < 50, 20 < 30, идём влево от 30
        
        // 5. Вставляем 40
        set.add(40);  // compareTo: 40 < 50, 40 > 30, идём вправо от 30
        
        // Дерево сбалансировано автоматически (красно-чёрное дерево)
        // Гарантирует O(log n) для добавления, удаления, поиска
        
        System.out.println(set); // [20, 30, 40, 50, 70]
    }
}

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

TreeSet<Integer> set = new TreeSet<>();

// Все эти операции O(log n):
set.add(5);           // O(log n) - проходит по дереву для вставки
set.remove(5);        // O(log n) - находит элемент и удаляет
set.contains(5);      // O(log n) - ищет элемент в дереве
set.first();          // O(log n) - находит минимум
set.last();           // O(log n) - находит максимум
set.floor(5);         // O(log n) - наибольший элемент <= 5
set.ceiling(5);       // O(log n) - наименьший элемент >= 5
set.lower(5);         // O(log n) - наибольший элемент < 5
set.higher(5);        // O(log n) - наименьший элемент > 5
set.headSet(5);       // O(log n) - элементы < 5
set.tailSet(5);       // O(log n) - элементы >= 5
set.subSet(3, 7);     // O(log n) - элементы от 3 до 7

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

Пример 1: Сортировка по убыванию

TreeSet<Integer> descending = new TreeSet<>(Collections.reverseOrder());
descending.addAll(Arrays.asList(5, 2, 8, 1, 9));
System.out.println(descending); // [9, 8, 5, 2, 1]

Пример 2: Уникальные элементы в отсортированном порядке

List<Integer> numbers = Arrays.asList(5, 2, 8, 2, 1, 5, 9);
TreeSet<Integer> unique = new TreeSet<>(numbers);
System.out.println(unique); // [1, 2, 5, 8, 9]

Пример 3: Диапазонные запросы

TreeSet<Integer> set = new TreeSet<>(Arrays.asList(1, 3, 5, 7, 9, 11, 13));

// Элементы от 5 до 10 (5 включительно, 10 исключительно)
NavigableSet<Integer> range = set.subSet(5, false, 10, true);
System.out.println(range); // [5, 7, 9]

// Все элементы меньше 8
System.out.println(set.headSet(8)); // [1, 3, 5, 7]

// Все элементы больше или равны 7
System.out.println(set.tailSet(7)); // [7, 9, 11, 13]

Пример 4: Сортировка объектов со сложной логикой

public class Event implements Comparable<Event> {
    private LocalDateTime time;
    private String name;
    private int priority; // Высший приоритет первым
    
    @Override
    public int compareTo(Event other) {
        // Сначала по приоритету (убывающий)
        int priorityCompare = Integer.compare(other.priority, this.priority);
        if (priorityCompare != 0) return priorityCompare;
        
        // Потом по времени (возрастающий)
        int timeCompare = this.time.compareTo(other.time);
        if (timeCompare != 0) return timeCompare;
        
        // Потом по названию
        return this.name.compareTo(other.name);
    }
}

TreeSet<Event> events = new TreeSet<>();
events.add(new Event("Task B", LocalDateTime.now(), 1));
events.add(new Event("Task A", LocalDateTime.now(), 3));
events.add(new Event("Task C", LocalDateTime.now(), 2));

// Будут отсортированы по приоритету: Task A (3), Task C (2), Task B (1)

Важные особенности

// 1. null не допускается
TreeSet<String> set = new TreeSet<>();
set.add(null); // NullPointerException

// 2. Если compareTo() возвращает 0, элемент считается дубликатом
TreeSet<String> set = new TreeSet<>((a, b) -> 1); // Всегда a > b
set.add("apple");
set.add("banana");
set.add("cherry");
System.out.println(set.size()); // 3 - все добавлены

TreeSet<String> set2 = new TreeSet<>((a, b) -> 0); // Всегда a == b
set2.add("apple");
set2.add("banana");
set2.add("cherry");
System.out.println(set2.size()); // 1 - остался только первый

// 3. Inconsistent with equals() может привести к проблемам
class Bad implements Comparable<Bad> {
    int id;
    
    @Override
    public int compareTo(Bad other) {
        return Integer.compare(this.id, other.id); // По ID
    }
    
    @Override
    public boolean equals(Object o) {
        // Но equals() может сравнивать по другому
        return this == o;
    }
}

Резюме

TreeSet использует два способа сортировки:

1. Comparator — передаётся при создании, имеет приоритет
2. Comparable — реализуется в классе элемента

Оба способа основаны на методе compareTo(), который вызывается при каждой вставке/удалении для поддержания отсортированного порядка в красно-чёрном дереве. Это гарантирует O(log n) для основных операций.