Insérable successeur dans l'arbre de recherche binaire

Question

C'est le problème que je dois résoudre:

donné un nœud dans un arbre de recherche binaire, trouvez le nœud avec la plus petite clé supérieure à la clé de la donnée donnée nœud ..

L'algorithme qui est souvent donné est celui-ci:

bst_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;
}

(vous pouvez trouver d'autres explications sur le problème ici .)

Maintenant, je me demandais si cela peut être une autre solution:

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

Answer 1

Votre code est correct si la clé d'un nœud n'est jamais égale à la clé d'un autre nœud.

Sinon, le code ne parvient pas à renvoyer le bon successeur du nœud au bas du graphique suivant.