Удаление в красно-черном дереве

Я пытаюсь следовать RB-DELETE-FIXUP в 3-м издании «Введение в алгоритм». У них есть этот код:

RB-DELETE-FIXUP(T, x)
 1 while x != root[T] and color[x] == BLACK
 2     do if x == left[p[x]]
 3           then w = right[p[x]]
 4                if color[w] == RED
 5                   then color[w] = BLACK                        ?  Case 1
 6                        color[p[x]] = RED                       ?  Case 1
 7                        LEFT-ROTATE(T, p[x])                    ?  Case 1
 8                        w = right[p[x]]                         ?  Case 1
 9                if color[left[w]] == BLACK and color[right[w]] == BLACK
10                   then color[w] = RED                          ?  Case 2
11                        x = p[x]                                  ?  Case 2
12                   else if color[right[w]] == BLACK
13                           then color[left[w]] = BLACK          ?  Case 3
14                                color[w] = RED                  ?  Case 3
15                                RIGHT-ROTATE(T, w)              ?  Case 3
16                                w = right[p[x]]                 ?  Case 3
17                         color[w] = color[p[x]]                 ?  Case 4
18                         color[p[x]] = BLACK                    ?  Case 4
19                         color[right[w]] = BLACK                ?  Case 4
20                         LEFT-ROTATE(T, p[x])                   ?  Case 4
21                         x = root[T]                            ?  Case 4
22        else (same as then clause with "right" and "left" exchanged)
23 color[x] = BLACK

Я не могу понять, как балансируется дерево в случае 4. Глядя на это изображение: .gif" rel="nofollow noreferrer">здесь)

Результат для случая 4 не сбалансирован. От D до A высота черного цвета равна 2. И от D до E высота черного цвета равна 1. Что мне здесь не хватает?


data-structures red-black-tree
person darkz9999    schedule 16.05.2014    source источник
comment
Я понятия не имею, и я рассматривал этот вопрос некоторое время. Когда я реализовал дерево RB, я использовал википедию для справки, в которой есть разные случаи. Я продолжу работать над этим и посмотрю, чего мне не хватает.   -  person Justin    schedule 20.05.2014

Ответы (1)


arrow_upward
1
arrow_downward

Чего вам не хватает, так это того, что левая сторона не сбалансирована. Эта подпрограмма вызывается после того, как родитель x был выделен из дерева, и только если родитель был черным. Поскольку дерево было сбалансировано до удаления родителя, мы знаем, что поддерево с корнем в A должно иметь черную высоту, которая на единицу меньше высоты поддерева с корнем в D. Поскольку E изначально красное, а D черное, тогда поддерево с корнем в E должно изначально иметь ту же высоту черного, что и A. После преобразования цвет E теперь черный, поэтому его высота черного теперь на единицу больше, чем у A, так что две стороны дерева действительно сбалансированы.

person Christopher Barber    schedule 30.05.2014