49
правок
Изменения
Нет описания правки
# На каждой ветви дерева, идущей от корня к листу, число чёрных узлов одно и то же.
При этом все листья дерева являются фиктивными и не содержат данных. Число чёрных узлов между корнем и узлом называется '''чёрной высотой дерева.'''
==Свойства==
# Число листьев в дереве с чёрной высотой h не менее, чем <tex>2^{h-1}</tex>.
Докажем по индукции. При h = 1 получаем дерево, в котором чёрными являются только листья, а их больше одного.
Иначе пусть корень - чёрный, тогда оба его поддерева имеют чёрную высоту h-1 и, следовательно, не менее, чем <tex>2^{h-2}</tex> элементов. Тогда всё дерево имеет более <tex>2^{h-1}</tex> элементов. В случае, если корень красный, то оба его поддерева имеют чёрные корни и чёрную высоту h, то есть, как только что было показано, не менее <tex>2^{h-1}</tex> элементов. Таким образом, дерево будет иметь более <tex>2^{h}</tex> элементов.
