TreeSet в Java

Java предоставляет обширный набор структур данных для эффективной работы с коллекциями элементов. Одной из таких структур данных является TreeSet, реализация красно-черного дерева в Java. TreeSet поддерживает отсортированный порядок для хранения уникальных элементов: он реализует интерфейс NavigableSet, выполняет добавление, удаление и поиск за O(log n), держит элементы в порядке естественного сравнения или заданного компаратора и не принимает null. Новичкам использование класса TreeSet в Java может показаться поначалу немного сложным. В этой статье мы разберемся, как использовать TreeSet, объясним его основные концепции и предоставим примеры кода, которые помогут вам начать применять TreeSet в ваших Java-проектах.

Кратко

• TreeSet это реализация NavigableSet на красно-черном дереве: хранит только уникальные элементы и всегда держит их отсортированными.
• Порядок задает либо естественное сравнение элементов (Comparable), либо Comparator, переданный в конструктор.
• Методы add(), remove() и contains() работают за O(log n): медленнее, чем O(1) у HashSet, зато набор всегда упорядочен.
• null в TreeSet положить нельзя: при естественном порядке add(null) бросает NullPointerException.
• Кроме обычных методов Set есть навигация: first(), last(), ceiling(), floor(), higher(), lower(), pollFirst(), pollLast() и диапазонные subSet(), headSet(), tailSet().
• Внутри TreeSet это обертка над TreeMap, поэтому сложность операций у них одинаковая.

Структура TreeSet: красно-черное дерево

Как мы упоминали ранее, структура класса TreeSet в Java реализована как самобалансирующееся бинарное дерево поиска, известное как красно-черное дерево. Давайте объясним, что это такое... Красно-черное дерево представляет собой сбалансированную структуру данных бинарного поиска, обычно используемую для хранения и организации отсортированных данных. Оно получило свое название благодаря свойствам, которые поддерживают его баланс:

• Каждый узел дерева является либо красным, либо черным.
• Корень красно-черного дерева всегда черный.
• Все листовые узлы (NIL-узлы или нулевые ссылки) являются черными.
• Если узел дерева красный, то его дочерние узлы черные.
• Каждый простой путь от узла к его потомкам содержит одинаковое количество черных узлов.

Красно-черные деревья демонстрируют эффективную производительность для операций вставки, удаления и поиска элементов за счет обеспечения баланса. Это гарантирует, что высота дерева остается пропорциональной логарифму количества содержащихся в нем узлов, что приводит к логарифмической временной сложности операций. Внутри TreeSet отдельного дерева нет: это обертка над TreeMap, где элементы набора лежат ключами карты. Именно так класс и описан в документации Oracle: реализация NavigableSet на основе TreeMap. Красно-черные деревья находят широкое применение в различных областях, включая реализацию сбалансированных деревьев поиска в языках программирования, базах данных (например, внутренние индексные структуры) и других сценариях, где необходимо эффективное хранение и выполнение операций с отсортированными данными.

Особенности и недостатки TreeSet

TreeSet предоставляет несколько ключевых функций, которые делают его ценным инструментом для управления коллекциями объектов в отсортированном виде. Преимущества:

• Автоматическое поддержание элементов в отсортированном порядке. При добавлении или удалении элементов древовидная структура корректируется, чтобы сохранить их отсортированными. Это устраняет необходимость ручной сортировки и обеспечивает эффективный доступ в порядке возрастания или убывания.
• Эффективные операции поиска, вставки и удаления. Использует структуру бинарного дерева поиска, что позволяет выполнять эти операции с временной сложностью O(log N). Где N это количество элементов.
• TreeSet гарантирует уникальность элементов, используя их естественный порядок или пользовательский Comparator. Это полезно при работе с коллекциями, требующими различных элементов.

Ограничения:

• Немного медленнее, чем HashSet из-за поддержания отсортированного порядка.
• Не допускает null-элементы, так как полагается на естественный порядок или пользовательский Comparator для сравнения элементов. Исключение одно: если компаратор написан так, что умеет сравнивать null, такой элемент добавить получится.

