Изменения

Пусть наше предположение верно для высот до <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} - 1 + 2^{h'-1} - 1 + 1 = 2^{h'+1} - 1</tex>.