Inorder Sucessor na Árvore de Busca Binária

Question

Este é o problema que eu tenho para resolver:

dado um nó em uma árvore de busca binária, encontrar o nó com a menor chave que é maior do que a chave do dado nó..

O algoritmo que é muitas vezes dado é este:

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

(você pode encontrar mais explicações sobre o problema aqui.)

Agora, eu queria saber se isso pode ser uma outra solução:

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

Seu código está correto, se a chave de um nó nunca é igual à chave de um nó diferente.

Caso contrário, o código de falha de retorno correto para agradar o sucessor do nó na parte inferior do gráfico a seguir.