Java TreeSet: примеры основных операций

Теперь давайте продемонстрируем, как создать TreeSet в Java, получить размер коллекции, добавить в нее элементы, удалить их и проверить, присутствует ли элемент в TreeSet. Эти примеры кода демонстрируют основные операции при работе с TreeSet: создание экземпляра, добавление элементов, удаление элементов, проверка наличия элемента и получение размера TreeSet.

Создание TreeSet и добавление элементов

Создаем набор чисел и кладем в него четыре элемента методом add():

// Создание TreeSet типа Integer
TreeSet<Integer> numbers = new TreeSet<>();

// Добавление элементов в TreeSet
numbers.add(18);
numbers.add(2);
numbers.add(7);
numbers.add(28);

System.out.println(numbers); // Вывод: [2, 7, 18, 28]

Здесь мы используем метод add() для добавления 4 чисел в наш TreeSet. Если создать метод main и запустить программу, вывод будет в отсортированном порядке (2, 7, 18, 28).

Удаление элементов

Удалить элемент из набора можно методом remove():

TreeSet<String> names = new TreeSet<>();

names.add("Johnny");
names.add("Ivy");
names.add("David");
names.add("Ricky");

// Удаление элемента из TreeSet
names.remove("David");

System.out.println(names); // Вывод: [Ivy, Johnny, Ricky]

Проверка наличия элемента

Метод contains() отвечает, есть ли элемент в наборе:

TreeSet<String> musicalInstrument = new TreeSet<>();

musicalInstrument.add("Piano");
musicalInstrument.add("Drums");
musicalInstrument.add("Violin");
musicalInstrument.add("Double Bass");

// Проверка существования элемента в TreeSet
boolean containsPiano = musicalInstrument.contains("Piano");
boolean containsCello = musicalInstrument.contains("Cello");

System.out.println(containsPiano); // Вывод: true
System.out.println(containsCello); // Вывод: false

Размер коллекции

Количество элементов возвращает метод size():

TreeSet<Character> letters = new TreeSet<>();

letters.add('A');
letters.add('B');
letters.add('C');
letters.add('D');

// Получение размера TreeSet
int size = letters.size();

System.out.println(size); // Вывод: 4

Сортировка и итерирование в TreeSet

TreeSet в Java предоставляет мощные функции для сортировки и итерирования по коллекциям элементов. В этом разделе мы рассмотрим различные техники сортировки элементов, итерирования по TreeSet и выполнения диапазонного поиска с использованием методов subSet(), headSet() и tailSet(). По умолчанию TreeSet автоматически поддерживает элементы в отсортированном порядке. Однако мы можем настроить поведение сортировки, предоставив Comparator при создании TreeSet. Давайте посмотрим на пример:

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

public class TreeSetSortingExample {
  public static void main(String[] args) {
    // Создание TreeSet с пользовательской сортировкой
    TreeSet<Integer> numbers = new TreeSet<>(Comparator.reverseOrder());

    // Добавление элементов в TreeSet
    numbers.add(5);
    numbers.add(3);
    numbers.add(7);
    numbers.add(1);

    System.out.println(numbers); // Вывод: [7, 5, 3, 1]
  }
}

В приведенном выше коде мы создаем TreeSet типа Integer и предоставляем пользовательский Comparator, используя Comparator.reverseOrder() для сортировки элементов в порядке убывания. Полученный TreeSet будет содержать элементы [7, 5, 3, 1]. Существует несколько способов итерирования по TreeSet. Мы можем использовать итератор или использовать расширенный цикл for-each. Давайте посмотрим примеры обоих подходов:

import java.util.TreeSet;
import java.util.Iterator;

public class TreeSetIterationExample {
  public static void main(String[] args) {
    TreeSet<String> names = new TreeSet<>();

    names.add("Johnny");
    names.add("Ivy");
    names.add("Ricky");
    names.add("David");

    // Итерирование с использованием итератора
    Iterator<String> iterator = names.iterator();
    while (iterator.hasNext()) {
      String name = iterator.next();
      System.out.println(name);
    }

    // Итерирование с использованием расширенного цикла for-each
    for (String name : names) {
      System.out.println(name);
    }
  }
}

