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