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

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

License

Algorithms-and-Data-Structures-2021/semester-work-red-black-tree

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

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

Сложность ключевых операций структуры данных

Описание основных частей семестрового проекта.

Проект состоит из следующих частей:

• src / include — реализация структуры данных (исходный код и заголовочные файлы);
• benchmark — контрольные тесты производительности структуры данных (операции добавления, удаления, поиска и пр.);
• dataset — наборы данных для запуска контрольных тестов и их генерация;

1. С++ компилятор c поддержкой стандарта C++17 (например, GNU GCC 8.1.x и выше).
2. Система автоматизации сборки CMake (версия 3.12.x и выше).
3. Рекомендуемый объем оперативной памяти — не менее 8 ГБ.
4. Свободное дисковое пространство объемом ~ 2 ГБ (набор данных для контрольных тестов).

Склонируйте проект к себе на устройство через Git for Windows (либо используйте возможности IDE):

git clone https://github.com/Algorithms-and-Data-Structures-2021/semester-work-red-black-tree.git

Генерация тестовых данных

Для генерации чисел мы использовали ГПСЧ (генератор псевдослучайных чисел), а именно mersenne twister, (mt19937). Генерирует случайное число он довольно быстро. Определен он в хедере random и пространстве имён std. Является 32-битным генератором.

Генерация тестового набора данных в формате comma-seperated values (CSV):

# переход в папку генерации набора данных cd dataset

По названию директории /dataset/data/add можно понять, что здесь хранятся наборы данных для контрольных тестов по добавлению элементов в структуру данных. Названия файлов 100.csv . 5000000.csv и т.д. хранят информацию о размере набора данных (т.е. количество элементов).

Контрольные тесты (benchmarks)

В benchmark / Benchmark.cpp реализовано одновременное тестирование всех ключевых методов по всем контрольным тестам. Если Вы хотите протестировать лишь один из методов, то закомментируйте тестирование остальных методов.

Список контрольных тестов

Источник

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

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.

Источник

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

Привет Хабр! Изучал недавно красно-черные деревья. Попробовал визуализировать детали работы алгоритмов вставки и удаления на d3.js. Надеюсь, полученный результат поможет сэкономить немного времени тем, кто изучает алгоритмы на javascript. Посмотреть можно тут. Исходник реализации, от которой отталкивался тут . Под катом краткие подробности.

Поиск существующих решений

Главной целью задумки было разобраться в реализации алгоритма и визуализировать ее. Первым делом стал искать реализацию с полными и понятными пояснениями и кодом на js. В процессе поиска опечалило, что авторы временами недоделывают исходник, например, тут есть алгоритм вставки, но нету удаления. Или делают визуализацию как тут , но не дают ссылки на исходник. Потом нашел вот эту отличную статью. Но хоть убейте, до сих пор не могу понять почему автор вставил код картинками и не дал по запросу в коментах ссылку на исходник. Есть еще npm пакет red-black-tree , весь исходный код которого: ‘in progress. ‘ в readme. Также нашлась популярная реализация красно-черных деревьев на js, от которой зависит куча пакетов и миллионы закачек в неделю, но код там устарел лет на пять.

Расстановка приоритетов и конкретизация задачи

Пораскинув мозгами, решил, что читаемость и понятность кода для учебных целей приоритетнее, поэтому взял за основу статью, которую упоминал вначале, а не npm пакет. Реализация оказалась более удобной и наглядной в плане чтения кода. В статье автор начинает с двоичного дерева, потом расширяет его до красно-черного. Для визуализации выглядит вполне логичным наследовать от красно-черного дерева и сделать анимированное дерево. Поэтому, перенабрав код и убедившись, что он работает, приступил к рисованию анимированного дерева. Дальше на помощь приходит d3.js. Там есть замечательные transitions, которые позволяют двигать элементы в нужные позиции и плавно трансформировать в подходящие состояния, по ходу работы алгоритма.

Смысл красно-черных деревьев

Долго думал, как бы по простому, объяснить что к чему. Наверное, все таки надо почитать теорию из разных источников. Как говорится: «Из песни слов не выкинешь». Но простые итоговые выводы в двух словах сформулировать можно. Суть сводится к тому, что есть несколько кейсов при вставке и удалении элемента, в зависимости от которых «дедушки», «папы», «дяди», «дети», «братья» перекрашиваются и сдвигаются (поворачиваются) в сторону, где элементов меньше. В результате никогда не бывает, чтобы путь от самого дальнего узла к корневому был слишком длинным, поэтому поиск нужного элемента в такой структуре происходит очень быстро. Ну а компенсируется это сложностью вставки и удаления.

Источник