В приведенном выше коде мы создаем TreeSet с именем names и добавляем несколько элементов. Затем мы демонстрируем два способа итерирования по TreeSet: используя итератор и используя расширенный цикл for-each. TreeSet предоставляет методы для выполнения диапазонного поиска, позволяющие извлекать подмножества элементов на основе определенных критериев. Три основных метода для диапазонного поиска:

• subSet(E fromElement, E toElement): Возвращает подмножество элементов от fromElement (включительно) до toElement (исключительно).
• headSet(E toElement): Возвращает подмножество элементов меньше toElement.
• tailSet(E fromElement): Возвращает подмножество элементов больше или равных fromElement.

Давайте посмотрим на пример:

import java.util.TreeSet;

public class TreeSetRangeSearchExample {
  public static void main(String[] args) {
    TreeSet<Integer> numbers = new TreeSet<>();

    numbers.add(1);
    numbers.add(3);
    numbers.add(5);
    numbers.add(7);
    numbers.add(9);

    // Выполнение диапазонного поиска с использованием subSet()
    TreeSet<Integer> subset = new TreeSet<>(numbers.subSet(3, 8));
    System.out.println(subset); // Вывод: [3, 5, 7]

    // Выполнение диапазонного поиска с использованием headSet()
    TreeSet<Integer> headSet = new TreeSet<>(numbers.headSet(6));
    System.out.println(headSet); // Вывод: [1, 3, 5]

    // Выполнение диапазонного поиска с использованием tailSet()
     TreeSet<Integer> tailSet = new TreeSet<>(numbers.tailSet(5));
    System.out.println(tailSet); // Вывод: [5, 7, 9]
  }
}

В приведенном выше коде мы создаем TreeSet с именем numbers и добавляем несколько элементов. Затем мы демонстрируем диапазонный поиск с использованием методов subSet(), headSet() и tailSet().

• subset TreeSet содержит элементы между 3 (включительно) и 8 (исключительно), которые являются [3, 5, 7].
• headSet TreeSet содержит элементы меньше 6, которые являются [1, 3, 5].
• tailSet TreeSet содержит элементы больше или равные 5, которые являются [5, 7, 9].

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

Методы для навигации

Вы изучили основы использования TreeSet для хранения и извлечения элементов в отсортированном порядке. Но знаете ли вы, что TreeSet имеет очень удобные методы навигации для быстрого поиска элементов без итерирования по всему набору? Давайте погрузимся в эти методы и увидим их в действии.

Получение первого и последнего элементов

Метод first() возвращает наименьший (или «самый низкий») элемент в TreeSet, в то время как last() возвращает наибольший (или «самый высокий»). Идеально подходит, когда вы хотите мгновенно получить граничные элементы.

import java.util.TreeSet;

public class TreeSetFirstLastExample {
    public static void main(String[] args) {
        TreeSet<Integer> numbers = new TreeSet<>();
        numbers.add(10);
        numbers.add(40);
        numbers.add(20);
        numbers.add(30);

        System.out.println("TreeSet: " + numbers);
        System.out.println("Первый элемент: " + numbers.first());
        System.out.println("Последний элемент: " + numbers.last());
    }
}

Вывод:

TreeSet: [10, 20, 30, 40]
Первый элемент: 10
Последний элемент: 40

first() и last() являются операциями O(log n), так как TreeSet основан на древовидной структуре. Это все еще довольно эффективно для извлечения граничных элементов.

Поиск элементов с помощью ceiling(), floor(), higher() и lower()

Когда вам нужно найти ближайшее совпадение с заданным значением, эти методы спасают ситуацию:

• ceiling(e): возвращает наименьший элемент, больший или равный e.
• floor(e): возвращает наибольший элемент, меньший или равный e.
• higher(e): возвращает наименьший элемент, строго больший e.
• lower(e): возвращает наибольший элемент, строго меньший e.

