Oberon space
General Category => Общий раздел => Тема начата: ilovb от Ноябрь 15, 2013, 06:29:37 pm
-
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;
-
Зависит от того, что надо было сделать. Если я правильно понимаю, то они делают разные вещи.
-
Может быть я где накололся... Но вообще это один и тот же алгоритм
-
Делают, вроде, одно и то же, но оба читать тяжело.
Я бы предложил выкинуть оба варианта и написать третий, где в именах переменных отражался бы уровень дерева:
PROCEDURE RotateLeft (tree: Tree; n1: Node);
n2Right
n3Left
n0
Или типа того.
-
Может быть я где накололся... Но вообще это один и тот же алгоритм
Да, это я ошибся
-
А во втором варианте комменты "before" и "after" ясности не добавляют?
-
Добавляют.
-
Еще вопрос:
А если бы код читался после статьи: http://www.rsdn.ru/article/alg/binstree.xml#EAJAC
и разглядывания картинки: (http://www.rsdn.ru/article/alg/binstree/image5.gif)
Какой вариант было бы легче понять?
ps Второй вариант я написал в попытках сделать код яснее. Лично мне комменты дают всю необходимую информацию для понимания. Но беда в том, что автор этих комментов я... Вот хотелось узнать мнение со стороны.
-
Что показывают комментарии, я самостоятельно разобрался. Но далеко не сразу.
-
Обычно проще проверять соответствия кода ожиданиям, чем разбираться в его смысле, вроде как второй вариант более подходит для этого
-
Еще пример переписывания:
Исходный вариант:
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;
-
Разбор случаев при вставке хорошо разобран тут: Красно-чёрное дерево (http://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D1%91%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE#.D0.92.D1.81.D1.82.D0.B0.D0.B2.D0.BA.D0.B0)
-
Лохонулся таки в 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 Второй вариант ближе к исходному, чем первый.
-
Вообще, кстати, исходный вариант (который гуляет в интернетах) это 1:1 код из алгоритмов Кормена.
Еще предостережение, для тех, кто читает http://www.ozon.ru/context/detail/id/18319699/
Там описывается другой вариант красно-черного дерева (AA дерево), и код соответственно другой.
Еще можно встретить реализацию без поля parent. Это нормально, т.к. родитель нужен только для последовательного обхода дерева (в порядке возрастания/убывания ключей)
Если обход не нужен, то код для вставки/удаления/поиска можно написать через рекурсию.