2-3-4 – Деревья (стр. 2 )

 

B B

В RB: 3-узел

B R

 

R R B B

 

3в)

3 4

В 2-3-4:

4 2 2

 

B B 4-узел

В RB:

R B R R

R R B B

 

3с) 3 4

 

В 2-3-4 4 2 2

 

В RB: 3-узел

B B B

 

4-узел R разделение 4-узла R 3-узел R R

 

B R 3 B B

R R 1 B 2 B

 

 

3d) 3 4

 

В 2-3-4: 4

 

В RB: B разделение B B B

4-узла

R R R R R

 

B R R B B B

 

R R B B B

 

Два последних случая 3с) и 3d) отличительны тем, что 4-узел подключен к красному узлу

3-узла. Разделение 4-узла приводит к образованию двух 2-узлов и на более высоком уровне – к образованию структуры 3-узла. В дереве образуются две последовательные R-связи, что не может быть 2-3-4 –деревом.

Можно преобразовать такое неправильное дерево так, чтобы эти две связи вели из одного узла, что соответствует 4-узлу, путем вращений.

Если две последовательные R-связи ориентированы одинаково (3с), то выполняем ротацию корня неправильного дерева и изменяем цвета узлов.

Если две R-связи ориентированы по-разному (3d), то сначала путем ротации верхнего R-узла сводим связи к одинаковой ориентации, а затем выполняем ротацию, аналогичную случаю 3с).

Для реализации RB-дерева в структуру узла вводим дополнительный параметр – цвет color, который может быть равен RED(1) или BLACK(0) и вспомогательную функцию проверки цвета узла.

Red(t)

1 t-узел RB-дерева

2 if t=nil then return BLACK

3 return color(t)

Главная функция вставки в RB-дерево выглядит так:

RB_Insert(t, x)

1 t-корень RB-дерева

2 x-новый узел

3 t RB_Insert1(t, x,0)

4 color [t] BLACK

5 return t

Вызов этой функции: root RB_Insert(root, x)

RB_Insert1(t, x,s)

1 t-корень дерева/поддерева

2 x-новый узел

3 s - тип родителя(левый-0/правый-1)

4 if t=nil then color[x] RED

5 return x

6 if Red(left[t]) & Red(right[t])

7 then разделение

8 color[t] RED

9 color[left[t]] color[right[t]] BLACK

10 if key[x]<key[t] R(t)

11 then left[t] RB_Insert1(left[t],x,0) R t R

12 if Red(t) & Red(left[t]) & s=1

13 then t R(t) R R t

14 if Red(left[t]) & Red(left[left[t]]) R(t)

15 then t R(t) t R

16 color[t] BLACK left[t]

17 color[right[t]] RED R B

18 else right[t] RB_Insert1(right[t],x,1)

19 if Red(t) & Red(right[t]) & s=0 B R R t

20 then t L(t)

21 if Red(right[t]) & Red(right[right[t]]) L(t)

22 then t L(t) R t R

23 color[t] BLACK

24 color[left[t]] RED R t R

25 return t B t

 

R B

 

R t R R

 

Рассмотрим, как строится RB-дерево при последовательном включении элементов.

 

RB-дерево 2-3-4 - дерево

 

1 1 1

 

19 1

1 19

19

1 1 5

5

1 5 19

5 19

5 R 5 5

 

1 19