Вставка в красное черное дерево, когда родитель P красный, а дядя U черный - PullRequest
Новая
       51

Вставка в красное черное дерево, когда родитель P красный, а дядя U черный

0 голосов
/ 15 декабря 2018

Это случай 4 в вики , когда вставляется узел в красно-черное дерево.

Как показывает рисунок , узел "U", по-видимому, не равен NIL, поскольку у него есть chlidren.

Но это красно-черное дерево?

Неправильно ли изображение или я что-то упустил?

1 Ответ

0 голосов
/ 19 декабря 2018

Но это красно-черное дерево?

Нет.Это красно-черное дерево после того, как узел был вставлен, в данном случае N. Это все часть процедур по исправлению дерева, так что оно снова, красно-черное дерево.

Изображениене неправильно.

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

В таких псевдоалгоритмических терминах алгоритм имеет вид 

LOOP
   P = PARENT(N)
   IF P == NULL THEN
      'N MUST BE ROOT
      N.COLOUR = BLACK
      RETURN
   ENDIF
   IF P.COLOUR == BLACK THEN
      'FIXUPS HAVE ENDED
      RETURN
   ENDIF
   'NOTE: SINCE PARENT IS RED AND PREVIOUSLY WAS A RED-BLACK TREE THEN
   'GRANDPARENT EXISTS AND MUST BE BLACK AS ROOT NODE IS BLACK
   G = GRANDPARENT(N)
   U = UNCLE(N)
   IF U.COLOUR = RED THEN
       'COLOUR FLIP. BLACK NODE HEIGHT DOES NOT CHANGE
       P.COLOUR = BLACK
       U.COLOUR = BLACK
       G.COLOUR = RED
       'BUT G's PARENT COULD BE RED, SO LOOP AGAIN WITH NEW N BEING G
       N = G
    ELSE
       'PARENT IS RED AND UNCLE IS BLACK
       IF N IS ON INSIDE UNDERNEATH G
           ROTATE OUTWARDS ABOUT P
           N = P
       END IF
       'N IS ON OUTSIDE
       ROTATE ABOUT G TOWARD U
       P.COLOUR = BLACK 'NEW GRANDFATHER
       G.COLOUR = RED   'NEW UNCLE
       'N.COLOUR = RED  'NO CHANGE
       RETURN
    END IF


ENDLOOP
...