Давайте посмотрим на пример:

import java.util.TreeSet;

public class TreeSetNavigationExample {
    public static void main(String[] args) {
        TreeSet<Integer> numbers = new TreeSet<>();
        numbers.add(15);
        numbers.add(10);
        numbers.add(25);
        numbers.add(20);

        System.out.println("TreeSet: " + numbers);

        System.out.println("ceiling(18): " + numbers.ceiling(18));  // Возвращает 20
        System.out.println("floor(18): " + numbers.floor(18));      // Возвращает 15
        System.out.println("higher(20): " + numbers.higher(20));    // Возвращает 25
        System.out.println("lower(15): " + numbers.lower(15));      // Возвращает 10
    }
}

Вывод:

TreeSet: [10, 15, 20, 25]
ceiling(18): 20
floor(18): 15
higher(20): 25
lower(15): 10

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

Удаление элементов с помощью pollFirst() и pollLast()

Нужно немедленно удалить наименьший или наибольший элемент? pollFirst() удаляет и возвращает первый элемент, в то время как pollLast() делает то же самое для последнего элемента.

import java.util.TreeSet;

public class TreeSetPollExample {
    public static void main(String[] args) {
        TreeSet<Integer> numbers = new TreeSet<>();
        numbers.add(5);
        numbers.add(15);
        numbers.add(25);

        System.out.println("TreeSet перед извлечением: " + numbers);

        int first = numbers.pollFirst(); // Удаляет 5
        System.out.println("Извлечен первый: " + first);
        System.out.println("TreeSet теперь: " + numbers);

        int last = numbers.pollLast();   // Удаляет 25
        System.out.println("Извлечен последний: " + last);
        System.out.println("TreeSet теперь: " + numbers);
    }
}

Вывод:

TreeSet перед извлечением: [5, 15, 25]
Извлечен первый: 5
TreeSet теперь: [15, 25]
Извлечен последний: 25
TreeSet теперь: [15]

Эти методы пригодятся для сценариев, когда вы хотите поддерживать отсортированную коллекцию, но также удалять граничные элементы по требованию, например, при имитации min-heap или max-heap.

Обход в обратном порядке: descendingSet() и descendingIterator()

Если элементы нужны от большего к меньшему, копировать набор не нужно. Метод descendingSet() возвращает представление того же набора в обратном порядке, а descendingIterator() сразу дает итератор, который идет с конца.

import java.util.Iterator;
import java.util.TreeSet;

public class TreeSetDescendingExample {
    public static void main(String[] args) {
        TreeSet<Integer> numbers = new TreeSet<>();
        numbers.add(10);
        numbers.add(40);
        numbers.add(20);
        numbers.add(30);

        System.out.println("Обычный порядок: " + numbers);
        System.out.println("Обратный порядок: " + numbers.descendingSet());

        Iterator<Integer> iterator = numbers.descendingIterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
    }
}

Вывод:

Обычный порядок: [10, 20, 30, 40]
Обратный порядок: [40, 30, 20, 10]
40 30 20 10 

Важно, что descendingSet() это именно представление, а не копия: изменения в исходном наборе видны в нем, и наоборот. С Java 21 у отсортированных наборов появился еще один набор методов: интерфейс SortedSet теперь наследует SequencedSet, а через него SequencedCollection (JEP 431), а значит у TreeSet есть getFirst(), getLast(), removeFirst(), removeLast() и reversed(). Делают они то же самое, что first(), last(), pollFirst(), pollLast() и descendingSet(), но теперь одинаково называются у списков, очередей и наборов. Методы addFirst() и addLast() у отсортированных наборов бросают UnsupportedOperationException: позицию элемента определяет порядок сортировки, а не вызывающий код.

Comparator в TreeSet: сортировка с пользовательскими критериями

