Урок 4. Алгоритм красно-черных деревьев

Название урока: Алгоритм красно-черных деревьев

Краткое описание: Рассмотрена логика алгоритма бинарного дерева и алгоритма красно-черного дерева

Что получу после прохождения урока: понимание как и зачем поддерживать структуру данных красно-черного дерева

ДЗ: придумать реализацию структуры красно-черного дерева на Вашем любимом языке программирования

Использованные материалы: Адитья бхаргава "Грокаем алгоритмы" Тим Рафагарден. Совершенный алгоритм. Основы

[winter-lbid]

Всё что я понял, что дед должен быть черным

[SergSab]

Что-то с балансировкой "Черный дядя - поворот" автор ни то то ли нарисовал то ли наговорил. Три красных узла подряд. "Красный дядя" - также непонятно, корень красный в итоге.

[DadundddaD]

5:00 - при каких случаях могут быть дядя или отец корнем дерева? По-моему это невозможно

[DadundddaD]

5:44 - вообще не понятно, что значит "черный дядя, папа и дед по одной линии"? Что именно мы проверяем, если папа и дед и так по одной линии всегда, мы сами их так расставили?

[kolyanlock]

Магазин красное и черное и красно белые деревья или наоборот :)

[Andrey-xgvy]

Не объяснил в чем суть поворота и что это такое. Что за полный поворот... По идее, мы вообще не можем никакие цифры поворачивать, т.к. большие идут правее, а меньшие левее. Все, что происходило, подходит под подгонку под правила КЧД. Чтобы цвета шли по очереди и чтобы в 1 сторону дерево не заваливалось периодически вытаскивают типа середину в качестве корня, красят его черным и все остальные цвета подгоняют. Но как это алгоритмически описать... Если бы дерево меняло корни после каждой вставки это была бы катастрофа. А если оно так не делает, то врядли будет совпадать количество черных узлов от корня до листьев в его обеих частях. В итоге, можно забить на то, как оно само подгоняется по цветам и в каком случае балансируется, а запомнить только правила КЧД.

[Артем-ъиж]

Нужно иметь талант чтобы так непонятно объяснять, спасибо за бездарно потраченное время