Изменения
→Высота красно-черного дерева
|statement= В красно-черном дереве с черной высотой <tex>hb</tex> количество внутренних вершин не менее <tex>2^{hb+1}-1</tex>.
|proof=
По индукции докажем, что поддерево любого узла <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>2^{h'}-1x</tex> вершин, а во всём дереве, соответственно, содержится не менее чем <tex>2^{h'}-1 + 2^{h'}-1 + 1=2^{h'+1}-1</tex>. Следовательно, утверждение верно и для всего дерева.
}}
|statement=Красно-чёрное дерево с <tex>N</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
|proof=
Так как только черные узлы могут иметь красных детей, то в самом длинном пути от корня до листа красных вершин будет точно не больше половины, поэтому если обычная высота дерева равна <tex>h</tex>, то черная высота дерева будет не меньше <tex>h/2-1</tex> и, по лемме, количество внутренних вершин в дереве
