Изменения

Перейти к: навигация, поиск

Красно-черное дерево

227 байт добавлено, 19:16, 24 марта 2012
Высота красно-черного дерева
|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>.
98
правок

Навигация