98
правок
Изменения
Нет описания правки
||proof=
'''1.Лемма''' Совмещаем все красные узлы . В красно-черном дереве с родительскими чёрными (они существуют по свойству черной высотой <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> и, по лемме, 3 или 4 потомкаколичество внутренних вершин в дереве
<tex>\log(N+1) \geqslant h/2</tex>
<tex>h \leqslant 2\log(N+1)</tex>
}}
