Suppression dans un arbre de recherche binaire

Question

L'enseignant nous a expliqué cet algorithme de supprimer un nœud dans un arbre de recherche binaire, mais je ne comprends pas comment cela fonctionne lorsque le nœud à supprimer n'a qu'un seul enfant (je sais déjà comment cela fonctionne théoriquement).

algorithme:

abc_delete(T, z) // z is the node that must be eliminated 
{
        if((z.left == NULL) && (z.right == NULL))
                y = z;
        else
                y = abr_successor(z);

        if(y.left != NULL)
                    x = y.left;
        else
                    x = y.right;

        if(x != NULL)
                x.p = y.p;

        if(y.p == NULL)
                T.root = x;
        else
        {
                if(y == (y.p).left)
                        (y.p).left = x;
                else
                        (y.p).right = x;
        }

        if(y != z)
                z.key = y.key;
        return y;
}

abr_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x == y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

Par exemple, je veux supprimer le numéro de nœud $ 7 $ :

Mais, ne devrait-il pas le résultat final?

Answer 1

vous le choix est certainement correct.

Cependant, il n'y a rien de mal avec le code de votre professeur, non plus. Voici un extrait de CLRS.

Les opérations d'insertion et de suppression causent le jeu dynamique représenté par un arbre de recherche binaire à modifier. La structure de données doit être modifiée pour refléter ce changement, mais de manière à ce que la propriété Binary-Search-Tree-Tree continue à contenir.

Nous préférons certainement que l'opération soit faite de la manière la plus simple ou la voie la plus rapide. Cependant, il n'est pas nécessaire que la modification doit être faite de la manière la plus simple, voire même de manière simple. Cela ne nécessite pas non plus que la modification soit faite au moyen le plus rapide, voire même de manière rapide. Tout cela nécessite que le fonctionnement de la suppression produise une autre arborescence de recherche binaire contenant tous les nœuds de l'arbre de recherche binaire donné sans ce nœud spécifique (et plus de nœuds). Comment ces nœuds restants forment un arbre de recherche binaire est totalement exempt de contraintes.

Le code de votre professeur, d'autre part, est probablement le code clair le plus court qui fait le travail. Plus j'étudie, plus l'ingéniosité que je trouve.

Answer 2

Votre dessin est la solution correcte, quelle que soit votre analyse de votre code d'enseignant n'est pas précise (U Mis d'interprète le code)

Quand j'ai vu UR Qi n'a pas lu le code à fond et j'ai pensé (à partir du 1er pic / dessin) Votre enseignant effectue une opération de suppression pour un type spécial de BST qui a des conditions supplémentaires que l'ordre relatif, mais Ce n'est pas le cas

Lors de la suppression d'une BST (essayant de suivre vos variables de code, z est le nœud à supprimer)

Si z est un nœud de feuille (pas d'enfants), il suffit de remplacer le pointeur parent avec NULL

Si z a 1 enfant (que ce soit à gauche ou à droite, cela signifie que le pointeur parent pointe sur son seul enfant

C'est très simple codage, dans un code semi pseudo

si (z.left== null) {physicy_delete (z, zright); revenir(); // soit nous avons seulement le bon sous-arbre ou aucun droit }

// ici nous sommes sûrs qu'il y a un sous-arbre gauche

si (z. droite== null) {physical_delete (z, z.left); revenir(); }

// physicy_delete a le remplacement en tant que 2e paramètre, toutes les boucles de votre code d'enseignant consiste à déterminer ce qui est en cas d'incaser que nous avons deux sous-arbres

Si z a 2 enfants, alors vous devez choisir l'un d'entre eux de prendre sa place et voici votre code de l'enseignant (pas dans le cas précédent)

Dans votre photo Imagine U r Suppression "5" Ce long code est destiné à ajuster le sous-arbre restant de ses 2 enfants (comment lier 7 & 3 et leurs enfants au noeud 12 Garder la BST Contrainfain)

Si vous avez besoin de traçage détaillé, nous pouvons le faire, mais seulement si vous avez trouvé cela utile comme un démarrage