||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>, т.к. не более половины узлов на каждом пути – красные
[[Файл:2-3-4_tree.JPG|350px|]]
# 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>
<tex>h \leqslant 2\log(n + 1)</tex>
}}
== Операции ==
