98
правок
Изменения
→Высота красно-черного дерева
|statement=Красно-чёрное дерево с <tex>n</tex> ключами имеет высоту <tex>h \leqslant 2\log(N+1) = O(\log N)</tex>.
||proof=
Будем называть чёрной высотой вершины <tex>x</tex> число чёрных вершин на пути из <tex>x</tex> в лист, не учитывая саму вершину <tex>x</tex>.
В красно-черном дереве с черной высотой <tex>hb</tex> количество внутренних вершин не менее <tex>2^{hb+1}-1</tex>.
