Изменения
→Высота красно-черного дерева
|statement=Красно-чёрное дерево с <tex>N</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
|proof=
Рассмотрим красно-чёрное дерево с высотой <tex>h.</tex> Так как только черные узлы могут иметь красных детейу красной вершины чёрные дети <tex>(</tex>по свойству <tex>3), то в самом длинном пути от корня до листа </tex> количество красных вершин будет точно не больше половины, поэтому если обычная высота дерева равна <tex>h/ 2. </tex>, то черная высота дерева будет Тогда чёрных вершин не меньше , чем <tex>h/2-1.</tex> и, по По доказанной лемме, количество для количества внутренних вершин в дереве<tex>N</tex> выполняется неравенство:
<tex>N \geqslant 2^{h/2}-1</tex>