Помимо естественного порядка, вы можете использовать пользовательский Comparator для сортировки TreeSet. В этом разделе мы углубимся в концепцию компаратора и его роль в TreeSet. Мы рассмотрим, как создать TreeSet с пользовательским компаратором, и предоставим примеры кода для демонстрации сортировки TreeSet на основе конкретных критериев.

Что такое Comparator?

Comparator это интерфейс в Java, который позволяет выполнять пользовательскую сортировку объектов. Он предоставляет способ определения порядка элементов на основе определенных атрибутов или свойств. Реализуя интерфейс Comparator и переопределяя его метод compare(), мы можем указать, как элементы должны быть отсортированы в TreeSet.

Создание TreeSet с пользовательским Comparator

Чтобы создать TreeSet с пользовательским компаратором, нам нужно передать компаратор в качестве аргумента при создании экземпляра TreeSet. Давайте посмотрим на пример:

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

public class TreeSetComparatorExample {
  public static void main(String[] args) {
    // Создание TreeSet с пользовательским компаратором
    TreeSet<String> names = new TreeSet<>(new LengthComparator());

    // Добавление элементов в TreeSet
    names.add("Johnny");
    names.add("Ivy");
    names.add("Rick");
    names.add("David");

    System.out.println(names); // Вывод: [Ivy, Rick, David, Johnny]
  }
}

class LengthComparator implements Comparator<String> {
  @Override
  public int compare(String s1, String s2) {
    return Integer.compare(s1.length(), s2.length());
  }
}

В приведенном выше коде мы создаем TreeSet с именем names с пользовательским компаратором LengthComparator. LengthComparator сравнивает длину двух строк и сортирует их соответственно. В результате TreeSet сортируется по длине строк, что дает нам вывод [Ivy, Rick, David, Johnny].

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

Помимо создания TreeSet с пользовательским компаратором, мы также можем использовать компаратор для временной сортировки TreeSet без изменения его естественного порядка. Давайте посмотрим на пример:

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

  public class TreeSetTest {
    public static void main(String[] args) {
      TreeSet<String> names = new TreeSet<>();

      names.add("Johnny");
      names.add("Ivy");
      names.add("Ricky");
      names.add("David");

      // Временная сортировка TreeSet с использованием компаратора
      TreeSet<String> sortedNames = new TreeSet<>(Comparator.reverseOrder());
      sortedNames.addAll(names);

      System.out.println(sortedNames); // Вывод: [Ricky, Johnny, Ivy, David]
      System.out.println(names); // Вывод: [David, Ivy, Johnny, Ricky]
    }
  }

В приведенном выше коде мы создаем TreeSet с именем names и добавляем несколько элементов. Затем мы создаем новый TreeSet с именем sortedNames с пользовательским компаратором Comparator.reverseOrder(). Добавляя все элементы из исходного TreeSet names в sortedNames, мы получаем временную отсортированную версию TreeSet.

Сравнение TreeSet с другими структурами данных

Сначала сводка, а дальше подробности по каждой структуре:

Сравнение TreeSet с HashSet

Как TreeSet, так и HashSet являются реализациями интерфейса Set в Java. Однако между ними есть существенные различия. TreeSet: TreeSet хранит уникальные элементы в отсортированном порядке. Он использует самобалансирующееся бинарное дерево поиска (обычно красно-черное дерево) для поддержания отсортированного порядка, что приводит к логарифмической временной сложности для операций, таких как вставка, удаление и поиск. TreeSet эффективен для поддержания отсортированной коллекции и выполнения диапазонных операций. Однако он имеет более высокие затраты памяти из-за древовидной структуры и не допускает null-элементы. HashSet: HashSet хранит уникальные элементы в неупорядоченном виде, используя хеш-коды и хеш-таблицу внутри. Он обеспечивает константную временную сложность для базовых операций, таких как вставка, удаление и поиск. HashSet эффективен для быстрого поиска элементов и не накладывает дополнительных затрат памяти на поддержание порядка. Однако он не гарантирует какого-либо конкретного порядка элементов.

Когда использовать TreeSet:

