Почему реализация TreeSet в Java содержит в названии слово «Tree»?

Название TreeSet отражает его внутреннюю структуру данных — он построен на основе самобалансирующегося бинарного дерева поиска (конкретно, красно-черного дерева).

Ключевые следствия использования древовидной структуры:

• Автоматическая сортировка: Элементы хранятся в отсортированном порядке согласно их естественному порядку (Comparable) или предоставленному Comparator. Это основное отличие от HashSet, где порядок не определен.
• Логарифмическая сложность операций: Базовые операции (add, remove, contains) выполняются за время O(log n), что предсказуемее, чем в HashSet (амортизированное O(1), но может деградировать).
• Навигационные методы: Реализуя интерфейс NavigableSet, TreeSet предоставляет методы для работы с отсортированным порядком: higher(), lower(), ceiling(), floor(), subSet(), headSet(), tailSet().

Пример, демонстрирующий сортировку и навигацию:

TreeSet<Integer> scores = new TreeSet<>();
scores.add(85);
scores.add(92);
scores.add(78);

System.out.println(scores); // [78, 85, 92] - автоматическая сортировка
System.out.println("First: " + scores.first()); // 78
System.out.println("Last: " + scores.last());  // 92
System.out.println("Score lower than 90: " + scores.lower(90)); // 85
System.out.println("Subset between 80 and 95: " + scores.subSet(80, 95)); // [85, 92]

Слово "Tree" прямо указывает на эту древовидную реализацию, которая обеспечивает упорядоченность и предсказуемую производительность.