98
правок
Изменения
Нет описания правки
{{Теорема
|statement=Красно-чёрное дерево с <tex>n</tex> ключами имеет высоту <tex>h \geqslant \log(n + 1) = O(\log n)</tex>.
||proof=Схема доказательства:
'''1. ''' Совмещаем все красные узлы с родительскими чёрными (они существуют по свойству 2) начиная с корня
'''2. ''' В результате получим дерево, каждый узел котрого имеет 2, 3 или 4 потомка
'''3. ''' В следствии свойства 4 красно-чёрного дерева, все листья 2-3-4 дерева будут иметь одинаковую глубину – black-height корня исходного дерева
'''4. ''' Пусть дерево из п.2 имеет высоту <tex>h'</tex>. Тогда <tex>h' \geqslant h/2</tex>, т.к. не более половины узлов на каждом пути – красные
'''5. ''' Количество листьев не изменяется и равно <tex>n + 1</tex> для обоих деревьев, т.к. в красно-чёрном дереве все внутренние узлы имеют ровно два листа
'''6. ''' В 2-3-4 дереве высоты <tex>h'</tex> количество листьев <tex>n + 1</tex> ограничено:
<tex>2^{h'} \leqslant n + 1 \leqslant 4^{h'}</tex>
'''7. ''' Тогда:
<tex>n + 1 \geqslant 2^{h'}</tex>
