бесконечное количество максимально неуравновешенных красных черных деревьев

Question

Мне нужно найти семью максимально неуравновешенных красно-черных деревьев и доказать «соответствующие атрибуты» этого семейства, чтобы доказать, что существует бесконечно большое семейство красных черных деревьев, которые имеют высота, близкая к 2log (n + 1).

Теперь я предполагаю, что это семейство состоит в основном из всех красных черных деревьев, у которых есть один путь с узлами s-r-s-r ... и остальное заполнено черными узлами. Но как мне это доказать? и как я официально записываю, как выглядит такая семья?

Спасибо!

Answer 1

Теперь я предполагаю, что это семейство состоит в основном из всех красных черных деревьев, которые имеют один путь с узлами s-r-s-r ... и остальные заполнены черными узлами.

Это разумное предположение.

Но как это доказать?

описать бесконечную последовательность деревьев T_0, Т_1, И_2, T_3, ..., такие, что для любого целого п существует дерево в последовательности с по меньшей мере п узлов. Покажите, что существует константа C такая, что для каждого i высота T_i составляет не менее 2 log (n_i + 1) - C, где n_i - количество узлов в T_i. (Это одна из возможных интерпретаций двусмысленного термина «близко к».)

Как я могу официально записать, как выглядит такая семья?

Индуктивно. Я приведу все-черные деревья в качестве примера. Дерево T_0 пусто (базовый регистр). Для всех целых чисел i> 0 дерево T_i состоит из черного узла с левым и правым поддеревьями, равным T_ {i-1} (индуктивный шаг). Затем вы можете доказать факты об этих деревьях, используя индукцию.