Как узнать, является ли дерево окрашиваемым (RB Tree)

Question

Есть ли алгоритм, чтобы узнать, является ли дерево раскрашиваемым или нет?Потому что я нашел эту фразу в Википедии:

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

Так, например, принимая на экзамене эти два дерева:

В первом из них самый короткий путь от корня - тот, что слева, и он имеетрасстояние 1 от корня.Самый длинный справа и имеет расстояние 3. Значит, 3 не <= 2 * 1, поэтому дерево слева не раскрашивается, верно?Во втором дереве самый короткий путь занимает 2 узла, а самый быстрый - 2 узла.2 <= 2 * 2, так что я думаю, что это раскраска. </p>

Answer 1

Точно, чтобы узнать, является ли дерево окрашенным или нет, вы должны рассчитывать от корня (исключая его), а затем пройти по самому длинному пути.Тогда у вас будет ответ