Какие объекты можно добавлять в TreeSet

# Какие объекты можно добавлять в TreeSet

TreeSet имеет строгие требования к объектам, которые в него добавляются. Это связано с тем, что TreeSet хранит элементы в упорядоченном виде.

Основное правило

В TreeSet можно добавлять только те объекты, которые реализуют интерфейс Comparable ИЛИ передан Comparator в конструктор.

Требования к объектам

1. Реализация Comparable

Объект должен реализовать интерфейс Comparable<T> и метод compareTo():

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

// Теперь можно добавлять в TreeSet
TreeSet<Person> people = new TreeSet<>();
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 25));
people.add(new Person("Charlie", 35));

// Хранятся в порядке: Bob(25), Alice(30), Charlie(35)

2. Встроенные классы, реализующие Comparable

Много классов в Java уже реализуют Comparable:

// Integer, Long, Double, BigDecimal - реализуют Comparable
TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(2);
numbers.add(8);
numbers.add(1);
System.out.println(numbers);  // [1, 2, 5, 8] - отсортировано

// String - реализует Comparable (лексикографический порядок)
TreeSet<String> words = new TreeSet<>();
words.add("zebra");
words.add("apple");
words.add("banana");
System.out.println(words);  // [apple, banana, zebra]

// Date, LocalDate, LocalDateTime - реализуют Comparable
TreeSet<LocalDate> dates = new TreeSet<>();
dates.add(LocalDate.of(2025, 1, 1));
dates.add(LocalDate.of(2023, 6, 15));
dates.add(LocalDate.of(2024, 12, 25));
System.out.println(dates);  // [2023-06-15, 2024-12-25, 2025-01-01]

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

Если объект не реализует Comparable, можно передать Comparator в конструктор:

public class Student {
    private String name;
    private double gpa;
    
    public Student(String name, double gpa) {
        this.name = name;
        this.gpa = gpa;
    }
    
    public String getName() { return name; }
    public double getGpa() { return gpa; }
}

// Student НЕ реализует Comparable
// Но можно использовать Comparator

// Вариант 1: Comparator в конструктор
TreeSet<Student> byGpa = new TreeSet<>(
    (s1, s2) -> Double.compare(s2.getGpa(), s1.getGpa())  // По убыванию GPA
);
byGpa.add(new Student("Alice", 3.9));
byGpa.add(new Student("Bob", 3.5));
byGpa.add(new Student("Charlie", 3.8));
// Хранятся в порядке: Alice(3.9), Charlie(3.8), Bob(3.5)

// Вариант 2: Явный Comparator класс
class StudentComparatorByName implements Comparator<Student> {
    @Override
    public int compare(Student s1, Student s2) {
        return s1.getName().compareTo(s2.getName());
    }
}

TreeSet<Student> byName = new TreeSet<>(new StudentComparatorByName());
byName.add(new Student("Alice", 3.9));
byName.add(new Student("Bob", 3.5));
byName.add(new Student("Charlie", 3.8));
// Хранятся в порядке: Alice, Bob, Charlie (по алфавиту)

Иерархия и требования

TreeSet использует TreeMap внутри

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E> {
    private transient NavigableMap<E, Object> m;  // Внутренняя TreeMap
    
    public TreeSet() {
        this(new TreeMap<>());  // Требует Comparable
    }
    
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));  // С Comparator
    }
}

Так что если передашь объект без Comparable и без Comparator - получишь ClassCastException:

class CustomClass {  // НЕ реализует Comparable
    private int value;
}

// ❌ ОШИБКА!
TreeSet<CustomClass> set = new TreeSet<>();
set.add(new CustomClass());  // ClassCastException: CustomClass cannot be cast to Comparable

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

Пример 1: Сортировка студентов по разным критериям

public class Student implements Comparable<Student> {
    private String name;
    private int id;
    private double gpa;
    
    public Student(String name, int id, double gpa) {
        this.name = name;
        this.id = id;
        this.gpa = gpa;
    }
    
    // Сортировка по ID по умолчанию
    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.id, other.id);
    }
    
    public String getName() { return name; }
    public int getId() { return id; }
    public double getGpa() { return gpa; }
    
    @Override
    public String toString() {
        return name + " (ID: " + id + ", GPA: " + gpa + ")";
    }
}

// Сортировка по ID (по умолчанию из compareTo)
TreeSet<Student> byId = new TreeSet<>();
byId.add(new Student("Alice", 102, 3.9));
byId.add(new Student("Bob", 101, 3.5));
byId.add(new Student("Charlie", 103, 3.8));
System.out.println(byId);
// Bob (ID: 101, GPA: 3.5), Alice (ID: 102, GPA: 3.9), Charlie (ID: 103, GPA: 3.8)

