Анализ вычислительной сложности алгоритмов (стр. 6 )

5 R 5 5

 

1 19

 

18 18

 

3 5 5

 

1

 

3 18

 

5 5 5

8

18 19

 

3

8

 

 

1

 

3 8 19

9

 

14

1

 

 

9 8 14

 

14

 

 

1

 

84 19

 

8

7

 

24 9 R 9 9

5

 

9 24

 

 

Алгоритм вставки в красно-черное дерево гарантирует логарифмическую эффективность для поисков и включений. В худшем случае, когда путь поиска состоит из чередующихся 3- и

4-узлов, требуется 2logn+2 шагов. Анализ и моделирование RB-деревьев с n узлами, построенных из случайных ключей, показали, что эффективность имеет оценку 1.002logn. В этом смысле RB-деревья оптимальны для практического применения и часто включаются в библиотеки. При реализации алгоритма часто используется альтернативный подход при рассмотрении RB-дерева, как дерева с определенными структурными свойствами. При этом игнорируется соответствие с 2-3-4- деревом.

RB-дерево, как структура обладает следующими RB-свойствами:

1)  Каждый узел либо красный, либо черный.

2)  Каждый лист – черный.

3)  Если узел красный, то оба его сына – черные.

4)  Все пути, ведущие вниз от корня к листьям, содержат одинаковое количество черных узлов, то есть все пути имеют одинаковую черную высоту.

5)  Корень – черный.

Вставка и удаление из RB-дерева могут нарушать 3) и 4) свойства дерева. В этом случае используется балансировка, заключающаяся в восстановлении RB-свойств на пути поиска узла. Восстановление сводится к восходящей перекраске узлов и ротациям.

Рассмотрим реализацию алгоритмов вставки и удаления узлов в итеративном алгоритме (Кормен, Лейзерсон…).

Поскольку управление стеком в RB-дереве становится довольно сложным, то вместо стека введем в структуру каждого узла указатель на родителя. Итак, узел RB-дерева содержит помимо данных 3 указателя на сыновей и родителя (p[t]) и цвет color[t].

В связи с введением дополнительного указателя p[t], перепишем операцию ротации узла. It_L(t, x);

ВКЛЮЧЕНИЕ В RB – ДЕРЕВО

Новый узел включается в дерево как красный лист. Ссылка nil всегда считается черным псевдолистом. Часто для удобства программирования nil заменяется ссылкой на общий для всех фиктивный черный узел-лист.

При вставке может быть нарушено третье свойство RB-дерева и требуется балансировка для восстановления свойства. При этом возможны три случая конфигурации дерева в области включения нового элемента x.

Случай 1

 

B

перекраска

R B

или