Suppression du noeud Binary Search Tree

Question

J'ai essayé d'implémenter une fonction de suppression pour un arbre de recherche binaire mais je n'ai pas réussi à le faire fonctionner dans tous les cas.

C'est ma dernière tentative:

Node* RBT::BST_remove(int c) 
{ 
    Node* t = get_node(c); 
    Node* temp = t; 

    if(t->get_left() == empty) 
     *t = *t->get_left(); 
    else if(t->get_right() == empty) 
     *t = *t->get_right(); 
    else if((t->get_left() != empty) && (t->get_right() != empty)) 
    { 
     Node* node = new Node(t->get_data(), t->get_parent(), t->get_colour(), t->get_left(), t->get_right()); 
     *t = *node; 
    } 

    return temp; 
} 

Node* RBT::get_node(int c) 
{ 
    Node* pos = root; 

    while(pos != empty) 
    { 
     if(c < pos->get_data()) 
      pos = pos->get_left(); 
     else if(c == pos->get_data()) 
      return pos; 
     else 
      pos = pos->get_right(); 
    } 

    return NULL; 
} 

t est un nœud et vide est juste un nœud avec rien dedans. J'essaye juste d'échanger les valeurs mais j'obtiens une erreur d'exécution. Des idées?

edit: Je retourne temp pour l'effacer ensuite.

Merci

Answer 1

D'abord, votre dernière else if clause conditionnelle est redondante. Échangez-le avec une clause else. Deuxièmement, je pense que cela rendrait les choses plus faciles pour vous si vous preniez comme paramètre un pointeur vers le nœud à supprimer. Vous pouvez écrire une fonction find() qui trouverait un nœud donné avec sa clé. Je suppose bien sûr que vous pouvez changer la signature de la fonction. Si vous pouvez prendre comme paramètre le nœud à supprimer, vous pouvez vous concentrer sur la suppression du nœud plutôt que d'ajouter une logique pour trouver le nœud. Sinon, écrivez toujours cette fonction find() et utilisez-la pour obtenir le pointeur sur le nœud concerné.

Lorsque vous supprimez un nœud dans un arbre de recherche binaire, vous devez maintenir la commande afin que l'arborescence ne perde pas son intégrité. Rappelons qu'il y a un ordre spécifique dans l'arbre qui supporte la récupération rapide des éléments. Donc, énumérez les cas possibles:

1. Le noeud à supprimer n'a pas d'enfants. C'est facile: libérez simplement ses ressources et vous avez terminé.
2. Le noeud a un seul noeud enfant. C'est assez simple aussi. Relâchez le nœud et remplacez-le par son enfant, de sorte que l'enfant conserve la place du nœud supprimé dans l'arborescence.
3. Le noeud a deux enfants. Appelons le noeud D. Recherchez l'enfant le plus à droite de la sous-arborescence gauche D. Appelons ce noeud R. Affectez la valeur R à D et supprimez R (comme décrit dans cet algorithme). Notez que R peut avoir zéro ou un enfant.

Le troisième scénario, illustré:

  . 
     . 
     . 
    /
    D 
    /\ 
    /\ . 
/\ 
/ \ 
+------+ 
     \ 
     R 
     /
     ?