Treemap красно черное дерево

Руководство по TreeMap в Java

В этой статье мы собираемся изучить реализациюTreeMap интерфейсаMap из Java Collections Framework (JCF).

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

Ранее мы рассмотрели реализацииHashMap иLinkedHashMap, и мы поймем, что существует довольно много похожей информации о том, как работают эти классы.

Упомянутые статьи настоятельно рекомендуется прочитать, прежде чем приступить к этой.

2. Сортировка по умолчанию вTreeMap

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

Давайте посмотрим на естественный порядок в тесте:

@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() < TreeMapmap = new TreeMap<>(); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString()); >

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

Аналогично, когда мы используем строки, они будут отсортированы в их естественном порядке, т.е. по алфавиту:

@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2() < TreeMapmap = new TreeMap<>(); map.put("c", "val"); map.put("b", "val"); map.put("a", "val"); map.put("e", "val"); map.put("d", "val"); assertEquals("[a, b, c, d, e]", map.keySet().toString()); >

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

3. Пользовательская сортировка вTreeMap

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

В приведенном ниже примере мы хотим, чтобы целочисленные ключи были расположены в порядке убывания:

@Test public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() < TreeMapmap = new TreeMap<>(Comparator.reverseOrder()); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString()); >

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

4. Важность сортировкиTreeMap

Теперь мы знаем, чтоTreeMap хранит все свои записи в отсортированном порядке. Из-за этого атрибута древовидных карт мы можем выполнять такие запросы, как; найти «самый большой», найти «самый маленький», найти все ключи меньше или больше определенного значения и т. д.

Код ниже покрывает только небольшой процент этих случаев:

@Test public void givenTreeMap_whenPerformsQueries_thenCorrect() < TreeMapmap = new TreeMap<>(); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); Integer highestKey = map.lastKey(); Integer lowestKey = map.firstKey(); Set keysLessThan3 = map.headMap(3).keySet(); Set keysGreaterThanEqTo3 = map.tailMap(3).keySet(); assertEquals(new Integer(5), highestKey); assertEquals(new Integer(1), lowestKey); assertEquals("[1, 2]", keysLessThan3.toString()); assertEquals("[3, 4, 5]", keysGreaterThanEqTo3.toString()); >

5. Внутренняя реализацияTreeMap

TreeMap реализует интерфейсNavigableMap и основывает его внутреннюю работу на принципах красно-черных деревьев:

public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, java.io.Serializable

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

First of all, красно-черное дерево — это структура данных, состоящая из узлов; Представьте себе перевернутое манговое дерево с корнем в небе и ветвями, растущими вниз. Корень будет содержать первый элемент, добавленный в дерево.

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

Это правило гарантирует, что записи древовидной карты всегда будут в отсортированном и предсказуемом порядке.

Secondly, красно-черное дерево — это самобалансирующееся двоичное дерево поиска. Этот атрибут и приведенные выше гарантируют, что базовые операции, такие как поиск, получение, размещение и удаление, занимают логарифмическое времяO(log n).

Быть самоуравновешенным является ключевым здесь. По мере того, как мы продолжаем вставлять и удалять записи, представьте себе, что дерево растет длиннее на одном краю или короче на другом.

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

Поэтому об этом заботятся в оформлении красно-черных деревьев. Для каждой вставки и удаления максимальная высота дерева на любом ребре поддерживается на уровнеO(log n), т.е. дерево постоянно уравновешивается.

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

6. Выбор правильной карты

Посмотрев на реализацииHashMap иLinkedHashMap ранее, а теперь наTreeMap, важно провести краткое сравнение между тремя, чтобы понять, какая из них и где подходит.

A hash map хорош как реализация карты общего назначения, которая обеспечивает быстрые операции хранения и извлечения. Однако, это терпит неудачу из-за его хаотического и неупорядоченного расположения записей.

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

A linked hash map обладает хорошими атрибутами хэш-карт и добавляет порядок в записи. Он работает лучше там, где много итераций, потому что учитывается только количество записей независимо от емкости.

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

