1
Мне было задано задание на домашнее задание ответить на вопрос о деревьях «красно-красно-черных». Описание красно-красно-черного дерева (скопированный откуда-то в интернете) является:Число узлов с удельной черной высотой в красно-красно-черных деревьях
«Красно-красно-черное дерево является бинарное дерево, которое удовлетворяет следующим условиям:
- Каждый узел красный или черный
- Каждый лист (ноль) черный
- Если узел красный и его родителей красный, то оба его потомка черны
- Каждый простой путь от узла к листьям, такое же количество черных узлов (черная высота дерева) "
Меня спрашивали, учитывая красно-красно-черное дерево с n узлами, какое наибольшее количество внутренних узлов с черной высотой k? Какое наименьшее число?
Я пытаюсь думать об этом более двух часов, но кроме головной боли я никуда не мог добраться.
Спасибо!
пункт 3 не звучит правильно вообще ... и должен быть другой пункт, говорящий, что корень всегда черный. «Где-то в Интернете» не всегда является хорошим ориентиром ... – Gevorg
Это не определение красного/черного дерева, с которым я знаком; Я чаще видел точку (3), поскольку «ни один красный узел не имеет красного ребенка». Откуда у вас это определение? – templatetypedef