Класс TreeMap, его устройство и способ применения.

Введение

В интернете можно часто встретить вопросы про то, что такое TreeMap, как он устроен, и как им пользоваться. В данной статье я постараюсь кратко ответить на эти вопросы.

Класс TreeMap расширяет класс AbstractMap и реализует интерфейс NavigatebleMap. Он создает коллекцию, которая для хранения элементов применяет дерево. Объекты сохраняются в отсортированном порядке по возрастанию. Время доступа и извлечения элементов достаточно мало, что делает класс TreeMap блестящим выбором для хранения больших объемов отсортированной информации, которая должна быть быстро найдена.

На рисунке 1 показана иерархия предков TreeMap.

Рисунок 1

TreeMap основан на Красно-Черном дереве, вследствие чего TreeMap сортирует элементы по ключу в естественном порядке или на основе заданного вами компаратора.TreeMap гарантирует скорость доступа log(n) для операций containsKey, get, put и remove.

Пример

Давайте рассмотрим простой пример использования TreeMap


Вывод на консоль:

Arnold Schwarzenegger
Bruce Willis
Chuck Norris
Jackie Chan
Sylvester Stallone

Как видим, элементы отсортированы по ключу (Chuck Norris не первый :О).

Чтобы получить ключи и значения нужно использовать методы keySet() и values().

При попытке добавить null-элемент в TreeMap происходит исключение NullPointerException.

Конструкторы

В классе TreeMap присутствуют следующие конструкторы:

1. TreeMap( )

2. TreeMap(Comparator comp)

3. TreeMap(Map m)

4. TreeMap(SortedMap sm)

Первый конструктор создает коллекцию, в которой все элементы отсортированы в натуральном порядке их ключей.

Второй конструктор создаст пустую коллекцию, элементы в которой будут отсортированы по закону, который определен в передаваемом компараторе.

Третий конструктор создаст TreeMap на основе уже имеющегося Map.

Четвертый конструктор создаст TreeMap на основе уже имеющегося SortedMap , элементы в которой будут отсортированы по закону передаваемой SortedMap .

Обратите внимание на то, что для сортировки используются ключи, а не значения.

Синхронизация

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

Можно воспользоваться стандартным механизмом синхронизации, при котором в качестве монитора передаться ссылка объекта, инкапсулирующий данную коллекцию. Если такого объекта нет, можно воспользоваться методом synchronizedSortedMap .
Например:

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

Создание собственного порядка сортировки

Для определения собственного порядка следования элементов в коллекции, нужно реализовать интерфейс Comparator и передать объект своего компаратора в качестве конструктора TreeMap


Или реализовать интерфейс Comparable у класса, который будет использоваться в качестве ключа.



Классы Integer, String, Double и т.п. реализуют интерфейс Comparable. Если вы создали собственный класс для ключей и не реализовали интерфейс Comparable (и не используете Comparator), то при попытке добавления объекта в коллекцию будет брошено исключение java.lang.ClassCastException!

Пример:



Частая ошибка при использовании TreeMap, в том, что для класса ключа не определяется метод hashcode(). Если в данном случае использовать метод map.get(new MyCustomKey()), то результат может быть непредсказуем. Поэтому всегда рекомендуется реализовать метод hashCode() для класса ключей.

Структура данных

Как уже было сказано, TreeMap для хранения элементов применяет красно-черное дерево. Красно-черное дерево это частный случай двоичного дерева поиска.

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

ДДП позволяет выполнять следующие основные операции:

· Поиск вершины по ключу.

· Определение вершин с минимальным и максимальным значением ключа.

· Переход к предыдущей или последующей вершине, в порядке, определяемом ключами.

· Вставка вершины.

· Удаление вершины.

У читателя, возможно, возникает вопрос, зачем нужны такие сложности, если можно просто хранить список пар [ключ, значение]. Ответ прост — операции с деревом работают быстрее. При реализации списком все функции требуют O(n) действий, где n — размер структуры. Операции с деревом же работают за O(h), где h — максимальная глубина дерева (глубина — расстояние от корня до вершины). В оптимальном случае, когда глубина всех листьев одинакова, в дереве будет n=2^h вершин. Значит, сложность операций в деревьях, близких к оптимуму будет O(log(n)).


Рисунок 2

В худшем случае дерево может принять вид, изображённый на рисунке 1. Сложность операций в таком случае будет как у списка.

Красно-черные деревья

Для того, чтобы ситуации как на рисунке 2 не было, применяют специальные сбалансированные деревья.

Сбалансированные деревья:

1. B-дерево
2. АВЛ-дерево
3. Красно-чёрное дерево
….

Красно-чёрное дерево — двоичное дерево поиска, в котором каждый узел имеет атрибут цвет, принимающий значения красный или черный. В дополнение к обычным требованиям, налагаемым на двоичные деревья поиска, к красно-чёрным деревьям применяются следующие требования:

1. Узел либо красный, либо чёрный.
2. Корень — чёрный. (В других определениях это правило иногда опускается. Это правило слабо влияет на анализ, так как корень всегда может быть изменен с красного на чёрный, но не обязательно наоборот).
3. Все листья(NIL) — черные.
4. Оба потомка каждого красного узла — черные.
5. Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.

Минутка философии

Некоторые считают, что красно-черные деревья это всего лишь проекция 2-3-4 деревьев в чисто бинарные, где "настоящие узлы" 2-3-4 деревьев — это черные, а подузлы с 3-мя или 4-мя потомками это красные. Если смотреть правила балансировки 2-3-4 деревьев, то они очень простые, а если смотреть правила балансировки красно-черных деревьев, то они выглядят как мантры и заклинания, где ничего непонятно. :)


Рисунок 3

Количество черных узлов на ветви от корня до листа называется черной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви от корня к листу. Чтобы понять, почему это так, рассмотрим дерево с черной высотой 2. Кратчайшее возможное расстояние от корня до листа равно двум – когда оба узла черные. Длиннейшее расстояние от корня до листа равно четырем – узлы при этом покрашены (от корня к листу) так: красный–>черный–>красный–>черный. Сюда нельзя добавить черные узлы, поскольку при этом нарушится свойство 4, из которого вытекает корректность понятия черной высоты.

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

Если Вы с первого раза не поняли, как работает красно-черное дерево (как и я), то воспользуйтесь визуализатором по ссылке красно-черные деревья . Там пошагово рассказывают и показывают операции поиска и вставки элементов.