// Сортировка по GPA (с Comparator)
TreeSet<Student> byGpa = new TreeSet<>(
    Comparator.comparingDouble(Student::getGpa).reversed()
);
byGpa.addAll(byId);
System.out.println(byGpa);
// Alice (ID: 102, GPA: 3.9), Charlie (ID: 103, GPA: 3.8), Bob (ID: 101, GPA: 3.5)

// Сортировка по имени
TreeSet<Student> byName = new TreeSet<>(
    Comparator.comparing(Student::getName)
);
byName.addAll(byId);
System.out.println(byName);
// Alice, Bob, Charlie

Пример 2: Запрет дубликатов

// TreeSet использует compareTo для определения уникальности
public class Product implements Comparable<Product> {
    private int id;
    private String name;
    
    public Product(int id, String name) {
        this.id = id;
        this.name = name;
    }
    
    @Override
    public int compareTo(Product other) {
        return Integer.compare(this.id, other.id);
    }
    
    @Override
    public String toString() {
        return "Product(" + id + ", " + name + ")";
    }
}

TreeSet<Product> products = new TreeSet<>();
products.add(new Product(1, "Laptop"));
products.add(new Product(2, "Mouse"));
products.add(new Product(1, "Desktop"));  // Дубликат ID, не будет добавлен!

System.out.println(products.size());  // 2, а не 3!
System.out.println(products);
// Product(1, Laptop), Product(2, Mouse)

Пример 3: Сортировка объектов по нескольким критериям

public class Employee implements Comparable<Employee> {
    private String department;
    private String name;
    private double salary;
    
    public Employee(String department, String name, double salary) {
        this.department = department;
        this.name = name;
        this.salary = salary;
    }
    
    // Сортировка сначала по отделу, потом по имени
    @Override
    public int compareTo(Employee other) {
        int deptCompare = this.department.compareTo(other.department);
        if (deptCompare != 0) {
            return deptCompare;
        }
        return this.name.compareTo(other.name);
    }
    
    @Override
    public String toString() {
        return department + " - " + name + " (" + salary + ")";
    }
}

TreeSet<Employee> employees = new TreeSet<>();
employees.add(new Employee("IT", "Zoe", 80000));
employees.add(new Employee("HR", "Alice", 60000));
employees.add(new Employee("IT", "Bob", 75000));
employees.add(new Employee("HR", "Charlie", 65000));

System.out.println(employees);
// HR - Alice (60000), HR - Charlie (65000), IT - Bob (75000), IT - Zoe (80000)

Типичные ошибки

Ошибка 1: Забыл Comparable

class MyClass {  // ❌ НЕ реализует Comparable
    private int value;
}

TreeSet<MyClass> set = new TreeSet<>();
set.add(new MyClass());  // ClassCastException!

Ошибка 2: Некорректное сравнение

public class BadComparable implements Comparable<BadComparable> {
    private int value;
    
    @Override
    public int compareTo(BadComparable other) {
        // ❌ НЕПРАВИЛЬНО!
        return this.value - other.value;  // Может быть overflow!
        // Если this.value = 2000000000, other.value = -2000000000
        // Результат: 4000000000 (overflow, становится отрицательным)
    }
}

// ✅ ПРАВИЛЬНО!
public class GoodComparable implements Comparable<GoodComparable> {
    private int value;
    
    @Override
    public int compareTo(GoodComparable other) {
        return Integer.compare(this.value, other.value);
    }
}

Ошибка 3: Нарушение контракта Comparable

// ❌ НЕПРАВИЛЬНО! Нарушает контракт (не транзитивно)
public class BadContract implements Comparable<BadContract> {
    private int value;
    
    @Override
    public int compareTo(BadContract other) {
        return value % 3 - other.value % 3;  // Нарушает транзитивность
    }
}

// ✅ ПРАВИЛЬНО! Контракт соблюдается
public class GoodContract implements Comparable<GoodContract> {
    private int value;
    
    @Override
    public int compareTo(GoodContract other) {
        return Integer.compare(value, other.value);
    }
}

Итоговое резюме

В TreeSet можно добавлять:

1. Объекты, реализующие Comparable:

   TreeSet<String> set = new TreeSet<>();  // String implements Comparable
   

2. Объекты с передачей Comparator в конструктор:

   TreeSet<MyClass> set = new TreeSet<>(comparator);
   

3. Встроенные классы: Integer, String, Double, LocalDate и т.д.

Нельзя добавлять:

1. Объекты без Comparable и без Comparator → ClassCastException
2. null → NullPointerException (если Comparator не обрабатывает null)

Важные правила:

• Метод compareTo() должен быть согласован с equals() (обычно)
• TreeSet гарантирует упорядоченное хранение
• Время операций: O(log n) для добавления, удаления, поиска
• TreeSet НЕ позволяет дубликаты (как и HashSet)