Inodujo sucesor en árbol de búsqueda binaria.

Question

Este es el problema que tengo que resolver:

Dado un nodo en un árbol de búsqueda binario, encuentra el nodo con la clave más pequeña que es mayor que la clave de los dados Nodo ..

El algoritmo que a menudo se da es 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;
}

(puede encontrar más explicaciones del problema aquí .)

Ahora, me preguntaba si esto puede ser otra solución:

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

Su código es correcto si la tecla de un nodo nunca es igual a la tecla de un nodo diferente.

De lo contrario, su código no devuelve el iNoRed-sucesor correcto del nodo en la parte inferior del siguiente gráfico.