Какой код лучше?

[ilovb]

Код: [Выделить]

PROCEDURE RotateLeft (tree: Tree; node: Node);
   VAR
      temp: Node;
BEGIN

   temp := node.right;
   node.right := temp.left;
   
   IF temp.left # NIL THEN
      temp.left.parent := node;
   END;
   
   temp.parent := node.parent;
   
   IF node.parent = NIL THEN
      tree.root := temp;
   ELSIF node = node.parent.left THEN
      node.parent.left := temp;
   ELSE
      node.parent.right := temp;
   END;
   
   temp.left := node;
   node.parent := temp;
   
END RotateLeft;

Код: [Выделить]

PROCEDURE RotateLeft (tree: Tree; a: Node);
   VAR
      b, c, p: Node;
     
BEGIN
   
   p := a.parent;
   c := a.right;
   b := c.left;
   
   (* before:
      p
      a
          c
        b
     
   *)
   
   c.parent := p;
   a.parent := c;
   
   IF p = NIL THEN (* a = tree.root *)
      tree.root := c;
   ELSE
      IF p.right = a THEN
         p.right := c;
      ELSE
         p.left := c;
      END;
   END;
   
   c.left  := a;
   a.right := b;
   
   IF b # NIL THEN
      b.parent := a;
   END;
         
   (* after:
          p
          c
      a
        b
     
   *)
   
END RotateLeft;

[Valery Solovey]

Зависит от того, что надо было сделать. Если я правильно понимаю, то они делают разные вещи.

[ilovb]

Может быть я где накололся... Но вообще это один и тот же алгоритм

[Valery Solovey]

Делают, вроде, одно и то же, но оба читать тяжело.

Я бы предложил выкинуть оба варианта и написать третий, где в именах переменных отражался бы уровень дерева:

PROCEDURE RotateLeft (tree: Tree; n1: Node);

n2Right
n3Left
n0

Или типа того.

[Valery Solovey]

Может быть я где накололся... Но вообще это один и тот же алгоритм

Да, это я ошибся

[ilovb]

А во втором варианте комменты "before" и "after" ясности не добавляют?

[Valery Solovey]

Добавляют.

[ilovb]

Еще вопрос:
А если бы код читался после статьи: http://www.rsdn.ru/article/alg/binstree.xml#EAJAC
и разглядывания картинки:

Какой вариант было бы легче понять?

ps Второй вариант я написал в попытках сделать код яснее. Лично мне комменты дают всю необходимую информацию для понимания. Но беда в том, что автор этих комментов я... Вот хотелось узнать мнение со стороны.

[Valery Solovey]

Что показывают комментарии, я самостоятельно разобрался. Но далеко не сразу.

[adva]

Обычно проще проверять соответствия кода ожиданиям, чем разбираться в его смысле, вроде как второй вариант более подходит для этого

[ilovb]

Еще пример переписывания:

Исходный вариант:

Код: [Выделить]

PROCEDURE InsertFixup (tree: Tree; node: Node);
   VAR
      temp: Node;
