98
правок
Изменения
Нет описания правки
[[Файл:RBT.jpg|350px|thumb|Пример красно-чёрного дерева.]]'''Красно - чёрное дерево''' - самобалансирующееся двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" и "чёрный". При этом дерево должно удовлетворять следующим свойствам:# Все листья дерева чёрные.# Корень дерева чёрный.# Все сыновья красного узла чёрные.# На каждой ветви дерева, идущей от корня к листу, число чёрных узлов одно и то же.
При этом все листья дерева являются фиктивными и не содержат данных. Число чёрных узлов между корнем и узлом называется '''чёрной высотой дерева.'''
==Свойства==
* '''Свойство 1: '''Число листьев в дереве с высотой <tex>h</tex> не менее, чем <tex>2^{h-1}</tex>.<br/>
'''Доказательство: '''Докажем по индукции. При <tex>h=1</tex> получаем дерево, в котором чёрными являются только листья, а их больше одного.
