Можем ли мы нарисовать дерево RB с 8 черными узлами и 12 красными узлами?

Question

Я видел похожий вопрос здесь в стеке, но на него не было ответа (ясно).

Я могу попытаться построить такое дерево (8 черных узлов и 12 красных узлов)без аннулирования какого-либо из 5 RB-деревьев (пока я не смог этого сделать);

1. узел красный или черный
2. корень черный
3. Все листья черного цвета
4. Оба потомка каждого красного узла черные
5. Каждый простой путь от данного узла к любому из его дочерних листьев содержит одинаковое количество черных узлов.

Но я действительно заинтересован в более элегантном ответе (кроме как попробовать и посмотреть, работает ли он).

Отредактировано: В случае, когда листья считаются какчерные, очевидно, что такое дерево невозможно построить.Но что делать, если листья не считаются черными узлами (8 нелистовых узлов)

Answer 1

Из правила 3 ​​и 4 следует, что не может быть больше красных, чем черных узлов, так как добавление красных узлов в дерево обязательно добавляет черные узлы.Это если вы считаете листья дерева rb узлами (ваши определения это делают).