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

Question

У меня проблема с методом remove в дереве 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

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