Соратники!
Помогите разобраться с решением задачи из Яндекс Блиц 12.
https://m.habr.com/ru/company/yandex/blog/340784/Задача называется «Красно-черные деревья»
Не понимаю приведенный вариант решения.
Ниже приведу цитаты из решения, которые непонятны:
1)
...
Корнем у него может быть любое число i от 1 до N. Тогда в левом поддереве будет содержаться i-1 вершина, а в правом — j=N-i вершин.
...
- здесь непонятно как у красно-черного дерева вершиной может быть любое число i от 1 до N БЕЗ НАРУШЕНИЯ СВОЙСТВ КЧ-ДЕРЕВЬЕВ
Например, если N=5, а i=1, то по приведённой выше логике в левом поддереве будет i-1=0 вершин, а в правом j=5-1=4. Но в кч дереве согласно 2-му свойству
(Каждая вершина либо имеет два потомка, либо является листом (не имеет потомков)
а согласно 5-му свойству
(Количество черных вершин на пути от корня до любого листа дерева одинаково)
Если в левом поддереве 0 узлов, то каким образом в правом поддереве с 4-мя узлами может соблюдаться черная высота равной в левом? Это возможно только если в правом поддереве все вершины красные, но тогда нарушается 4-е свойство кч-деревьев (У красных вершин оба потомка имеют черный цвет)
2)
...
Поскольку нам нужно вычислить количество деревьев с точностью до изоморфизма, достаточно посчитать ответ для i-1 <= j. Если i-1 < j, то прибавим к ответу CountBlack[N][H] произведение числа поддеревьев слева и справа: CountLeft*CountRight. Если же мы строим оба поддерева из одинакового числа элементов (i-1=j), то к результату нужно прибавить CountLeft*(CountLeft+1)/2 вариантов.
...
- откуда могут быть получены такие выводы? Самое главное почему для случае равенства нужно прибавлять CountLeft*(CountLeft+1)/2 ?
3)
...
Следовательно, достаточно рассмотреть черные высоты, не превосходящие H = 2*log(N)*20
...
Откуда взялось 20? В кч-дереве верхнее ограничение черной высоты H = 2*log(N + 1)
https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE#.D0.94.D0.BE.D0.BA.D0.B0.D0.B7.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D1.81.D1.82.D0.B2.D0.BE_.D0.B0.D1.81.D0.B8.D0.BC.D0.BF.D1.82.D0.BE.D1.82.D0.B8.D1.87.D0.B5.D1.81.D0.BA.D0.B8.D1.85_.D0.B3.D1.80.D0.B0.D0.BD.D0.B8.D1.86
