TreeSet: примеры (JAVA)

Примеры использования TreeSet

Пример 1. Создание и базовые операции с числами.

import java.util.TreeSet;

TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(2);
numbers.add(8);
numbers.add(1);
System.out.println(numbers);
System.out.println(numbers.contains(2));
numbers.remove(5);
System.out.println(numbers);

[1, 2, 5, 8]
true
[1, 2, 8]

Пример 2. TreeSet с компаратором для строк в обратном алфавитном порядке.

import java.util.Comparator;
import java.util.TreeSet;

TreeSet<String> words = new TreeSet<>(Comparator.reverseOrder());
words.add("яблоко");
words.add("апельсин");
words.add("банан");
System.out.println(words);
System.out.println(words.first());
System.out.println(words.last());

[яблоко, банан, апельсин]
яблоко
апельсин

Пример 3. Использование методов first, last, subSet.

TreeSet<Integer> set = new TreeSet<>(Set.of(10, 20, 30, 40, 50));
System.out.println("first: " + set.first());
System.out.println("last: " + set.last());
System.out.println("headSet(30): " + set.headSet(30));
System.out.println("tailSet(30): " + set.tailSet(30));
System.out.println("subSet(20, 50): " + set.subSet(20, 50));

first: 10
last: 50
headSet(30): [10, 20]
tailSet(30): [30, 40, 50]
subSet(20, 50): [20, 30, 40]

Пример 4. Использование higher, lower, ceiling, floor.

TreeSet<Integer> set = new TreeSet<>(Set.of(10, 20, 30, 40, 50));
System.out.println("higher(30): " + set.higher(30));
System.out.println("lower(30): " + set.lower(30));
System.out.println("ceiling(25): " + set.ceiling(25));
System.out.println("floor(25): " + set.floor(25));
System.out.println("ceiling(50): " + set.ceiling(50));
System.out.println("higher(50): " + set.higher(50));

higher(30): 40
lower(30): 20
ceiling(25): 30
floor(25): 20
ceiling(50): 50
higher(50): null

Альтернативные коллекции в Java

В Java существуют другие реализации Set, которые стоит рассматривать в зависимости от требований к порядку и производительности:

• HashSet - не гарантирует порядок элементов, но операции выполняются за O(1) (среднее время). Используется, когда порядок не важен и нужна максимальная скорость.
• LinkedHashSet - сохраняет порядок вставки элементов (как LinkedList). Скорость операций близка к HashSet, но требует чуть больше памяти. Подходит для поддержания порядка добавления.
• TreeMap - реализует интерфейс Map, но можно использовать keySet() для получения упорядоченного множества ключей. Если требуется хранить пары ключ-значение, выбирайте TreeMap, а не TreeSet.

Выбор между TreeSet и другими коллекциями: если критична сортировка или нужно получать подмножества по диапазону, используйте TreeSet. В остальных случаях чаще предпочтительнее HashSet из-за лучшей производительности.

Аналоги в других языках программирования

Ниже приведены аналоги TreeSet в популярных языках с краткими примерами и отличиями.

PHP

$set = new \Ds\Set([5, 2, 8]);
$set->sort();
print_r($set->toArray()); // [2, 5, 8]

Array ( [0] => 2 [1] => 5 [2] => 8 )

Отличие: в PHP нет встроенного сортированного множества. Расширение DS (Data Structures) предоставляет Set, который не сортирует автоматически, требуется ручная сортировка. Также можно использовать array_unique и sort, но это не полноценная коллекция.

JavaScript

const set = new Set([5, 2, 8]);
const sorted = [...set].sort((a,b) => a - b);
console.log(sorted); // [2, 5, 8]

[2, 5, 8]

Set в JavaScript не упорядочен (хотя в современных спецификациях сохраняет порядок вставки), но не поддерживает автоматическую сортировку. Приходится каждый раз сортировать массив вручную.

Python

s = {5, 2, 8}
sorted_list = sorted(s)
print(sorted_list)  # [2, 5, 8]

[2, 5, 8]

Встроенные set и frozenset не упорядочены. Для сортированного множества можно использовать сторонние библиотеки (например, sortedcontainers) или вручную сортировать каждый раз. В Python упорядоченное множество не предоставляется стандартной библиотекой.

C#

using System.Collections.Generic;

var set = new SortedSet<int> { 5, 2, 8 };
Console.WriteLine(string.Join(", ", set)); // 2, 5, 8

2, 5, 8

SortedSet в C# - прямой аналог TreeSet. Реализован на красно-черном дереве. Поддерживает аналогичные методы (Add, Remove, Contains, Min, Max, GetViewBetween).

Lua

