Try English version of Quizful



Раздаем бесплатные Q! подробности в группе Quizful.Alpha-test
Партнеры
Рекрутерам: Прескрининг кандидатов about
Топ контрибуторов
loading
loading
Знаете ли Вы, что

Если у вас есть уникальная статья и вы хотите, чтобы она стала достоянием общественности, вы можете разместить ее на Quizful.

Лента обновлений
ссылка Dec 15 20:00
Комментарий от volart:
bool isExp (int32_t a){
return (a & -a) == a;
}
ссылка Dec 14 18:10
Добавлен вопрос в тест Java - Эксперт
ссылка Dec 14 15:04
Комментарий от rtyuehe:
Поддерживаю. Ответ "Function that converts a number in a...
ссылка Dec 14 14:25
Комментарий от andrey1_2:
Не уверен, что "millions of lines" это обязательный ат...
ссылка Dec 14 14:22
Комментарий от andrey1_2:
magnetic tapes .... are very popular data storage solu...
Статистика

Тестов: 153, вопросов: 8580. Пройдено: 389961 / 1895370.

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

head tail Статья
категория
Java
дата13.06.2013
авторvovanok
голосов34

Введение

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

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

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

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

Пример

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

Map treeMap = new TreeMap<>();

treeMap.put("Bruce""Willis");

treeMap.put("Arnold""Schwarzenegger");

treeMap.put("Jackie""Chan");

treeMap.put("Sylvester""Stallone");

treeMap.put("Chuck""Norris");

      

for(Map.Entry e : treeMap.entrySet()){

 

    System.out.println(e.getKey()+" "+ e.getValue());

}


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

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

public interface Comparator {

    public int compare (Object object1, Object object2);

    public boolean equals (Object object);

}


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

public interface Comparable {

    public int compareTo (Object objectToCompare);

}



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

Пример:

public class MyCustomKey implements Comparable{

     private int value;

 

     public MyCustomKey(int value){

        this.value = value;

    } 

        

      public int compareTo (MyCustomKey key){

        int comparison =0;         

         // Note:

        // Return -1 if this.value < key.value

        // Return  0 if this.value = key.value

        // Return  1 if this.value > key.value             

        // …. Реализация сравнения….

        return(comparison);

     }

 

     public int hashCode(){

         return(this.value *199);

     }

}



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

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

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

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

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

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

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

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

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

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

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

Иерархия treemap
Рисунок 2

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

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

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

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

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

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

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

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

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

800px-Red-black_tree_example.svg
Рисунок 3

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

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

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

Если Вам понравилась статья, проголосуйте за нее

Голосов: 34  loading...
AlexVovolka   vovanok   nagibator000   fdk512   Glare   GalaranF   hassan   RedMantis   Geniy   miroshnik1993   Letos   Amagister   siriusbetta   alexgiant   OlafStaf   Gleb90   Tryhanuch   Zusy_MT   nvgup   polinkot   zealousstudent   mimi27   DR_Smith   pr4yer   SamTan   KZ_Jumper   NiKo1996   devi17   togruls   VladimirBabenko   yer9ali   fil7   bixa   Dasmio