Comments 14
ошибка?
P.S. Не по теме, но хочется сказать :)
Спасибо всем тем, кто пишет статьи, — это реально отнимает много собственных сил и времени. Это действительно круто, что вы есть!
Спасибо всем тем, кто пишет статьи, — это реально отнимает много собственных сил и времени. Это действительно круто, что вы есть!
скажите, чем пользовались для отрисовки графов?
К сожалению, ни на хабре, ни на других ресурсах я не смог найти достаточно полную информацию на русском языке…
На всякий случай, может автору будет интересно. Все вопросы со структурами данных подробно и понятно описаны в книге Роберта Седжвика «Алгоритмы на С++. Анализ структур данных, сортировка, поиск алгоритмы на графах», в том числе и на русском языке. Вся теория подробна изложена с реализацией на С++. Там описаны, в том числе, 2-...-N деревья, как частный случай B-деревьев и сами B-деревья. Вообще книга, на мой взгляд, является лучшей книгой по структурам данных для программистов.
На всякий случай, может автору будет интересно. Все вопросы со структурами данных подробно и понятно описаны в книге Роберта Седжвика «Алгоритмы на С++. Анализ структур данных, сортировка, поиск алгоритмы на графах», в том числе и на русском языке. Вся теория подробна изложена с реализацией на С++. Там описаны, в том числе, 2-...-N деревья, как частный случай B-деревьев и сами B-деревья. Вообще книга, на мой взгляд, является лучшей книгой по структурам данных для программистов.
Да, я знаю. Лежит на столе и читается по мере надобности. Но из реализаций там нет ни 2-3-дерева, ни 2-3-4-дерева, а только аналог последного — красно-черное дерево. И самое сложное в данных деревьях — операция удаления — описаны совсем уж поверхностно, как и во всех других русскоязычных источниках, что я видел.
Есть у этой книги небольшой недостаток, её желательно читать всю. Там последующий главы ссылаются на предыдущие. Седжвик приводит 2-3-4 деревья, как частный случай B-деревьев, лишь для того, чтобы показать как они отображаются на RB-деревья (что это одно и то же). Далее он говорит, что данный тип деревьев (2-3-4) не эффективен в виде «наивной» реализации для структур в ОЗУ, но т.к. любое дерево можно представить в виде бинарного, есть метод, как сделать это эффективно, используя лишь один дополнительный бит на узел, это и есть RB-деревья. Работа с бинарными же деревьями у него разбирается очень подробно. Также, в главе про 2-3-4 деревья упоминается, что в последующих главах будет представлена более общая реализация B-деревьев. Там узел может иметь любое заданное листьев (N), в том числе и 3, как в вашем случае. Но B-деревья более эффективны для работы с внешними источниками данных, таких как файловые системы и базы данных.
В дополнение к статье: Седжвик в курсе на Coursera неплохо рассказывает про 2-3-деревья.
Публичные викиконспекты университета ИТМО — не все расписано так детально как хотелось бы, но в целом неплохо, плюс на вики много другого интересного.
Коллега, вы, судя по всему, только начинаете осваивать язык C++, поэтому хочу дать пару советов, которые сильно упростят жизнь в будущем.
Не пишите на "Си с классами".
Либо Си, либо Си++. Никаких гибридов, даже для экспериментов. Не нужно привыкать к вредным практикам.
Безумно нравиться в языке Си++ должны не конструкторы, а деструкторы (искать по ключевому слову RAII).
А также шаблоны (их здесь, как раз, и не хватает).
При проектировании интерфейсов в языке C++ лучше всего отталкиваться от стандартной библиотеки
В данном случае нужно смотреть на интерфейсы ассоциативных массивов. Например, map.
Большое спасибо автору! Статья очень выручила в своё время.
Sign up to leave a comment.
2-3-дерево. Наивная реализация