local set = {}
set[5] = true; set[2] = true; set[8] = true
local keys = {}
for k,_ in pairs(set) do keys[#keys+1]=k end
table.sort(keys)
for _,v in ipairs(keys) do print(v) end

2
5
8

Lua не имеет встроенного множества. Обычно используют таблицы с ключами, а затем сортируют ключи. Полноценного аналога TreeSet нет.

Go

package main
import (
    "fmt"
    "sort"
)

func main() {
    m := map[int]bool{5: true, 2: true, 8: true}
    keys := make([]int, 0, len(m))
    for k := range m {
        keys = append(keys, k)
    }
    sort.Ints(keys)
    fmt.Println(keys) // [2 5 8]
}

[2 5 8]

В Go нет встроенного сортированного множества. Используют map для уникальности, затем сортируют ключи. Существуют сторонние библиотеки (например, github.com/emirpasic/gods/sets/treeset), но они не встроены.

Kotlin

import java.util.TreeSet

fun main() {
    val set = TreeSet<Int>()
    set.addAll(listOf(5, 2, 8))
    println(set) // [2, 5, 8]
}

[2, 5, 8]

Kotlin работает на JVM, поэтому TreeSet доступен напрямую. Дополнительно есть функция sortedSetOf и toSortedSet для удобства.

Типичные ошибки при работе с TreeSet

1. ClassCastException при отсутствии Comparable или Comparator

import java.util.TreeSet;

class Person { String name; }

TreeSet<Person> set = new TreeSet<>();
set.add(new Person()); // Ошибка

Exception in thread "main" java.lang.ClassCastException: class Person cannot be cast to class java.lang.Comparable

Решение: либо реализовать Comparable в классе Person, либо предоставить Comparator в конструкторе.

2. NullPointerException при добавлении null

TreeSet<String> set = new TreeSet<>();
set.add(null); // Ошибка

Exception in thread "main" java.lang.NullPointerException

TreeSet не допускает null, так как сравнение с null невозможно. Альтернатива: обрабатывать null отдельно или использовать другую коллекцию.

3. ConcurrentModificationException при изменении во время итерации

TreeSet<Integer> set = new TreeSet<>(Set.of(1, 2, 3));
for (Integer n : set) {
    if (n == 2) set.remove(n); // Ошибка
}

Exception in thread "main" java.util.ConcurrentModificationException

Решение: использовать итератор с методом iterator.remove() или создать копию коллекции для итерации.

4. Несинхронизированный доступ в многопоточном окружении

TreeSet<Integer> set = new TreeSet<>();
// одновременная модификация из разных потоков может привести к повреждению структуры

Решение: обернуть через Collections.synchronizedSortedSet или использовать ConcurrentSkipListSet.

Изменения в TreeSet в последних версиях Java

TreeSet был введен в Java 2 (1.2). В версии Java 5 были добавлены обобщения (Generics). В Java 6 появился интерфейс NavigableSet (расширение SortedSet), и TreeSet был переработан для его поддержки, добавив методы ceiling, floor, higher, lower, pollFirst, pollLast, descendingIterator, descendingSet. В Java 8 были добавлены методы-дефолты в интерфейсе Collection (например, removeIf, stream, parallelStream), которые работают с TreeSet. В последующих версиях (Java 9+) существенных изменений в самом классе не произошло, но улучшилась производительность за счет оптимизаций сборщика мусора и JIT. Начиная с Java 21 (LTS) изменений, касающихся TreeSet, не зафиксировано - класс остается стабильным.

Расширенные примеры использования TreeSet

Пример A. Пользовательский класс с Comparator по нескольким полям.

import java.util.*;

class Employee {
    String name;
    int salary;
    Employee(String n, int s) { name = n; salary = s; }
    public String toString() { return name + ":" + salary; }
}

Comparator<Employee> bySalaryThenName = Comparator
    .comparingInt((Employee e) -> e.salary)
    .thenComparing(e -> e.name);

TreeSet<Employee> employees = new TreeSet<>(bySalaryThenName);
employees.add(new Employee("Иван", 50000));
employees.add(new Employee("Петр", 60000));
employees.add(new Employee("Мария", 50000));
System.out.println(employees);

[Иван:50000, Мария:50000, Петр:60000]

Пример B. Использование subSet с модификацией.

TreeSet<Integer> set = new TreeSet<>(Set.of(10, 20, 30, 40, 50));
SortedSet<Integer> sub = set.subSet(20, 40);
System.out.println("sub до: " + sub);
sub.add(25);
System.out.println("set после: " + set);
sub.remove(30);
System.out.println("set после удаления: " + set);

sub до: [20, 30]
set после: [10, 20, 25, 30, 40, 50]
set после удаления: [10, 20, 25, 40, 50]

Пример C. Преобразование TreeSet в массив с сохранением порядка.

TreeSet<Integer> set = new TreeSet<>(Set.of(3, 1, 4, 1, 5, 9));
Integer[] arr = set.toArray(new Integer[0]);
System.out.println(Arrays.toString(arr)); // [1, 3, 4, 5, 9]

[1, 3, 4, 5, 9]

Пример D. Использование descendingSet и pollFirst/pollLast для очереди с приоритетом.

TreeSet<Integer> set = new TreeSet<>(Set.of(40, 10, 30, 20));
NavigableSet<Integer> desc = set.descendingSet();
System.out.println("desc: " + desc);
System.out.println("pollFirst (min): " + set.pollFirst());
System.out.println("pollLast (max): " + set.pollLast());
System.out.println("set после: " + set);

desc: [40, 30, 20, 10]
pollFirst (min): 10
pollLast (max): 40
set после: [20, 30]

Пример E. TreeSet с лямбда-выражением для сортировки строк по длине.

TreeSet<String> set = new TreeSet<>(Comparator.comparingInt(String::length));
set.addAll(Set.of("яблоко", "дом", "компьютер", "кот"));
System.out.println(set); // [дом, кот, яблоко, компьютер]

[дом, кот, яблоко, компьютер]

Пример F. Копирование TreeSet в ArrayList с сортировкой (естественный порядок уже есть).

TreeSet<Integer> set = new TreeSet<>(Set.of(5, 3, 8, 1));
ArrayList<Integer> list = new ArrayList<>(set);
System.out.println(list); // [1, 3, 5, 8]

[1, 3, 5, 8]

Пример G. Использование Stream API с TreeSet.

TreeSet<Integer> set = new TreeSet<>(Set.of(10, 20, 30));
int sum = set.stream().filter(n -> n > 15).mapToInt(Integer::intValue).sum();
System.out.println(sum); // 20+30 = 50

50