В домашнем задании меня попросили ответить на вопрос о деревьях "красный-красный-черный".Описание красно-красно-черного дерева (скопированного из Интернета):
"Красно-красно-черное дерево - это двоичное дерево поиска, удовлетворяющее следующим условиям:
- Каждый узел красный или черный
- Каждый лист (ноль) черный
- Если узел красный, а его родитель красный, то оба его потомка черные
- Каждый простой путь от узла к листу-потомку содержит одинаковое количество черных узлов (высота дерева черного цвета) "
Меня спросили, учитывая красно-красно-черныйдерево с n узлами, какое наибольшее количество внутренних узлов с высотой черного k?Какое наименьшее число?
Я пытался думать об этом уже более двух часов, но кроме головной боли я не мог никуда добраться.
Спасибо!