Задача на красно-черное дерево

[openspace]

Давайте рассмотрим: кчд такое, что в его вершинках лежат натуральные числа [1..n], найти возможные значения ключа в корне.

Пытался вывести через рекуренты, но получил разнос.

[ИСН]

Вам бы это открыть в математике.
Да, я видел, что Вас там уже закрыли. Так надо же было в математической формулировке.

[venco]

Я бы сначала установил диапазон количества возможных элементов в КЧ дереве определённой глубины (количество чёрных узлов в любом пути к листьям). Очевидно любое количество элементов из этого диапазона реализуемо, что позволяет построить неравенства на количества элементов в левом и правом поддеревьях корня.

[Teletranslator]

Множество возможных значений ключа в корне дерева имеет вид [a , b] (докажите сами).

Задача сводится к поиску левой и правой границы этого диапазона. То есть: нужно взять максимально разбалансированное дерево из N элементов, вычислить число элементов с одной из сторон и вычесть что-то из N.

Вместо N нужно взять N округлённое вверх до ближайшего возможного числа узлов в максимально разбалансированном дереве.

Поправьте меня, если я в чём-то неправ.

[openspace]

Тут без вопросов, что будет промежуток.

А вот получение минимума или максимума из промежутка, уже интереснее. Собственно, именно этот вопрос меня и поставил в тупик.