Красно-чёрное дерево (удалить) — различия между версиями

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

Версия 07:31, 4 апреля 2011

Красно - чёрное дерево - самобалансирующееся двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" и "чёрный". При этом дерево должно удовлетворять следующим свойствам:

  1. Все листья дерева чёрные.
  2. Все сыновья красного узла чёрные.
  3. На каждой ветви дерева, идущей от корня к листу, число чёрных узлов одно и то же.

При этом все листья дерева являются фиктивными и не содержат данных. Число чёрных узлов между корнем и узлом называется чёрной высотой дерева.

Свойства

Свойство 1: Число листьев в дереве с чёрной высотой [math]h[/math] не менее, чем [math]2^{h-1}[/math].
Доказательство: Докажем по индукции. При [math]h=1[/math]получаем дерево, в котором чёрными являются только листья, а их больше одного. Иначе пусть корень - чёрный, тогда оба его поддерева имеют чёрную высоту h-1 и, следовательно, не менее, чем [math]2^{h-2}[/math] элементов. Тогда всё дерево имеет более [math]2^{h-1}[/math] элементов. В случае, если корень красный, то оба его поддерева имеют чёрные корни и чёрную высоту [math]h[/math], то есть, как только что было показано, не менее [math]2^{h-1}[/math] элементов. Таким образом, дерево будет иметь более [math]2^{h}[/math] элементов.
Свойство 2: Число листьев в красно-чёрном дереве высоты [math]h[/math] не менее [math]2^{(h-1)/2}[/math].
Доказательство: Возьмём самый длинный путь в дереве. Всего в нём [math]h+1[/math] узлов. По крайней мере половина узлов чёрные, поскольку двух подряд идущих красных узлов быть не может, а лист чёрный. Поэтому чёрная высота дерева не меньше [math](h-1)/2[/math], и, по первому утверждению, [math]2^{(h-1)/2}[/math] элементов.

Отсюда также получаем, что высота дерева не более [math]2log_2 N+1[/math], где N - число элементов дерева, т.е. [math]O(log N)[/math]