Деревья (стр. 3 )

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)

1 t – корень дерева

2 x – вращаемый узел дерева x y

3 y right[x]

4 right[x] left[y] 1 y x 3

5 if left[y]=nil

6 then p[left[y]] x

7 p[y] p[x]

8 if p[x]=nil

9 then t y

10 else if x=left[p[x]]

11 then left[p[x]] y

12 else right[p[x]] y

13 left[y] x

14 p[x] y

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

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

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

Случай 1

B

перекраска

R B