空指针异常在自下而上的张开树散播

我想在java中做一个自下而上的张大树。但不知何故，当我构建一棵树，添加几个元素，并尝试将插入的节点展开到顶部时，我会在我的旋转方法中得到一个空指针异常。谁能告诉我为什么我会得到这个错误？空指针异常在自下而上的张开树散播

基本上，我有一个左指针，右指针，父指针，根节点和splayNode持有者这个泛型SPTNode类。它还具有单旋转，ZigZig旋转，ZigZag旋转，展曲和插入方法的方法。

这里是我的比较级：

import java.util.Comparator; 


public class SPTNode<AnyType> { 

    private SPTNode<AnyType>left; 
    private SPTNode<AnyType>right; 
    private SPTNode<AnyType>parent; 
    private SPTNode<AnyType>root; 
    private AnyType value; 
    private Comparator<AnyType>cmp; 
    private SPTNode<AnyType>splayNode; 

    public SPTNode(AnyType data, SPTNode<AnyType> l, SPTNode<AnyType> r, SPTNode<AnyType> p){ 
     value=data; 
     left=l; 
     right=r; 
     parent=p; 
    } 

    public SPTNode(AnyType data, Comparator<AnyType>c){ 
     this(data,null,null,null); 
     cmp=c; 
    } 

    private final int compare(AnyType a, AnyType b){ 
     return cmp.compare(a,b); 
    } 

    public final SPTNode<AnyType> singleL(SPTNode<AnyType> n){ 
     SPTNode<AnyType>newRoot=n.right; 
     n.right=newRoot.left; 
     newRoot.left=n; 
     if(n.parent!=null){ 
      newRoot.parent=n.parent; 
      if(compare(n.value, n.parent.value)<0) 
       n.parent.left=newRoot; 
      else 
       n.parent.right=newRoot; 
     } 
     n.parent=newRoot; 
     if(n.right!=null) 
      n.right.parent=n; 
     return newRoot; 
    } 

    public final SPTNode<AnyType>singleR(SPTNode<AnyType>n){ 
     SPTNode<AnyType>newRoot=n.left; 
     n.left=newRoot.right; 
     newRoot.right=n; 
     if(n.parent!=null){ 
      newRoot.parent=n.parent; 
      if(compare(n.value, n.parent.value)<0) 
       n.parent.left=newRoot; 
      else 
       n.parent.right=newRoot; 
     } 
     n.parent=newRoot; 
     if(n.left!=null) 
      n.left.parent=n; 
     return newRoot; 
    } 

    public final SPTNode<AnyType>ZigZigL(SPTNode<AnyType>n){ 
     n.parent=singleL(n.parent.parent); 
     return singleL(n.parent); 

    } 

    public final SPTNode<AnyType>ZigZigR(SPTNode<AnyType>n){ 
     n.parent=singleR(n.parent.parent); 
     return singleR(n.parent); 
    } 

    public final SPTNode<AnyType>ZigZagL(SPTNode<AnyType>n){ 
     return singleL(singleR(n.parent).parent); 
    } 

    public final SPTNode<AnyType>ZigZagR(SPTNode<AnyType>n){ 
     return singleR(singleL(n.parent).parent); 

    } 

    public final SPTNode<AnyType> insert(AnyType value, SPTNode<AnyType> n){ 
     if(n==null){ 
      splayNode=new SPTNode<AnyType>(value,cmp); 
      return splayNode; 
     } 
     int compare=compare(value,n.value); 
     if(compare<0){ 
      n.left=insert(value,n.left); 
      n.left.parent=n; 
     } 
     else if(compare>0){ 
      n.right=insert(value,n.right); 
      n.right.parent=n; 
     } 

     return n; 

    } 

    public final void insert(AnyType value){ 
     root=insert(value,root); 
     root=splay(splayNode); 
    } 

    public final SPTNode<AnyType> splay(SPTNode<AnyType> splayNode){ 
     SPTNode<AnyType>p=splayNode.parent; 
     while(p!=null){ 
      SPTNode<AnyType>gp=p.parent; 
      if(gp==null){ 
       int compare=compare(splayNode.value,p.value); 
       if(compare<0) 
        splayNode=singleR(p); 
       else 
        splayNode=singleL(p); 
      } 
      else{ 
       int compare1=compare(splayNode.value,p.value); 
       int compare2=compare(p.value,gp.value); 
       if(compare1<0 && compare2<0) 
        splayNode=ZigZigR(splayNode); 
       else if(compare1>0 && compare2>0) 
        splayNode=ZigZigL(splayNode); 
       else if(compare1<0 && compare2>0) 
        splayNode=ZigZagL(splayNode); 
       else 
        splayNode=ZigZagR(splayNode); 
      } 
      p=splayNode.parent; 
     } 

     return splayNode; 

    } 


}

来源

2011-10-11 spider

请张贴NPE的堆栈跟踪。 –

我想我找出问题所在。在我原来的代码中，只有当n.parent不为null时，我才更新newRoot.parent。但是我认为我需要更新newRoot.parent，而不管n.parent是否为null。否则，下一次旋转调用将不知道splayNode的父节点。你怎么看？ – spider

的问题，如果一切是一样的二叉搜索树。使用父指针时，您需要小心如果，

1）该节点的父节点为空，则您位于根区域，需要将根设置为您的新节点。更新它的父指针。

2）如果父母有一个正确的孩子，并且您将该孩子作为轮换的一部分移动。将新节点设置为正确的子节点。需要检查父母的左或右是否是这种情况。

3）设置父指针时也需要检查null。

我有几个例外，而使用父指针，并得到修正它here

来源

2012-01-18 03:58:49

空指针异常在自下而上的张开树散播

回答

相关问题