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

    image

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

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


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

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


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

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


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

    Подробнее
    Реклама

    Комментарии 6

      +1
      Впечатление незаконченности статьи.
      Т.е. взяли стороннюю либу деревьев и приделали визуализацию?
      d3.js — это средство для визуализации? тогда хотелось бы что-то про него и как его использовать.
        0
        Взял статью, в которой небыло ссылки на исходный код, разобрался в алгоритме, собрал код, который там был разбросан в виде картинок и добавил визуализацию.
        +1
        А ваш-то код или картинки где? :)

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


        Поясните? Красно-черным деревьям как структуре данных почти 50 лет. Как «код может устареть»? Это как говорить «Ну вон там есть код, моделирующий свободное падение, но он устарел лет на 20». Кажется, такие вещи не устаревают, не?
          +1
          Алгоритм «моделирующий свободное падение» возможно и не может устареть)
          А вот его реализация в конкретном коде — легко. Языки-то развиваются, появяются новые конструкции и меняются подходы. Сам код будет рабочий, но вот встроить его в текущее решение написанное по новым подходам с новыми конструкциями может быть не очень удобно. Плюс еще и зависимости этого кода могут быть еще старее… в общем в этом вопросе не так просто.
            0
            Код на гитхабе. В начале статьи есть ссылка.
              +3

              Упомянутый код безжалостно заклеймен "устаревшим" потому, что в js стеке, по моим наблюдениям, устаревшим считается код, не использующий всех современных фич es6-7-8-etc или, не дай бог, использующий прототипы напрямую.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое