Удалить метод в Red Black Tree

Question

У меня проблема с методом удаления в дереве RB. Есть исключение NullPointerException в x.parent=y.parent, Проблема определенно x=null, и если я использую этот x в методе DeleteFixUp, то тоже будет NullPointerException. Где у меня ошибка?

Element delete(Element DeleteNode)   
 {

Element x=null;

Element y=null;

    if((DeleteNode.left==null)||(DeleteNode.right==null))
        y=DeleteNode;
    else 
        y=Succesor(DeleteNode,root);

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

    x.parent=y.parent;

    if (y.parent == null)
        root = x;
    else 
    if (y == y.parent.left)
        y.parent.left = x;
    else 
        y.parent.right = x;
    if (y != DeleteNode)
        DeleteNode.value = y.value;

    if(!isRed(y))
    { DeleteFixUp(x);}
    return y;
}

И вот метод преемника:

 Element Succesor(Element x, Element root)

 {

    if( x.right != null )
    { x=FindMin(x.right);
        return x;
              }

    Element succ = null;

    while (root != null)
    {
        if (_comparator.compare(x.value,root.value)==-1)
        {
            succ = root;
            root = root.left;
        }
        else if ((_comparator.compare(x.value,root.value)==1))
            root = root.right;
        else
            break;
    }

    return succ;
} 

Окей, я решил эту проблему, но у меня есть другая. Я добавляю в свой код:

Element delete(Element DeleteNode)   
 {

Element x=null;

Element y=null;

    if((DeleteNode.left==null)||(DeleteNode.right==null))
        y=DeleteNode;
    else 
        y=Succesor(DeleteNode,root);

    if (y.left != null)
        x=y.left;
    else 
        x=y.right;
    //added to code 
    if (x == null) 
    {x = new Element(null);              
     x.kolor=0;          
    }


    x.parent=y.parent;

    if (y.parent == null)
        root = x;
    else 
    if (y == y.parent.left)
        y.parent.left = x;
    else 
        y.parent.right = x;
    if (y != DeleteNode)
        DeleteNode.value = y.value;

    if(!isRed(y))
    { DeleteFixUp(x);}
    return y;
}

Теперь у меня есть вопрос, как это убрать x.value=nullпосле удаления?

Answer 1

У удаляемого узла может не быть дочерних элементов. В этом случае у вас нет поддерева для переписывания.