Что такое TreeSet в Java?

TreeSet – это реализация интерфейса NavigableSet, основанная на структуре данных красно-черного дерева (реализуется через TreeMap). Его ключевая особенность – хранение элементов в отсортированном порядке.

Основные характеристики:

• Сортировка: Элементы хранятся в естественном порядке (для Comparable) или согласно заданному Comparator.
• Производительность: Время выполнения основных операций (add, remove, contains) составляет O(log n).
• Уникальность: Не допускает дубликатов (свойство Set).
• Null-значения: Не разрешает null, если используется естественный порядок (Comparable).

Пример создания и использования:

// Создание TreeSet с естественным порядком (для Integer — по возрастанию)
TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(1);
numbers.add(3);
System.out.println(numbers); // Вывод: [1, 3, 5]

// Методы для навигации по отсортированному набору
Integer first = numbers.first(); // 1
Integer last = numbers.last();   // 5
Integer higher = numbers.higher(3); // 5 (наименьший элемент > 3)
Integer lower = numbers.lower(3);   // 1 (наибольший элемент < 3)

// Создание с пользовательским Comparator (по убыванию)
TreeSet<String> reverseSorted = new TreeSet<>(Comparator.reverseOrder());
reverseSorted.add("Banana");
reverseSorted.add("Apple");
System.out.println(reverseSorted); // [Banana, Apple]

Важные замечания:

• Не синхронизирован. Для использования в многопоточной среде требуется внешняя синхронизация: SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
• Итератор возвращает элементы в порядке сортировки.
• Идеально подходит для сценариев, где критически важен порядок элементов и нужен быстрый поиск.