Изменения

По индукции докажем, что поддерево любого узла <tex>x</tex> с черной высотой <tex>hb(x)</tex> содержит не менее <tex>2^{hb(x)} - 1</tex> внутренних узлов.

Если высота узла <tex>x</tex> равна <tex>0,</tex> то <tex>x</tex> {{---}} это лист, <tex>hb(x) = 0, </tex> <tex>2^{0} - 1 = 0.</tex>

Пусть наше предположение верно для высот до <tex>h'.</tex> Теперь рассмотрим внутреннюю вершину <tex>x</tex> с двумя потомками, для которой <tex>hb(x)=h'</tex>. Тогда если ее потомок <tex>p</tex> {{---}} черный, то его высота <tex>hb(p)=h'- 1</tex>, а если красный, то <tex>hb(p) = h'</tex>. Но поскольку высота потомка меньше, чем высота узла <tex>x</tex>, для него выполняется индукционное предположение. В таком случае в поддереве узла <tex>x</tex> содержится не менее чем <tex>2^{h'} - 1 + 2^{h'} - 1 + 1 = 2^{h'+1} - 1</tex>.