Красно черное дерево визуализация

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 реализовано одновременное тестирование всех ключевых методов по всем контрольным тестам. Если Вы хотите протестировать лишь один из методов, то закомментируйте тестирование остальных методов.

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

Источник

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

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

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

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

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

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

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

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

Источник

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.

2020. Визуализация алгоритмов для деревьев (произвольного дерева, двоичной кучи, красно-черного дерева, би-дерева; WebGL, threeJS, 3d-force-graph; React, Material-UI).

svtkrp/ShowTree

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

Визуализация деревьев и алгоритмов для них (по шагам с описанием каждого шага для конкретных узлов) + теория об этом. В данный момент можно посмотреть на произвольное дерево, двоичную кучу (min binary heap, min-bin-heap), красно-черное дерево (red-black tree, RB-tree) и би-дерево (B-tree).

Для построения деревьев и визуализации алгоритмов используются JavaScript-библиотеки 3d-force-graph (использующая ThreeJS/WebGL) и ThreeJS (для узлов деревьев). Для главной страницы и области управления деревом используются JavaScript-фреймворки React и Material-UI.

Скачать данный репозиторий:

$ git clone https://github.com/svtkrp/ShowTree.git

Находясь в корневой директории репозитория, выполнить:

$ npm install $ npm run-script build

Затем открыть в браузере public/index.html.

• Сайт https://showtree.my.to/ и главная страница.
• Нормальное отображение на экранах, разных по ширине (PC/планшет/смартфон).
• Возможность скрыть/отобразить область управления деревом.
• Кастомная тема для главной страницы и области управления деревом.

Произвольное дерево:

• Визуализация дерева по умолчанию.
• Визуализация дерева, записанного с помощью специального формата JSON.
• Глубина узла + отображение пути, который использовался для рассчета.
• Высота узла + отображение пути, который использовался для рассчета.
• Краткая теория.

Двоичная куча с корнем — минимальным узлом:

• Визуализация дерева по умолчанию.
• Визуализация дерева, записанного с помощью специального формата JSON.
• Генерация случайного значения узла для вставки.
• Визуализация вставки нового узла по шагам + текстовое описание каждого шага для конкретных узлов.
• Визуализация удаления минимального узла (корня) по шагам + текстовое описание каждого шага для конкретных узлов.
• Теория.

Красно-черное дерево:

• Визуализация дерева по умолчанию.
• Визуализация дерева, записанного с помощью специального формата JSON.
• Генерация случайного значения узла для вставки.
• Визуализация вставки нового узла по шагам + текстовое описание каждого шага для конкретных узлов.
• Визуализация поиска узла по шагам + текстовое описание каждого шага для конкретных узлов.
• Визуализация удаления узла.
• Теория про вставку и поиск (картинки и часть текста взяты с Wikipedia).

• Визуализация дерева по умолчанию.
• Визуализация дерева, записанного с помощью специального формата JSON.
• Генерация случайного значения ключа для вставки.
• Визуализация вставки нового ключа по шагам (в некоторых случаях работает некорректно).
• Визуализация поиска узла по шагам.

About

2020. Визуализация алгоритмов для деревьев (произвольного дерева, двоичной кучи, красно-черного дерева, би-дерева; WebGL, threeJS, 3d-force-graph; React, Material-UI).

Источник