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

Моя цель - предложение широкого ассортимента товаров и услуг на постоянно высоком качестве обслуживания по самым выгодным ценам.
image

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


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


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

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


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

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


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


Интересные статьи

Интересные статьи

Доброго времени суток! Как известно, одной из характерных черт JavaScript, наряду c мультипарадигменностью, слабой (динамической) типизацией, автоматическим управлением памятью и ...
Всем привет. Когда я искал информацию о журналировании (аудите событий) в Bitrix, на Хабре не было ни чего, в остальном рунете кое что было, но кто же там найдёт? Для пополнения базы знаний...
В течение первых нескольких лет использования JavaScript я чувствовал себя чуть ли не самозванцем. Даже хотя я и мог создавать веб-сайты с помощью фреймворков, я ощущал, что мне чего-то не хватае...
История сегодня пойдёт про автосервис в Москве и его продвижении в течении 8 месяцев. Первое знакомство было ещё пару лет назад при странных обстоятельствах. Пришёл автосервис за заявками,...
Вначале была функция и вызывали ее в одном месте. Потом мы захотели вызвать ее в другом месте с новыми возможностями и обновили ее. Нам эта ф-ия так понравилась, что мы вызвали ее в третьем месте...