Структуры данных и модели вычислений

         

Комбинаторные свойства красно-черных деревьев


Для произвольного узлаопределим черную высотукак количество черных узлов на пути из в некоторый лист, не считая сам узел . По свойству 4 эта сумма не зависит от выбранного листа. Черной высотой дерева будем считать черную высоту его корня.

Пусть— количество внутренних узлов в поддереве с корнем({\rm nil}-узлы не считаются).

Лемма 1.

Для произвольного узла красно-черного дерева выполняется неравенство .

Доказательство.

Если— лист, тои, следовательно, утверждение леммы выполнено. Далее, пусть для узлови утверждение леммы справедливо, то есть

тогда

Предпоследнее неравенство справедливо в силу соотношения

Лемма 2.

Красно-черное дерево свнутренними узлами-листья не считаютсяимеет высоту не больше .

Доказательство.

Обозначим высоту дерева через . Согласно свойству 3, по меньшей мере половину всех вершин на пути от корня к листу, не считая корень, составляют черные вершины. Следовательно, черная высота дерева не меньше . Тогда и, переходя к логарифмам, получаем или . Лемма доказана.

Полученная оценка высоты красно-черных деревьев гарантирует выполнение операций,,,и с красно-черными деревьями за время. Сложнее обстоит дело с процедурамии: проблема в том, что они могут испортить структуру красно-черного дерева, нарушив RB-свойства. Поэтому описанные процедуры придется модифицировать. Ниже увидим, как можно реализовать их за времяс сохранением RB-свойств.



Содержание  Назад  Вперед