Изменения

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

227 байт убрано, 21:34, 24 марта 2012

→‎Высота красно-черного дерева

|statement=Красно-чёрное дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.

||proof=

Будем называть чёрной высотой вершины <tex>x</tex> число чёрных вершин на пути из <tex>x</tex> в лист, не учитывая саму вершину <tex>x</tex>.

В красно-черном дереве с черной высотой <tex>hb</tex> количество внутренних вершин не менее <tex>2^{hb+1}-1</tex>.

98

правок