Red-Black Tree Proof

Question

У меня есть вопрос по моему окончательному обзору, который говорит. Докажите, что n> 1, красно-черное дерево должно иметь по крайней мере 1 красный узел. Это имеет смысл для меня, поскольку, если n четно, 2 поддеревья из корня имеют разное количество узлов, поэтому должно быть хотя бы один красный цвет, чтобы все пути имели ту же самую черную высоту. Тогда есть еще одна проблема, которая говорит, что минимальные внутренние узлы дерева с черной высотой k равны 2^k -1. Доказательство этого состоит в том, что если каждый узел был черным, то полное бинарное дерево, считая, что фиктивные внешние листья подсчитаны, будет иметь высоту k и включение этого в формулу 2^h -1 дает нам ответ.

Моя проблема заключается в том, как первое доказательство может совпадать со вторым. Как дерево с более чем одним узлом должно иметь как минимум 1 красный узел, но минимальное внутреннее дерево узлов имеет только черные узлы. Может ли кто-нибудь просветить меня, пожалуйста?

Answer 1

Первое доказательство основано на его алгоритме вставки, поэтому всегда есть красный узел. Но во втором случае вы можете построить дерево Red-Black, состоящее только из черного. При использовании обычно используемого алгоритма вставки вы всегда получаете красный цвет при вставке.

Я вставляю это как ответ в случае, если кто-то имеет такую ​​же проблему или знает более точное слово для использования в качестве aswer.

Чтения материал: http://www.geeksforgeeks.org/red-black-tree-set-2-insert/