Непреследующий преемник в двоичном валке поиска

Question

Это проблема, которую я должен решить:

Удал узел в двоичном дереве поиска, найдите узел с наименьшим ключом, который больше, чем ключ данного Узел ..

Алгоритм, который часто дан, это один:

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

.

(Вы можете найти дальнейшие объяснения проблемы здесь .)

Теперь мне было интересно, может ли это другое решение:

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

Ваш код правильный, если ключ одного узла никогда не равен ключению другого узла.

В противном случае вы код не удается вернуть правильный непослушник-преемник узла в нижней части следующего графика.