붉은 색 나무에서 방법 제거

Question

RB 트리에서 제거 방법에 문제가 있습니다. x.parent=y.parent에 NullPointerException이 있습니다. 문제는 확실히 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

삭제할 노드에 자식이 없을 수 있습니다. 이 경우에는 부모에게 하위 트리가 없습니다.