BEGIN
   
   node.color := red;
   
   WHILE (node # tree.root) & (node.parent.color = red) DO
      IF node.parent = node.parent.parent.left THEN
         temp := node.parent.parent.right;
         IF (temp # NIL) & (temp.color = red) THEN
            node.parent.color := black;
            temp.color := black;
            node.parent.parent.color := red;
            node := node.parent.parent;
         ELSE
            IF node = node.parent.right THEN
               node := node.parent;
               RotateLeft(tree, node);
            END;
            node.parent.color := black;
            node.parent.parent.color := red;
            RotateRight(tree, node.parent.parent);
         END;
         
      ELSE
         temp := node.parent.parent.left;
         IF (temp # NIL) & (temp.color = red) THEN
            node.parent.color := black;
            temp.color := black;
            node.parent.parent.color := red;
            node := node.parent.parent;
         ELSE
            IF node = node.parent.left THEN
               node := node.parent;
               RotateRight(tree, node);
            END;
            node.parent.color := black;
            node.parent.parent.color := red;
            RotateLeft(tree, node.parent.parent);
         END;
         
      END;
   END;
   
   tree.root.color := black;
   
END InsertFixup;Модифицированный:

Код: [Выделить]

PROCEDURE InsertFixup (tree: Tree; node: Node);
   VAR
      parent, uncle, grandad: Node;
BEGIN
   
   node.color := red;

   WHILE (node # tree.root) & (node.parent.color = red) DO
     
      (* grandad # NIL *)
     
      parent  := node.parent;
      grandad := parent.parent;
     
      grandad.color := red;
     
      IF parent = grandad.left THEN
         
         uncle := grandad.right;
         
         IF (uncle # NIL) & (uncle.color = red) THEN
           
            parent.color := black;
            uncle.color  := black;
            node := grandad; (* move up *)

         ELSE (* uncle.color = black *)
           
            (* preparation for the right rotation *)
            IF node = parent.right THEN (* parent.right.color = red*)
               RotateLeft(tree, parent);
            ELSE
               node := parent; (* move up *)
            END;
            (* node = grandad.left *)
           
            RotateRight(tree, grandad); (* node = grandad.parent *)
           
            node.color := black;
           
         END;
         
      ELSE (* parent = grandad.right *)
         
         uncle := grandad.left;
         
         IF (uncle # NIL) & (uncle.color = red) THEN
           
            parent.color := black;
            uncle.color  := black;
            node := grandad; (* move up *)

         ELSE (* uncle.color = black *)
           
            (* preparation for the left rotation *)
            IF node = parent.left THEN (* parent.left.color = red *)
               RotateRight(tree, parent);
            ELSE
               node := parent; (* move up *)
            END;
            (* node = grandad.right *)
           
            RotateLeft(tree, grandad); (* node = grandad.parent *)
           
            node.color := black;
           
         END;
         
      END;
   END;
   
   tree.root.color := black;
   
END InsertFixup;

[ilovb]

Разбор случаев при вставке хорошо разобран тут: Красно-чёрное дерево

[ilovb]

Лохонулся таки в InsertFixup.
В условии цикла нужно добавить еще одно ограничение (node.color = red):

Код: [Выделить]

PROCEDURE InsertFixup (tree: Tree; node: Node);
   VAR
      parent, uncle, grandad: Node;
BEGIN
   
   node.color := red;

   WHILE (node # tree.root) & (node.color = red) & (node.parent.color = red) DO
     
      parent  := node.parent;
      grandad := parent.parent;  (* grandad # NIL *)
     
      grandad.color := red;
     
      IF parent = grandad.left THEN
         
         uncle := grandad.right;
         
         IF (uncle # NIL) & (uncle.color = red) THEN
           
            parent.color := black;
            uncle.color  := black;
            node := grandad; (* move up *)

         ELSE (* uncle.color = black *)
           
            (* preparation for the right rotation *)
            IF node = parent.right THEN (* parent.right.color = red *)
               RotateLeft(tree, parent);
            ELSE
               node := parent; (* move up *)
            END;
            (* node = grandad.left *)
           
            RotateRight(tree, grandad); (* node = grandad.parent *)
           
            node.color := black;
           
         END;
         
      ELSE (* parent = grandad.right *)
         
         uncle := grandad.left;
         
         IF (uncle # NIL) & (uncle.color = red) THEN
           
            parent.color := black;
            uncle.color  := black;
            node := grandad; (* move up *)

         ELSE (* uncle.color = black *)
           
            (* preparation for the left rotation *)
            IF node = parent.left THEN (* parent.left.color = red *)
               RotateRight(tree, parent);
            ELSE
               node := parent; (* move up *)
            END;
            (* node = grandad.right *)
           
            RotateLeft(tree, grandad); (* node = grandad.parent *)
           
            node.color := black;
           
         END;
         
      END;
   END;
   
   tree.root.color := black;
   
END InsertFixup;
И еще одна вариация на тему (чтобы не менять условие цикла):

Код: [Выделить]

PROCEDURE InsertFixup (tree: Tree; node: Node);
   VAR
      parent, uncle, grandad: Node;
BEGIN
   
   node.color := red;

   WHILE (node # tree.root) & (node.parent.color = red) DO
     
      parent  := node.parent;
      grandad := parent.parent; (* grandad # NIL *)
     
      grandad.color := red;
     
      IF parent = grandad.left THEN
         
         uncle := grandad.right;
         
         IF (uncle # NIL) & (uncle.color = red) THEN
           
            parent.color := black;
            uncle.color := black;
            node := grandad; (* move up *)
            (* node.color = red *)
           
         ELSE (* uncle.color = black *)
           
            (* preparation for the right rotation *)
            IF node = parent.right THEN (* parent.right.color = red *)
               RotateLeft(tree, parent); (* parent = node.left *)
               node.color := black;
               node := parent; (* move down *)
            ELSE
               parent.color := black;
            END;
            (* node.color = red *)
            (* node.parent.color = black *)
           
            RotateRight(tree, grandad);
           
         END;
         
      ELSE (* parent = grandad.right *)
         
         uncle := grandad.left;
         
         IF (uncle # NIL) & (uncle.color = red) THEN
           
            parent.color := black;
            uncle.color  := black;
            node := grandad; (* move up *)
            (* node.color = red *)
           
         ELSE (* uncle.color = black *)
           
            (* preparation for the left rotation *)
            IF node = parent.left THEN (* parent.left.color = red *)
               RotateRight(tree, parent); (* parent = node.right *)
               node.color := black;
               node := parent; (* move down *)
            ELSE
               parent.color := black;
            END;
            (* node.color = red *)
            (* node.parent.color = black *)
           
            RotateLeft(tree, grandad);
           
         END;
         
      END;
   END;
   
   tree.root.color := black;
   
END InsertFixup;
ps Второй вариант ближе к исходному, чем первый.

[ilovb]

Вообще, кстати, исходный вариант (который гуляет в интернетах) это 1:1 код из алгоритмов Кормена.

Еще предостережение, для тех, кто читает http://www.ozon.ru/context/detail/id/18319699/
Там описывается другой вариант красно-черного дерева (AA дерево), и код соответственно другой.

Еще можно встретить реализацию без поля parent. Это нормально, т.к. родитель нужен только для последовательного обхода дерева (в порядке возрастания/убывания ключей)
Если обход не нужен, то код для вставки/удаления/поиска можно написать через рекурсию.