49
правок
Изменения
→Свойства
При этом все листья дерева являются фиктивными и не содержат данных. Число чёрных узлов между корнем и узлом называется '''чёрной высотой дерева.'''
==Свойства==
* '''Свойство 1: '''Число листьев в дереве с чёрной высотой <tex>h</tex> не менее, чем <tex>2^{h-1}</tex>.<br/>
'''Доказательство: '''Докажем по индукции. При <tex>h=1</tex>получаем дерево, в котором чёрными являются только листья, а их больше одного.
Иначе пусть корень - чёрный, тогда оба его поддерева имеют чёрную высоту h-1 и, следовательно, не менее, чем <tex>2^{h-2}</tex> элементов. Тогда всё дерево имеет более <tex>2^{h-1}</tex> элементов. В случае, если корень красный, то оба его поддерева имеют чёрные корни и чёрную высоту <tex>h</tex>, то есть, как только что было показано, не менее <tex>2^{h-1}</tex> элементов. Таким образом, дерево будет иметь более <tex>2^{h}</tex> элементов.<br/>
* '''Свойство 2: '''Число листьев в красно-чёрном дереве высоты <tex>h</tex> не менее <tex>2^{(h-1)/2}</tex>.<br/>
'''Доказательство: '''Возьмём самый длинный путь в дереве. Всего в нём <tex>h+1</tex> узлов. По крайней мере половина узлов чёрные, поскольку двух подряд идущих красных узлов быть не может, а лист чёрный. Поэтому чёрная высота дерева не меньше <tex>(h-1)/2</tex>, и, по первому утверждению, <tex>2^{(h-1)/2}</tex> элементов.<br/>
Отсюда также получаем, что высота дерева не более <tex>2log_2 N+1</tex>, где N - число элементов дерева, т.е. <tex>O(log N)</tex>
==Операции==
* '''Вставка элемента.''' Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет nil(т.е. этот сын - лист). Вставляем вместо него новый элемент с nil-потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента красный, то достаточно рассмотреть только два случая:
