TreeSet, особенности и внутреннее устройство
TreeSet — это класс в Java, представляющий собой коллекцию, которая хранит элементы в отсортированном порядке. Он является частью Java Collection Framework и имплементирует интерфейсы NavigableSet, SortedSet, и косвенно Set. Это значит, что TreeSet не допускает дубликатов и автоматически сортирует элементы при их добавлении.
Особенности TreeSet:
Автоматическая сортировка: Элементы в TreeSet автоматически сортируются в соответствии с естественным порядком (Comparable) или по переданному компаратору (Comparator).
Уникальные элементы: Как и любой другой Set, TreeSet не допускает дублирования элементов.
Балансировка: TreeSet основан на сбалансированном бинарном дереве поиска, что гарантирует логарифмическое время выполнения основных операций (добавление, удаление, поиск).
Навигация по элементам: TreeSet предоставляет методы для быстрого доступа к наименьшему и наибольшему элементам, а также позволяет эффективно находить элементы, ближайшие к заданному значению.
Внутреннее устройство TreeSet
TreeSet основан на структуре данных TreeMap, которая, в свою очередь, представляет собой красно-черное дерево — разновидность бинарного дерева поиска. Это дерево поддерживает балансировку, обеспечивая эффективное выполнение операций за время O(log n).
Каждый узел дерева имеет два потомка и родителя, а также хранит информацию о цвете (красный или черный), что помогает поддерживать балансировку дерева. Когда выполняется операция вставки или удаления, дерево перестраивается, чтобы оставаться сбалансированным.
Основные характеристики TreeSet:
Естественный порядок: Если элементы реализуют интерфейс Comparable, они сортируются по нему. Например, строки сортируются в лексикографическом порядке, числа — по возрастанию.
Пользовательский компаратор: Если нужно задать специфический порядок сортировки, можно передать объект Comparator в конструктор TreeSet.
Непотокобезопасность: TreeSet не является потокобезопасным. Если несколько потоков одновременно изменяют его, требуется внешняя синхронизация.
Пример создания TreeSet:
Этот код создаёт TreeSet, добавляет в него несколько строк и выводит их в отсортированном порядке: [Apple, Banana, Cherry].
Когда использовать TreeSet?
Когда требуется поддерживать отсортированный набор элементов: Например, для хранения уникальных слов из текста в алфавитном порядке.
Для задач, требующих быстрого доступа к минимальному или максимальному элементу: Например, когда нужно найти ближайшее к заданному значению число.
Когда нужно реализовать структуры данных с логарифмическим временем выполнения основных операций.
Однако TreeSet может быть неэффективен для больших наборов данных по сравнению с HashSet, так как операции требуют дополнительных вычислений для поддержания сортировки.
Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://www.baeldung.com/java-tree-set
https://for-each.dev/lessons/b/-java-tree-set
#Java #Training #Medium #TreeSet
TreeSet — это класс в Java, представляющий собой коллекцию, которая хранит элементы в отсортированном порядке. Он является частью Java Collection Framework и имплементирует интерфейсы NavigableSet, SortedSet, и косвенно Set. Это значит, что TreeSet не допускает дубликатов и автоматически сортирует элементы при их добавлении.
Особенности TreeSet:
Автоматическая сортировка: Элементы в TreeSet автоматически сортируются в соответствии с естественным порядком (Comparable) или по переданному компаратору (Comparator).
Уникальные элементы: Как и любой другой Set, TreeSet не допускает дублирования элементов.
Балансировка: TreeSet основан на сбалансированном бинарном дереве поиска, что гарантирует логарифмическое время выполнения основных операций (добавление, удаление, поиск).
Навигация по элементам: TreeSet предоставляет методы для быстрого доступа к наименьшему и наибольшему элементам, а также позволяет эффективно находить элементы, ближайшие к заданному значению.
Внутреннее устройство TreeSet
TreeSet основан на структуре данных TreeMap, которая, в свою очередь, представляет собой красно-черное дерево — разновидность бинарного дерева поиска. Это дерево поддерживает балансировку, обеспечивая эффективное выполнение операций за время O(log n).
Каждый узел дерева имеет два потомка и родителя, а также хранит информацию о цвете (красный или черный), что помогает поддерживать балансировку дерева. Когда выполняется операция вставки или удаления, дерево перестраивается, чтобы оставаться сбалансированным.
Основные характеристики TreeSet:
Естественный порядок: Если элементы реализуют интерфейс Comparable, они сортируются по нему. Например, строки сортируются в лексикографическом порядке, числа — по возрастанию.
Пользовательский компаратор: Если нужно задать специфический порядок сортировки, можно передать объект Comparator в конструктор TreeSet.
Непотокобезопасность: TreeSet не является потокобезопасным. Если несколько потоков одновременно изменяют его, требуется внешняя синхронизация.
Пример создания TreeSet:
import java.util.TreeSet;
public class TreeSetExample {
public static void main(String[] args) {
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("Apple");
treeSet.add("Banana");
treeSet.add("Cherry");
System.out.println(treeSet);
}
}
Этот код создаёт TreeSet, добавляет в него несколько строк и выводит их в отсортированном порядке: [Apple, Banana, Cherry].
Когда использовать TreeSet?
Когда требуется поддерживать отсортированный набор элементов: Например, для хранения уникальных слов из текста в алфавитном порядке.
Для задач, требующих быстрого доступа к минимальному или максимальному элементу: Например, когда нужно найти ближайшее к заданному значению число.
Когда нужно реализовать структуры данных с логарифмическим временем выполнения основных операций.
Однако TreeSet может быть неэффективен для больших наборов данных по сравнению с HashSet, так как операции требуют дополнительных вычислений для поддержания сортировки.
Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://www.baeldung.com/java-tree-set
https://for-each.dev/lessons/b/-java-tree-set
#Java #Training #Medium #TreeSet
Baeldung
A Guide to TreeSet in Java | Baeldung
A quick and practical introduction to the TreeSet in Java.
Основные методы TreeSet и примеры использования
Добавление элементов:
boolean add(E e): Добавляет элемент в набор. Возвращает true, если элемент успешно добавлен (не был дубликатом).
Удаление элементов:
boolean remove(Object o): Удаляет элемент из набора. Возвращает true, если элемент был удалён.
void clear(): Удаляет все элементы из набора.
Поиск и получение элементов:
E first(): Возвращает первый (наименьший) элемент в наборе.
E last(): Возвращает последний (наибольший) элемент.
E lower(E e): Возвращает наибольший элемент, строго меньший чем переданный.
E higher(E e): Возвращает наименьший элемент, строго больший чем переданный.
E floor(E e): Возвращает наибольший элемент, меньший или равный переданному.
E ceiling(E e): Возвращает наименьший элемент, больший или равный переданному.
boolean contains(Object o): Проверяет, содержит ли набор указанный элемент.
Навигация и получение поднаборов:
SortedSet<E> headSet(E toElement): Возвращает поднабор от начала до элемента (исключительно).
SortedSet<E> tailSet(E fromElement): Возвращает поднабор от элемента (включительно) до конца.
SortedSet<E> subSet(E fromElement, E toElement): Возвращает поднабор от одного элемента до другого (от включительно, до исключительно).
Примеры использования методов:
1. Работа с элементами:
2. Получение поднаборов:
#Java #Training #Medium #TreeSet
Добавление элементов:
boolean add(E e): Добавляет элемент в набор. Возвращает true, если элемент успешно добавлен (не был дубликатом).
Удаление элементов:
boolean remove(Object o): Удаляет элемент из набора. Возвращает true, если элемент был удалён.
void clear(): Удаляет все элементы из набора.
Поиск и получение элементов:
E first(): Возвращает первый (наименьший) элемент в наборе.
E last(): Возвращает последний (наибольший) элемент.
E lower(E e): Возвращает наибольший элемент, строго меньший чем переданный.
E higher(E e): Возвращает наименьший элемент, строго больший чем переданный.
E floor(E e): Возвращает наибольший элемент, меньший или равный переданному.
E ceiling(E e): Возвращает наименьший элемент, больший или равный переданному.
boolean contains(Object o): Проверяет, содержит ли набор указанный элемент.
Навигация и получение поднаборов:
SortedSet<E> headSet(E toElement): Возвращает поднабор от начала до элемента (исключительно).
SortedSet<E> tailSet(E fromElement): Возвращает поднабор от элемента (включительно) до конца.
SortedSet<E> subSet(E fromElement, E toElement): Возвращает поднабор от одного элемента до другого (от включительно, до исключительно).
Примеры использования методов:
1. Работа с элементами:
import java.util.TreeSet;
public class TreeSetDemo {
public static void main(String[] args) {
TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(2);
numbers.add(10);
numbers.add(1);
System.out.println("Наименьший элемент: " + numbers.first());
System.out.println("Наибольший элемент: " + numbers.last());
System.out.println("Наибольший элемент, меньший 10: " + numbers.lower(10));
}
}
Вывод:
Наименьший элемент: 1
Наибольший элемент: 10
Наибольший элемент, меньший 10: 5
2. Получение поднаборов:
import java.util.TreeSet;
public class TreeSetSubSetExample {
public static void main(String[] args) {
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("Apple");
treeSet.add("Banana");
treeSet.add("Cherry");
treeSet.add("Date");
treeSet.add("Fig");
System.out.println("Поднабор до 'Cherry': " + treeSet.headSet("Cherry"));
System.out.println("Поднабор от 'Banana': " + treeSet.tailSet("Banana"));
}
}
Вывод:
Поднабор до 'Cherry': [Apple, Banana]
Поднабор от 'Banana': [Banana, Cherry, Date, Fig]
#Java #Training #Medium #TreeSet