Можно сказатьlinked hash map reduces the chaos in the ordering of a hash map without incurring the performance penalty of a tree map.

7. Заключение

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

Полный исходный код всех примеров, использованных в этой статье, можно найти в папкеGitHub project.

Источник

Treemap красно черное дерево

We follow a path from the root to the searched node (or to a NIL leaf). At each level, we perform a comparison. The effort for the comparison is constant. The search cost is thus proportional to the tree height. We denote by n the number of tree nodes. In the «Height of a Red-Black Tree» section, we have recognized that the longest path is at most twice as long as the shortest path. It follows that the height of the tree is bounded by O(log n). A formal proof is beyond the scope of this article. You can read the proof on Wikipedia. Thus, the time complexity for finding a node in a red-black tree is: O(log n)

Insertion Time

• Checking the color of the parent node
• Determination of the uncle node and checking its color
• Recoloring one up to three nodes
• Performing one or two rotations

Each of these operations has constant time, O(1), in itself. The total time for checking and repairing the tree is therefore also proportional to its height.

So the time complexity for inserting into a red-black tree is also: O(log n)

Deletion Time

Just as with insertion, we first search for the node to be deleted in time O(log n).

Also, the deletion cost is independent of the tree size, so it is constant O(1).

For checking the rules and repairing the tree, one or more of the following operations occur – at most once per level:

• Checking the color of the deleted node
• Determining the sibling and examining its color
• Checking the colors of the sibling’s children
• Recoloring the parent node
• Recoloring the sibling node and one of its children
• Performing one or two rotations

These operations also all have a constant complexity in themselves. Thus, the total effort for checking and restoring the rules after deleting a node is also proportional to the tree height.

So the time complexity for deleting from a red-black tree is also: O(log n)

Red-Black Tree Compared With Other Data Structures

The following sections describe the differences and the advantages and disadvantages of the red-black tree compared to alternative data structures.

Red-Black Tree vs. AVL Tree

The red-black tree, as well as the AVL tree, are self-balancing binary search trees.

In the red-black tree, the longest path to the root is at most twice as long as the shortest path to the root. On the other hand, in the AVL tree, the depth of no two subtrees differs by more than 1.

In the red-black tree, balance is maintained by the node colors, a set of rules, and by rotating and recoloring nodes. In the AVL tree, the heights of the subtrees are compared, and rotations are performed when necessary.

These differences in the characteristics of the two types of trees lead to the following differences in performance and memory requirements:

• Due to the more even balancing of the AVL tree, search in an AVL tree is usually faster. In terms of magnitude, however, both are in the range O(log n).
• For insertion and deletion, the time complexity in both trees is O(log n). In a direct comparison, however, the red-black tree is faster because it rebalances less frequently.
• Both trees require additional memory: the AVL tree one byte per node for the height of the subtree starting at a node; the red-black tree one bit per node for the color information. This rarely makes a difference in practice since a single bit usually occupies at least one byte.

If you expect many insert/delete operations, then you should use a red-black tree. If, on the other hand, you expect more search operations, then you should choose the AVL tree.

Red-Black Tree vs. Binary Search Tree

The red-black tree is a concrete implementation of a self-balancing binary search tree. So every red-black tree is also a binary search tree.

There are also other types of binary search trees, such as the AVL tree mentioned above – or trivial non-balanced implementations. Thus, not every binary search tree is also a red-black tree.

Summary

This tutorial taught you what a red-black tree is, which rules govern it and how these rules are evaluated and restored if necessary after inserting and deleting nodes. I also introduced you to a Java implementation that is as easy to understand as possible.

The JDK uses red-black trees in TreeMap (here is the source code on GitHub) and in bucket collisions in HashMap (here is the source code).

With this, I conclude the tutorial series on binary trees.

If I could help you better understand binary trees in general, binary search trees, AVL trees, and – in this article – red-black trees, I’m happy about a comment. Also, feel free to share the article using one of the share buttons at the end.

Do you want to be informed when the next article is published on HappyCoders.eu? Then click here to sign up for the HappyCoders newsletter.

Источник