• Когда вам нужно автоматически поддерживать элементы в отсортированном порядке.
• Когда требуются диапазонные операции или нужно эффективно находить элементы в определенном диапазоне.
• Когда дублирующиеся элементы не допускаются и уникальность важна.
• Когда вы готовы пожертвовать немного большим использованием памяти ради преимуществ автоматической сортировки и диапазонных операций.

Сравнение TreeSet с ArrayList

ArrayList это реализация динамического массива в Java. Вот ключевые различия между TreeSet и ArrayList:

• TreeSet: TreeSet хранит уникальные элементы в отсортированном порядке, обеспечивая эффективные операции для поддержания отсортированной коллекции и выполнения диапазонного поиска. Имеет логарифмическую временную сложность для операций. TreeSet не подходит для произвольного доступа или поддержания порядка вставки.
• ArrayList: ArrayList хранит элементы в порядке вставки, обеспечивая быстрый произвольный доступ к элементам с использованием индексов. Имеет константную временную сложность для большинства операций при доступе к элементам по индексу. Однако имеет линейную временную сложность для вставки или удаления элементов из середины списка, так как это требует смещения элементов.

Когда рассматривать другие структуры данных

• Если поддержание элементов в отсортированном порядке не требуется, и вам нужен быстрый поиск элементов или неупорядоченная коллекция, HashSet может быть лучшим выбором.
• Если вам требуется частый произвольный доступ к элементам по индексу или необходимо поддерживать порядок вставки, ArrayList будет более подходящим.

Вопросы и ответы

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

Это реализация интерфейса NavigableSet, построенная на красно-черном дереве. Набор хранит только уникальные элементы и всегда держит их отсортированными: по естественному порядку элементов или по компаратору, который передали в конструктор. Добавление, удаление и проверка наличия стоят O(log n). В документации Oracle класс так и описан: реализация NavigableSet на основе TreeMap.

Чем TreeSet отличается от HashSet?

Порядком и скоростью. HashSet держит элементы в хеш-таблице, порядок не гарантирует и выполняет базовые операции в среднем за O(1). TreeSet держит элементы в дереве, всегда возвращает их отсортированными и тратит на операции O(log n). Плюс HashSet разрешает один null, а TreeSet при естественном порядке не разрешает ни одного. Берите TreeSet, если нужен порядок или поиск по диапазону, и HashSet, если нужен только быстрый поиск.

Можно ли добавить null в TreeSet?

При естественном порядке нет: add(null) бросает NullPointerException, потому что набор сравнивает новый элемент с уже существующими. Исключение одно: если вы передали в конструктор собственный компаратор, который умеет обрабатывать null, такой элемент добавить получится. На практике на это не полагаются, а пустые значения отфильтровывают до вставки.

Как отсортировать TreeSet в обратном порядке?

Двумя способами. Первый: передать в конструктор набора компаратор Comparator.reverseOrder(), тогда набор изначально хранит элементы по убыванию. Второй: оставить обычный набор и получить обратное представление методом descendingSet() или пройти его через descendingIterator(). Второй способ ничего не копирует, это именно представление того же набора.

Как найти ближайший элемент к заданному значению?

Для этого есть четыре метода навигации. ceiling(e) вернет наименьший элемент, который больше или равен e, floor(e) наибольший из тех, что меньше или равны, а higher(e) и lower(e) делают то же самое, но строго больше и строго меньше. Для набора 10, 15, 20, 25 вызов ceiling(18) даст 20, а floor(18) даст 15. Если подходящего элемента нет, методы возвращают null.

Что будет, если компаратор считает разные объекты одинаковыми?

Они станут дубликатами, и второй элемент в набор не попадет. TreeSet определяет равенство не через equals(), а через результат сравнения: если compare() вернул ноль, элемент считается уже существующим. Компаратор из примера этой статьи сравнивает строки по длине, поэтому после «Rick» слово «Anna» в набор не добавится. Документация Oracle называет это требованием согласованности с equals(). Читайте также:

• ArrayList в Java
• Структуры данных: пирамида (двоичная куча) в Java
• Алгоритмы сортировки в теории и на практике