Красно черное дерево сортировка

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.

Источник

Красно-черные деревья: коротко и ясно

Итак, сегодня хочу немного рассказать о красно-черных деревьях. Рассказ будет кратким, без рассмотрения алгоритмов балансировки при вставке/удалении элементов в красно-черных деревьях.

Красно-черные деревья относятся к сбалансированным бинарным деревьям поиска.

Как бинарное дерево, красно-черное обладает свойствами:

1) Оба поддерева являются бинарными деревьями поиска.

2) Для каждого узла с ключом выполняется критерий упорядочения:

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

Свойства красно-черных деревьев:

1) Каждый узел окрашен либо в красный, либо в черный цвет (в структуре данных узла появляется дополнительное поле – бит цвета).

2) Корень окрашен в черный цвет.

3) Листья(так называемые NULL-узлы) окрашены в черный цвет.

4) Каждый красный узел должен иметь два черных дочерних узла. Нужно отметить, что у черного узла могут быть черные дочерние узлы. Красные узлы в качестве дочерних могут иметь только черные.

5) Пути от узла к его листьям должны содержать одинаковое количество черных узлов(это черная высота).

Ну и почему такое дерево является сбалансированным?

Действительно, красно-черные деревья не гарантируют строгой сбалансированности (разница высот двух поддеревьев любого узла не должна превышать 1), как в АВЛ-деревьях. Но соблюдение свойств красно-черного дерева позволяет обеспечить выполнение операций вставки, удаления и выборки за время . И сейчас посмотрим, действительно ли это так.

Пусть у нас есть красно-черное дерево. Черная высота равна (black height).

Если путь от корневого узла до листового содержит минимальное количество красных узлов (т.е. ноль), значит этот путь равен .

Если же путь содержит максимальное количество красных узлов ( в соответствии со свойством ), то этот путь будет равен .

То есть, пути из корня к листьям могут различаться не более, чем вдвое (, где h — высота поддерева), этого достаточно, чтобы время выполнения операций в таком дереве было

Как производится вставка?

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

Свойство 1 не нарушается, поскольку новому узлу сразу присваивается красный цвет.

Свойство 2 нарушается только в том случае, если у нас было пустое дерево и первый вставленный узел (он же корень) окрашен в красный цвет. Здесь достаточно просто перекрасить корень в черный цвет.

Свойство 3 также не нарушается, поскольку при добавлении узла он получает черные листовые NULL-узлы.

В основном встречаются 2 других нарушения:

1) Красный узел имеет красный дочерний узел (нарушено свойство ).

2) Пути в дереве содержат разное количество черных узлов (нарушено свойство ).

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

Это вообще где-то используется?

Да! Когда в институте на третьем курсе нам читали «Алгоритмы и структуры данных», я и не могла представить, что красно-черные деревья где-то используются. Помню, как мы не любили тему сбалансированных деревьев. Ох уж эти родственные связи в красно-черных деревьях («дядя», «дедушка», «чёрный брат и ~~крестный~~ красный отец»), прям Санта-Барбара какая-то. Правые и левые, малые и большие повороты АВЛ-деревьев – сплошные американские горки. Вы тоже не любите красно-черные деревья? Значит, просто не умеете их готовить. А кто-то просто взял и приготовил. Так, например, ассоциативные массивы в большинстве библиотек реализованы именно через красно-черные деревья.

Это все, что я хотела рассказать.

Источник