2-3-дерево. Наивная реализация

[@ns5d]

ошибка?

[@konshyn]

Да, спасибо! Исправил.

[@konshyn]

P.S. Не по теме, но хочется сказать :)
Спасибо всем тем, кто пишет статьи, — это реально отнимает много собственных сил и времени. Это действительно круто, что вы есть!

[@zasaz63]

скажите, чем пользовались для отрисовки графов?

[@konshyn]

Векторный редактор InkScape

[@Videoman]

К сожалению, ни на хабре, ни на других ресурсах я не смог найти достаточно полную информацию на русском языке…

На всякий случай, может автору будет интересно. Все вопросы со структурами данных подробно и понятно описаны в книге Роберта Седжвика «Алгоритмы на С++. Анализ структур данных, сортировка, поиск алгоритмы на графах», в том числе и на русском языке. Вся теория подробна изложена с реализацией на С++. Там описаны, в том числе, 2-...-N деревья, как частный случай B-деревьев и сами B-деревья. Вообще книга, на мой взгляд, является лучшей книгой по структурам данных для программистов.

[@konshyn]

Да, я знаю. Лежит на столе и читается по мере надобности. Но из реализаций там нет ни 2-3-дерева, ни 2-3-4-дерева, а только аналог последного — красно-черное дерево. И самое сложное в данных деревьях — операция удаления — описаны совсем уж поверхностно, как и во всех других русскоязычных источниках, что я видел.

[@konshyn]

Посмотрел только что Седжвика и есть небольшое уточнение. В книге не описаны 2-3-деревья, только 2-3-4, при этом про операцию удаления ни слова.

[@Videoman]

Есть у этой книги небольшой недостаток, её желательно читать всю. Там последующий главы ссылаются на предыдущие. Седжвик приводит 2-3-4 деревья, как частный случай B-деревьев, лишь для того, чтобы показать как они отображаются на RB-деревья (что это одно и то же). Далее он говорит, что данный тип деревьев (2-3-4) не эффективен в виде «наивной» реализации для структур в ОЗУ, но т.к. любое дерево можно представить в виде бинарного, есть метод, как сделать это эффективно, используя лишь один дополнительный бит на узел, это и есть RB-деревья. Работа с бинарными же деревьями у него разбирается очень подробно. Также, в главе про 2-3-4 деревья упоминается, что в последующих главах будет представлена более общая реализация B-деревьев. Там узел может иметь любое заданное листьев (N), в том числе и 3, как в вашем случае. Но B-деревья более эффективны для работы с внешними источниками данных, таких как файловые системы и базы данных.

[@cl0ne]

В дополнение к статье: Седжвик в курсе на Coursera неплохо рассказывает про 2-3-деревья.

[@QtRoS]

Приятно зайти в комментарии и увидеть, что твоя мысль уже озвучена. Тоже хотел порекомендовать этот курс, считаю его основополагающим в плане понимания алгоритмов и структур данных.

[@blanabrother]

Публичные викиконспекты университета ИТМО — не все расписано так детально как хотелось бы, но в целом неплохо, плюс на вики много другого интересного.

[@izvolov]

Коллега, вы, судя по всему, только начинаете осваивать язык C++, поэтому хочу дать пару советов, которые сильно упростят жизнь в будущем.

1. Не пишите на "Си с классами".

   
   

   Либо Си, либо Си++. Никаких гибридов, даже для экспериментов. Не нужно привыкать к вредным практикам.

   
   

   Безумно нравиться в языке Си++ должны не конструкторы, а деструкторы (искать по ключевому слову RAII).
   А также шаблоны (их здесь, как раз, и не хватает).

   
   

2. При проектировании интерфейсов в языке C++ лучше всего отталкиваться от стандартной библиотеки

   
   

   В данном случае нужно смотреть на интерфейсы ассоциативных массивов. Например, map.

   
   

[@x6x4]

Большое спасибо автору! Статья очень выручила в своё время.