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

R B

или

B B R

 

R R y

x R x

 

Если дядя нового узла y-красный, то восстановление свойства в области включения сводится к перекраске родителя и дяди в черный цвет, а деда – в красный. Перекраска не меняет черной высоты дерева.

Но теперь может быть нарушено 3-е свойство выше по дереву.

Случаи 2 и 3 соответствуют конфигурации, когда у красного узла x родитель красный, но дядя - черный.

Случай 2 имеет дело с конфигурацией, когда x имеет правую (левую) ориентацию, а родитель – левую (правую) ориентацию, то есть разные ориентации в дереве.

Случай 2 Случай 3

P[x]

P[x] перекраска

X дед

y

 

x

 

В случае 2 используем левый поворот родителя узла x, чтобы свести случай 2 к случаю 3.

В случае 3 делаем правый поворот деда узла x и перекраску: опущенный дед перекрашивается в красный цвет, а поднятый родитель – в черный цвет.

It_RB_Insert(t, x)

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

2 x-новый/красный узел

3 t BST_Insert(t, x)

4 color[x] RED

5 while x=t & color[p[x]]=RED

6 do if p[x]=left[p[p[x]]]

7 then y right[p[p[x]]]

8 if color[y]=RED случай 1

9 then color[p[x]] color[y] BLACK

10 color[p[p[x]]] RED

11 x p[p[x]]

12 else if x=right[p[x]] случай 2

13 then x p[x]

14 It_L(t, x)

15 color[p[x]] BLACK случай 3

16 color[p[p[x]]] RED

17 It_R(t, p[p[x]])

18 else симметричный текст с заменой left на right

19 color[t] BLACK

20 return t

Моделирование показало, что если встречается случай 2 , то выполняется не более 2-х вращений, при случае 3 – не более одного вращения.

УДАЛЕНИЕ ИЗ RB – ДЕРЕВА

Удаление из RB-дерева также требует О(log n) времени. Удаление вершины несколько сложнее включения. Для упрощения программирования операции удаления в RB-дерево вводится фиктивный элемент NIL, который будет использоваться вместо ссылок nil в терминальных узлах дерева. Все терминальные узлы, не имеющие сыновей или одного сына, вместо nil имеют ссылку на фиктивный элемент NIL. Фиктивный элемент, как и все узлы имеет поля p и color. Цвет фиктивного элемента всегда черный.

Благодаря фиктивному узлу все реальные узлы всегда внутренние.

Операция RB_Delete работает также, как и операция BST_Delete. Но после удаления вершины, если она черная, вызывается дополнительная операция RB_Fixup, которая восстанавливает нарушенное четвертое свойство RB-дерева («верная высота всех путей в RB-дереве одинакова»). Восстановление ведется путем перекрашивания узлов и вращений на пути поиска удаляемого элемента.

It_RB_Delete(t, x)

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

2 x-удаляемый узел

3 if left[x]=NIL or right[x]=NIL

4 then y x y-удаляемый узел

5 else y BST_Successor(t, x) поиск самого левого узла в правом поддереве x

6 if left[y]=NIL

7 then z left[y] z-сын удаляемого узла, возможно NIL

8 else z right[y]

9 вырезание узла y

10 p[z] p[y]

11 if p[y]=NIL y-корень

12 then t z

13 else if y=left[p[y]]

14 then left[p[y]] z

15 else right[p[y]] z

16 if y=x y-замещающий узел

17 then key[x] key[y]

18 data[x] data[y]

19 delete y

20 if color[y]=BLACK

21 then RB_Fixup(t, z)

22 return t

Если удаляемый узел y-красный, то 4-е свойство RB-дерева не нарушается и операция удаления на этом завершается.

Если удалена черная вершина, то выполняется операция RB_Fixup для сына удаленного узла y – z. Сыном удаленного узла может быть либо его единственный левый или правый сын, либо фиктивный узел NIL, причем в этот момент p[z] или p[NIL] указывают на родителя удаленного узла y.

При восстановлении 4-го свойства RB-дерева операция RB_Fixup рассматривает следующие случаи:

1) p[y] p[y] Если узел z- красный, то он перекрашивается в черный цвет и

операция RB_Fixup заканчивается.

z

R z B

 

NIL NIL NIL NIL

2) p[y] p[y] Если узел z – черный, то ему отдается чернота удаленного

родителя, то есть узел z становится дважды черным.

z B z BB

 

NIL NIL NIL NIL

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

Если z – корень всего RB-дерева, то лишняя чернота просто удаляется из корня. Иначе выполняется циклическая перестройка узлов, лежащих на пути от корня к z путем перекрашивания и вращений.

Перестройка учитывает 4 возможных конфигурации, которые могут встретится на пути.

Случай 1:брат узла с двойной чернотой - красный

 

P[y] B B В этом случае вращаем родителя узла z, чтобы

получить конфигурацию, при которой у z

Z BB R w R B будет черный брат.

 

a b B B z BB B e f

новый w

c d e f a b c d

Получено новое состояние – случай 2, 3 или 4. Черная высота поддеревьев a, b,c, d,e, f не изменилась.

Случай 2: брат узла с двойной чернотой и сыновья брата - черные

 

R/B z B/BB

 

z BB B w B R

 

a b B B a b B B

c d e f c d e f

Брат и узел z отдают свою черноту родителю, а брат перекрашивается в красный цвет. Родитель узлов z и w становится черным или дважды черным. Если родитель был красным, то перестройка завершается, если родитель был черным, то перестройка переносится на один уровень вверх. Высота поддеревьев a, b,c, d,e, f не изменилась.

Случай 3: брат узла z – черный, левый сын брата – красный, а правый сын брата - черный

R/B

 

z BB B w

 

a b R B

 

c d e f

Перекрасить брата как в случае 2 нельзя, так как нарушается 3-е свойство для брата.

В этом случае применяется вращение брата вправо и перекрашивание левого сына в черный, а опущенного брата – в красный. Высота поддеревьев a, b,c, d,e, f не изменилась.

 

R/B

z B BB w

a b c R

 

d B

 

e f

Получаем случай 4 (он возможен и в исходном дереве), когда левый сын красный или черный, а правый брат – красный.

 

R/B R/B

z BB B w B B

 

a b R/B R z B R/B e f

 

c d e f a b c d

Произведем вращение родителя p[z] и перекрасим вершины. В случае перестройка завершается.

RB_Fixup(t, z)

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

2 z-узел с двойной чернотой

3 while z=t & color[z]=BLACK

4 do if z=left[p[z]]

5 then w right[p[z]]

6 if color[w]=RED случай 1

7 then color[w] BLACK

8 color[p[z]] RED

9 It_L(t, p[z]) вращение влево родителя

10 w right[p[z]]

11 if color[left[w]]=BLACK & color[right[w]]=BLACK

12 then color[w] RED случай 2

13 z p[z]

14 else if color[right[w]]=BLACK

15 then color[left[w]] BLACK случай 3

16 color[w] RED

17 It_R(t, w)

18 w right[p[z]]

19 случай 4

20 color[w] color[p[z]]

21 color[p[z]] BLACK

22 color[right[w]] BLACK

23 It_L(t, p[z])

24 z t для прекращения цикла

25 else

26 симметричный фрагмент для правого поддерева

27 с заменой left на right

28 color[z] BLACK если z – красный узел или z-корень