Структуры данных и модели вычислений
Комбинаторные свойства красно-черных деревьев
Для произвольного узлаопределим черную высотукак количество черных узлов на пути из в некоторый лист, не считая сам узел . По свойству 4 эта сумма не зависит от выбранного листа. Черной высотой дерева будем считать черную высоту его корня.
Пусть— количество внутренних узлов в поддереве с корнем({\rm nil}-узлы не считаются).
Лемма 1.
Для произвольного узла красно-черного дерева выполняется неравенство .
Доказательство.
Если— лист, тои, следовательно, утверждение леммы выполнено. Далее, пусть для узлови утверждение леммы справедливо, то есть
тогда
Предпоследнее неравенство справедливо в силу соотношения
Лемма 2.
Красно-черное дерево свнутренними узлами-листья не считаютсяимеет высоту не больше .
Доказательство.
Обозначим высоту дерева через . Согласно свойству 3, по меньшей мере половину всех вершин на пути от корня к листу, не считая корень, составляют черные вершины. Следовательно, черная высота дерева не меньше . Тогда и, переходя к логарифмам, получаем или . Лемма доказана.
Полученная оценка высоты красно-черных деревьев гарантирует выполнение операций,,,и с красно-черными деревьями за время. Сложнее обстоит дело с процедурамии: проблема в том, что они могут испортить структуру красно-черного дерева, нарушив RB-свойства. Поэтому описанные процедуры придется модифицировать. Ниже увидим, как можно реализовать их за времяс сохранением RB-свойств.
