Изменения

Назовем черной высотой дерева с корневой вершиной '''<tex>r''' </tex> максимальное количество черных вершин во всех ветвях, начинающихся в '''<tex>r''' </tex> и заканчивающихся в листьях, не считая саму вершину '''<tex>r'''</tex>. Будем обозначать ее '''<tex>hb(r)'''</tex>. '''Лемма'''. В красно-черном дереве с черной высотой '''<tex>hb''' </tex> количество внутренних вершин не менее <tex>2^{hb+1}-1</tex>. '''Доказательство'''. Если рассмотреть лист (фиктивную вершину), то для нее лемма верна. Рассмотрим внутреннюю вершину '''<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>.Если обычная высота дерева равна '''<tex>h'''</tex>, то черная высота дерева будет не меньше '''<tex>h/2-1''' </tex> и, по лемме, количество внутренних вершин в дереве <tex>N >= 2^{h/2}-1</tex> 

<tex>\log(N+1) >= h/2</tex> <tex>2\log(N+1) >= h</tex> <tex>h <= 2\log(N+1)</tex> Итак, учитывая, что для любого бинарного дерева <tex>h > \log(N)</tex>, получаем, что доказана следующая '''Теорема'''. Для красно-черного дерева, имеющего <tex>N</tex>внутренних вершин, верна следующая оценка для его высоты <tex>h=O(\log(N))</tex>, или, более точно, <tex>\log(N) < h <= 2\log(N+1)</tex>.