supprimer un noeud dans BST

Question

J'essaie d'implémenter la suppression de BST. L'algorithme j'utilise est:

1. si la recherche correspond à un noeud

1.1. s'il y a un nœud enfant quitté, permutez la valeur de ce nœud et de son nœud enfant gauche. Et appelez la fonction du noeud gauche à nouveau.

1.2. Sinon, s'il n'y a pas de nœud gauche mais qu'il y a un nœud droit, permutez la valeur du nœud et celle du nœud droit. appelle la fonction du noeud droit.

1.3. s'il n'y a pas de noeud gauche ou droit, supprimez ce noeud.

ce qui suit est la définition de classe.

fonction

class node{ 
    public: 
    int value; 
    node *left; 
    node *right; 
    node(){value=0; left=0; right =0;} 
    node(int value){this -> value = value; left=0;right=0;} 
    void print(); 
}; 

class tree{ 
    public: 
    node *root; 
    tree(){ 
    root = 0; 
    } 
    ~tree(){} 
    void remove(node *, int); 
    //tree(int value){root = &node(value);} 
    void insert(int); 
    void printSorted(node *); 
    void printAll(node *); 
}; 

print() pour imprimer ... je suis, mon enfant gauche est ..., mon enfant droit est ...

void node::print(){ 
    if(this == 0) return; 
    cout<<"i am "<<value<<endl; 
    if(left !=0){ 
    cout<<"i have left, left is "<<left -> value<<endl; 
    } 
    if(right !=0){ 
    cout<<"i have right, right is "<<right -> value <<endl; 
    } 
} 

fonction printAll(), traversée de la Racine et imprime dans l'ordre.

void tree::printAll(node *nodeP){ 
    if(nodeP == 0) return; 
    else{ 
    node *iter = nodeP; 
    if(iter -> left !=0){ 
     printAll(iter->left); 
    } 
    iter->print(); 
    cout<<endl; 
    if(iter -> right !=0){ 
     printAll(iter -> right); 
    } 
    } 
} 

Ceci est la fonction de suppression.

void tree::remove(node* origin, int toDel){ 
    if(origin == 0) return; 
    node *orig_origin = origin; 
    int tmp; 
    if(origin -> value == toDel){ 
    if((origin -> left == 0) && (origin -> right == 0)){ 
     delete origin; 
     origin =0; 
    } 
    else if((origin -> left != 0) && (origin -> right == 0)){ 
     tmp = origin -> value; 
     origin -> value = origin -> left -> value; 
     origin -> left -> value = tmp; 
     remove(origin -> left, toDel); 
    } 
    else if((origin -> left == 0) && (origin -> right != 0)){ 
     tmp = origin -> value; 
     origin -> value = origin -> right -> value; 
     origin -> right -> value = tmp; 
     remove(origin -> right, toDel); 
    } 
    else{ 
     tmp = origin -> value; 
     origin -> value = origin -> left -> value; 
     origin -> left -> value = tmp; 
     remove(origin -> left, toDel); 
    } 
    } 
    else{ 
    if(origin -> value > toDel) remove(origin -> left, toDel); 
    else remove(origin -> right, toDel); 
    } 
    origin = orig_origin; 
} 

entrée I 7 4 10 1 6 5 après l'appel de suppression, 1 est dans la position 4 d'origine. Mais il reste un enfant de 0. Donc, d'une manière ou d'une autre, j'ai échoué à supprimer le nœud 1 d'origine.

sc-xterm-24:~/scratch/code/cpp_primer> ./a.out 
7 4 10 1 6 5 
i am 0 

i am 1 
i have left, left is 0 
i have right, right is 6 

i am 5 

i am 6 
i have left, left is 5 

i am 7 
i have left, left is 1 
i have right, right is 10 

i am 10 

Answer 1

Lorsque vous avez trouvé la valeur dans l'arbre, la manipulation du dernier cas (où il est à la fois gauche et branche droite) est faux. Vous ne pouvez pas échanger le origin->value et le origin->left->value car cela interrompt l'ordre requis par l'arborescence. Étant donné que le origin->value d'origine est supérieur à toutes les valeurs stockées dans le sous-arbre gauche, le nouveau origin->left->value sera supérieur à toutes les valeurs stockées dans le sous-arbre origin->left->right. Comme la valeur d'un nœud doit être inférieure à tout ce qui est stocké dans l'arborescence de droite, les recherches ultérieures le long de cette branche peuvent échouer ou trouver le mauvais nœud.