#c #algorithm #data-structures
Вопрос:
я читаю книгу Введение в алгоритмы в главе раздел удаление красно-черных деревьев. Они показывают мне код ниже
RB-DELETE(T,z)
1 y = z
2 y-original-color = y:color
3 if z.left == T.nil
4 x = z.right
5 RB-T RANSPLANT .T; ´; ´:right/
6 elseif z.right == T:nil
7 x =z.left
8 RB-T RANSPLANT (z,z.left)
9 else y = Minimum(z.right)
10 y-original-color = y.color
11 x = y.right
12 if y.p == z
13 x.p = y
14 else RB-TRANSPLANT (T,y,y.right)
15 y.right = z.right
16 y.right.p = y
17 RB-TRANSPLANT(T,z,y)
18 y.left = z.left
19 y.left:p = y
20 y.color = z.color
21if y-original-color == BLACK
22 RB-DELETE-Fix-Up(T,x)
это реализация в C
void RedBlack::transplant(ColoredNode* destination, ColoredNode* source)
{
if(destination->parent == centinel)
this->root = source;
else if(destination->parent->left == destination)
destination->parent->left = source ;
else
destination->parent->right = source;
source->parent = destination->parent;
}
void RedBlack::DeleteNode(ColoredNode* node)
{
bool replacementColor = node->black;
ColoredNode* replacement = node ;
ColoredNode* repReplacement = node;
if(node->left == this->centinel amp;amp; node->right == this->centinel)
{
transplant(node , centinel); // IT CHANGES THE CENTINEL PARENT
}
else if(node->left == centinel amp;amp; node->right != centinel)
{
repReplacement = node->right;
this->transplant(node,node->right);
}
else if(node->right == centinel amp;amp; node->left != centinel)
{
repReplacement = node->left ;
this->transplant(node,node->left);
}
else
{
replacement = this->successor(node);
replacementColor = replacement->black; // save the color of replacement ...
repReplacement = replacement->right ;
if(replacement == node->right)
repReplacement->parent = replacement ;
// this line is in case of repRe** == centinel ,centinel->parent == null then the fixup function will fail cause we don't have any path to ancestors ...
else
{
transplant(replacement,repReplacement);
replacement->right = node->right;
node->right->parent = replacement;
}
transplant(node,replacement);
replacement->left = node->left;
node->left->parent = replacement ;
replacement->black = node->isBlack();
}
if(replacementColor) // if the replacement is black ...
this->DeleteNodeFixUp(repReplacement);
}
Также алгоритм исправления удаления :
RB-DELETE-FIXUP (T,x)
1 while x != T.root and x.color == BLACK
2 if x == x.p.left
3 w = x.p.right
4 if w.color == RED // CASE 1
5 w.color = BLACK
6 x.p.color = RED
7 LEFT-ROTATE(T,x.p)
8 w D x.p.right
9 if w.left.color == BLACK and w.right.color == BLACK // CASE 2
10 w.color = RED
11 x = x.p
12 else if w.right.color == BLACK // CASE 3
13 w.left.color D BLACK
14 w.color D RED
15 RIGHT-ROTATE(T,w)
16 w = x.p.right
17 w.color = x.p.color //CASE 4
18 x.p.color = BLACK
19 w.right.color = BLACK
20 LEFT-ROTATE(T, x.p)
21 x = T.root
22 else (same as then clause with “right” and “left” exchanged)
23 x:color D BLACK
my C implementation is :
void RedBlack::DeleteNodeFixUp(ColoredNode* node)
{
ColoredNode *parent = node->parent ;
ColoredNode *sibling = this->centinel ;
while( node != this->root amp;amp; node->isBlack())
{
if(node == parent->left)
{
sibling = parent->right ;
printf("node = %d , parent =%d ,sibling = %d n",node->data,parent->data,sibling->data);
if(sibling->isRed())
{
printf("sibling is redn");
parent->black = false;
sibling->black = true;
node->black = true ;
LeftRotation(parent);
sibling = parent->right;
}
if(sibling->isBlack())
{
// CASE 2 : SIBLING AND ITS CHILDREN ARE BLACK
if(sibling->right->isBlack() amp;amp; sibling->left->isBlack())
{
sibling->black = false ;
node = parent ;
parent = node->parent;
if(node == parent->left)
sibling = parent->right;
else
sibling = parent->left;
//continue;
}
else if(sibling->right->isBlack())//CASE 3 : SIBLING IS BLACK AND ITS RIGHT IS BLACK
{
sibling->black = false;
sibling->left->black = true;
RightRotation(sibling);
sibling = parent->right;
}
}
//CASE 4 : SIBLING IS BLACK AND SIBLING'S RIGHT IS RED
sibling->right->black = true;
sibling->black = false;
parent->black = true;
LeftRotation(parent);
node = this->root;
}
else // node is right child and sibling
{
sibling = parent->left ;
printf("node = %d , parent =%d ,sibling = %d n",node->data,parent->data,sibling->data);
if(sibling->isRed())
{
parent->black = false;
sibling->black = true;
node->black = true ;
RightRotation(parent);
sibling = parent->left;
}
if(sibling->isBlack())
{
// CASE 2 : SIBLING AND ITS CHILDREN ARE BLACK ...
if(sibling->left->isBlack() amp;amp; sibling->right->isBlack())
{
sibling->black = false ;
node = parent ;
parent = node->parent;
//continue;
}
else if(sibling->left->isBlack())//CASE 3 : SIBLING IS BLACK AND ITS LEFT IS BLACK
{
sibling->right->black = true;
sibling->black = false ;
RightRotation(sibling);
sibling = parent->left ;
}
}
sibling->left->black = true;
//CASE 4 : SIBLING IS BLACK AND ITS LEFT IS RED
sibling->black = false;
parent->black = true;
RightRotation(parent);
node = this->root;
}
}
node->black = BLACK_NODE ;
}
but when i test all that i find out that there is an error in fixup algorithms :
this is my tree
N
50|B
N
35|R
N
24|B
N
23|B
N
21|B
N
20|R
N
19|B
N
15|B
N
4|B
N
2|R
N
1|B
N
-4|B
N
-30|R
N
когда я удаляю 23, полученное дерево выглядит
N
50|R
N
35|R
N
24|B
N
21|B
N
20|R
N
19|B
N
15|B
N
4|B
N
2|R
N
1|B
N
-4|B
N
-30|R
N
как вы можете видеть, 35 и 50 нарушают третье правило (каждый красный узел, оба его дочерних элемента должны быть черными).
я думаю, что я должен добавить оператор continue в СЛУЧАЕ 2 …
Комментарии:
1. Я понятия не имею об этой книге, но следует иметь в виду, что псевдокод, как правило, содержит ошибки, потому что он не может быть эффективно протестирован. Вы могли бы лучше изучить проверенную реализацию. Мне всегда нравилась библиотека Бена Пфаффа, написанная на C Web, старой грамотной системе программирования. Видишь adtinfo.org . Форма PDF красива и интересна для чтения. Там есть пара вариаций Красно-черных деревьев.
2. я думаю, что я должен добавить заявление о продолжении в СЛУЧАЕ 2. Вы делаете. СЛУЧАЙ 2 возобновляет цикл while с родителем в качестве нового узла для исправления. Теперь у вас есть новый родитель, новый брат или сестра, дети нового брата или сестры.
Ответ №1:
Я не уверен, что это «ответ», а скорее предложение.
Реализовав библиотеку дерева RB, я могу заверить вас, что алгоритм удаления-это настоящая ПИТА. Существует множество особых случаев, и вам нужно понять (на бумаге), прежде чем пытаться реализовать их на любом языке. Не хочу показаться неуважительным, но я очень сомневаюсь, что кто-нибудь захочет найти ваши ошибки для вас здесь бесплатно.
Тем не менее, если ваша цель не заключается конкретно в реализации дерева RB с нуля, я бы настоятельно рекомендовал вместо этого реализовать дерево AVL. Вы обнаружите, что алгоритмы намного проще, и существует простая симметрия между вставкой и удалением, чего нет в случае с деревьями RB. Кроме того, дерево AVL имеет те же характеристики производительности, что и дерево RB, так зачем мучить себя?
P.S. Я искренне надеюсь, что ни одному студенту не будет поручено выполнить удаление дерева RB!
P. P. S. Вы можете получить древовидную производительность из списка пропусков, который очень прост в реализации по сравнению с деревом RB или деревом AVL.