Rouge Noir Arbre de la suppression de l'algorithme
De "Introduction aux Algorithmes 2e édition" j'ai eu cette suppression de l'algorithme:
/*
RB-DELETE(T, z)
1 if left[z] = nil[T] or right[z] = nil[T]
2 then y ← z
3 else y ← TREE-SUCCESSOR(z)
4 if left[y] ≠ nil[T]
5 then x ← left[y]
6 else x ← right[y]
7 p[x] ← p[y]
8 if p[y] = nil[T]
9 then root[T] ← x
10 else if y = left[p[y]]
11 then left[p[y]] ← x
12 else right[p[y]] ← x
13 if y != z
14 then key[z] ← key[y]
15 copy y's satellite data into z
16 if color[y] = BLACK
17 then RB-DELETE-FIXUP(T, x)
18 return y
*/
Maintenant quelques problèmes avec cet algorithme, l'un des principaux problèmes est que si vous essayez de construire l'arbre ( vous pouvez le faire ici) avec des nœuds 1,2,3,4,5,6 (placés dans cet ordre), puis supprimer le nœud 2, lignes 4, 5 et 6 de cet algorithme retourne nullptr (x == nullptr). Quelqu'un peut-il m'aider?
Voici l'aide d'algorithmes (à partir du même livre):
TREE-SUCCESSOR(x)
1 if right[x] ≠ NIL
2 then return TREE-MINIMUM (right[x])
3 y ← p[x]
4 while y ≠ NIL and x = right[y]
5 do x ← y
6 y ← p[y]
7 return y
TREE-MINIMUM (x)
1 while left[x] ≠ NIL
2 do x ← left[x]
3 return x
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
LEFT-ROTATE(T, x)
1 y ← right[x] ▹ Set y.
2 right[x] ← left[y] ▹ Turn y's left subtree into x's right subtree.
3 p[left[y]] ← x
4 p[y] ← p[x] ▹ Link x's parent to y.
5 if p[x] = nil[T]
6 then root[T] ← y
7 else if x = left[p[x]]
8 then left[p[x]] ← y
9 else right[p[x]] ← y
10 left[y] ← x ▹ Put x on y's left.
11 p[x] ← y
RB-INSERT(T, z)
1 y ← nil[T]
2 x ← root[T]
3 while x ≠ nil[T]
4 do y ← x
5 if key[z] < key[x]
6 then x ← left[x]
7 else x ← right[x]
8 p[z] ← y
9 if y = nil[T]
10 then root[T] ← z
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z
14 left[z] ← nil[T]
15 right[z] ← nil[T]
16 color[z] ← RED
17 RB-INSERT-FIXUP(T, z)
RB-INSERT-FIXUP(T, z)
1 while color[p[z]] = RED
2 do if p[z] = left[p[p[z]]]
3 then y ← right[p[p[z]]]
4 if color[y] = RED
5 then color[p[z]] ← BLACK ▹ Case 1
6 color[y] ← BLACK ▹ Case 1
7 color[p[p[z]]] ← RED ▹ Case 1
8 z ← p[p[z]] ▹ Case 1
9 else if z = right[p[z]]
10 then z ← p[z] ▹ Case 2
11 LEFT-ROTATE(T, z) ▹ Case 2
12 color[p[z]] ← BLACK ▹ Case 3
13 color[p[p[z]]] ← RED ▹ Case 3
14 RIGHT-ROTATE(T, p[p[z]]) ▹ Case 3
15 else (same as then clause
with "right" and "left" exchanged)
16 color[root[T]] ← BLACK
Mise en ŒUVRE
enum Color {Black,Red};
template<class Key>
struct Node
{
Key* key_;
Color color_;
Node* parent_;
Node* left_;
Node* right_;
Node(Key k,Node* parent = nullptr, Node* left = nullptr,Node* right = nullptr):key_(new Key[2]),
color_(Red),
parent_(parent),
left_(left),
right_(right)
{
key_[0] = k;
key_[1] = '\0';
}
};
template<class Key>
class Tree
{
Node<Key>* head_;
typedef Key* key_pointer;
typedef Node<Key>* pointer;
typedef Node<Key> value_type;
public:
Tree(Key k):head_(new value_type(k))
{
head_->color_ = Black;
}
~Tree()
{
delete head_;
}
pointer root()const
{
auto root = head_;
while (root->parent_)
{
root = root->parent_;
}
return root;
}
void root(pointer root)
{
head_ = root;
}
pointer parent()const
{
return head_->parent_;
}
void parent(pointer parent)
{
head_->parent_ = parent;
}
pointer left()const
{
return head_->left_;
}
void left(pointer left)
{
head_->left_ = left;
}
pointer right()const
{
return head_->right_;
}
void right(pointer right)
{
head_->right_ = right;
}
key_pointer key()const
{
return head_->key_;
}
};
template<class Tree,class Node>
void left_rotate(Tree* t, Node* x)
{
auto y = x->right_;
x->right_ = y->left_;
if (y->left_)
{
y->left_->parent_ = x;
}
y->parent_ = x->parent_;
if (!x->parent_)
{
t->root(y);
}
else if(x == x->parent_->left_)
{
x->parent_->left_ = y;
}
else
{
x->parent_->right_ = y;
}
y->left_ = x;
x->parent_ = y;
}
template<class Tree,class Node>
void right_rotate(Tree* t, Node* x)
{
auto y = x->left_;
x->left_ = y->right_;
if (y->right_)
{
y->right_->parent_ = x;
}
y->parent_ = x->parent_;
if (!x->parent_)
{
t->root(y);
}
else if(x == x->parent_->right_)
{
x->parent_->right_ = y;
}
else
{
x->parent_->left_ = y;
}
y->right_ = x;
x->parent_ = y;
}
template<class Tree, class Node_Value>
void insert(Tree* t, Node_Value n)
{
auto z = make_node(n);
auto x = t->root();
decltype(z) y = nullptr;
while(x)
{
y = x;
if (*z->key_ < *x->key_)
{
x = x->left_;
}
else
{
x = x->right_;
}
}
z->parent_ = y;
if (!y)
{
t->root(z);
}
else
{
if (*z->key_ < *y->key_)
{
y->left_ = z;
}
else
{
y->right_ = z;
}
}
z->left_ = nullptr;
z->right_ = nullptr;
z->color_ = Red;
insert_fix_up(t,z);
}
template<class Tree, class Node>
void insert_fix_up(Tree* t, Node* z)
{
while (z->parent_->color_ == Red)
{
if (z->parent_ == z->parent_->parent_->left_)
{
auto y = z->parent_->parent_->right_;
if (y->color_ == Red)
{
z->parent_->color_ = Black;
y->color_ = Black;
z->parent_->parent_->color_ = Red;
z = z->parent_->parent_;
}
else if(z == z->parent_->right_)
{
z = z->parent_;
left_rotate(t,z);
}
z->parent_->color_ = Black;
z->parent_->parent_->color_ = Red;
right_rotate(t,z->parent_->parent_);
}
else
{
auto y = z->parent_->parent_->left_;
if (y->color_ == Red)
{
z->parent_->color_ = Black;
y->color_ = Black;
z->parent_->parent_->color_ = Red;
z = z->parent_->parent_;
}
else if(z == z->parent_->left_)
{
z = z->parent_;
right_rotate(t,z);
}
z->parent_->color_ = Black;
z->parent_->parent_->color_ = Red;
left_rotate(t,z->parent_->parent_);
}
}
t->root()->color_ = Black;
}
template<class Node>
Node* tree_minimum(Node* x)
{
while (x->left_)
{
x = x->left_;
}
return x;
}
template<class Node>
Node* tree_successor(Node* x)
{
if (x->right_)
{
return tree_minimum(x->right_);
}
auto y = x->parent_;
while (y && x == y->right_)
{
x = y;
y = y->parent_;
}
return y;
}
template<class Tree, class Node>
Node* rb_delete(Tree* t,Node* z)
{
Node* x = nullptr;
Node* y = nullptr;
if (!z->left_ || !z->right_)
{
y = z;
}
else
{
y = tree_successor(z);
}
if (y->left_)
{
x = y->left_;
}
else
{
x = y->right_;
}
x->parent_ = y->parent_;
if (!y->parent_)
{
t->root(x);
}
else if (y == y->parent_->left_)
{
y->parent_->left_ = x;
}
else
{
y->parent_->right_ = x;
}
if (y != z)
{
z->key_ = y->key_;
}
if (y->color_ = Black)
{
rb_delete_fix_up(t,x);
}
return y;
}
template<class Tree, class Node>
void rb_delete_fix_up(Tree*& t,Node*& x)
{
while (x != t->root() && x->color_ == Black)
{
Node* w = nullptr;
if (x == x->parent_->left_)
{
w = x->parent_->right_;
if (w->color_ == Red)
{
w->color_ = Black;
x->parent_->color_ = Red;
left_rotate(t,x->parent_);
w = x->parent_->right_;
}
if (w->left_->color_ == Black && w->right_->color_ == Black)
{
w->color_ = Red;
x = x->parent_;
}
else if(w->right_->color_ == Black)
{
w->left_->color_ = Black;
w->color_ = Red;
right_rotate(t,w);
w = x->parent_->right_;
}
w->color_ = x->parent_->color_;
x->parent_->color_ = Black;
w->right_->color_ = Black;
left_rotate(t,x->parent_);
x = t->root();
}
else
{
w = x->parent_->left_;
if (w->color_ == Red)
{
w->color_ = Black;
x->parent_->color_ = Red;
right_rotate(t,x->parent_);
w = x->parent_->left_;
}
if (w->right_->color_ == Black && w->left_->color_ == Black)
{
w->color_ = Red;
x = x->parent_;
}
else if(w->left_->color_ == Black)
{
w->right_->color_ = Black;
w->color_ = Red;
left_rotate(t,w);
w = x->parent_->left_;
}
w->color_ = x->parent_->color_;
x->parent_->color_ = Black;
w->left_->color_ = Black;
right_rotate(t,x->parent_);
x = t->root();
}
}
x->color_ = Black;
}
template<class Key>
Node<Key>* make_node(Key k)
{
return new Node<Key>(k);
}
int _tmain(int argc, _TCHAR* argv[])
{
auto t = new Tree<int>(1);
insert(t,2);
insert(t,3);
insert(t,4);
insert(t,5);
insert(t,6);
rb_delete(t,t->left());
return 0;
}
Avez-vous vérifié si votre problème est répertorié ici: cs.dartmouth.edu/~thc/clrs-2e-bugs/bugs.php ?
n'y est pas.
Pouvons-nous voir votre mise en œuvre effective?
Il y a peut être quelque chose de mal avec la mise en œuvre. RBTrees sont assez solides et éprouvées. Surtout avec un cas bien connu comme l'insertion d'une liste triée des éléments.
et Nico, pas de problème, donnez-moi 5 minutes et je vais vous présenter tous ces algorithmes mis en œuvre. Pour autant que je suis concerded ni d'insertion ni de suppression de fonctionner correctement (pour l'arbre construit dans cet ordre:1,2,3,4,5,6).
n'y est pas.
Pouvons-nous voir votre mise en œuvre effective?
Il y a peut être quelque chose de mal avec la mise en œuvre. RBTrees sont assez solides et éprouvées. Surtout avec un cas bien connu comme l'insertion d'une liste triée des éléments.
et Nico, pas de problème, donnez-moi 5 minutes et je vais vous présenter tous ces algorithmes mis en œuvre. Pour autant que je suis concerded ni d'insertion ni de suppression de fonctionner correctement (pour l'arbre construit dans cet ordre:1,2,3,4,5,6).
OriginalL'auteur smallB | 2011-07-17
Vous devez vous connecter pour publier un commentaire.
Pour une version de la rb-arbre sans sentinelles de l'opération de suppression de la mise en œuvre est comme suit:
C'est en Java, mais peut facilement être porté à n'importe quelle langue.
Le code suivant est différente à l'égard de votre mise en œuvre:
De nidification ici:
et ici:
Sans-sentinelle de trucs ici:
puis ici:
et dans
deleteFixUp()- il suffit de regarder pour l'utilisation denodeParentetnodeIsLeft, et enfin à cet endroit:et ce:
isBlacketisRedsauvé ma journée, merciau lieu de (node == nodeParent._left), devrait être (nodeParent != null && node == nodeParent._left) Sinon, vous pouvez obtenir un nullpointer exception lorsque vous atteignez le nœud racine. En plus de cela, c'est une excellente solution pour les supprimer/supprimer-fixup sans sentinelles
C'est pas un null test quelque part (peut-changement de la ligne de
deleteFixUpàif (node != null) node._isRed = false; ou pourraient changerif (!y._isRed) { deleteFixUp(tree, x, xParent, yIsLeft);}àif (!y._isRed && tree._root != null) { deleteFixUp(tree, x, xParent, yIsLeft);}), car il donne une NullPointerException lorsque l'arbre est un simple noir noeud et de le supprimer.OriginalL'auteur Trog
La couleur d'un
Nilnœud est défini pour être noir. Le code contient des énoncés tels quequi va se bloquer si
yest unnullptr. Si vous remplacez toutes ces comparaisons avec des appels à la sécuritéis_red()etis_black()fonctions qui permettent de vérifierNilnœuds, puis quelques-unes des accidents de disparaître.L'imbrication ici
ne correspond pas à la nidification ici:
D'autres choses peut-être besoin de débogage trop, mais je ne pense pas que CLR sera à blâmer.
et à propos de is_red() || is_black()? Et que suis-je censé faire, si c'est nullptr? Sautez simplement la ligne où la variable est null mentionné? Sauter sur tout le bloc? C'est ce qui m'énerve, 3ème édition de ce livre, et pourtant on ne peut pas construire l'arbre basé sur leurs algorithmes. Pathétique.
et l'ensemble de la procédure supprimer? Il est vissé en place. Essayer de construire l'arbre 1,2,3,4,5,6, dans l'ordre, puis supprimer le nœud 1.
doit retourner false en
nullptretis_black()doit retourner true. L'imbrication devrait être commeelse { if (...) { ... } ... }.merci pour votre commentaire sur la nidification. Qui fonctionne maintenant. Mais supprimer est foutu. Essayez-le et vous verrez.
OriginalL'auteur antonakos