ボトムアップ・スプレイ・ツリー・スプレイでのヌル・ポインタ例外

Question

Javaでボトム・アップ・スプレイ・ツリーを実行しようとしています。しかし、どういうわけか、ツリーを構築し、いくつかの要素を追加し、挿入されたノードを上に広げようとすると、私の回転メソッドでnullポインタ例外が発生します。誰が私になぜそのエラーが出るのか教えてもらえますか？

基本的に、私はこの汎用SPTNodeクラスに、左ポインタ、右ポインタ、親ポインタ、ルートノード、およびsplayNodeのホルダを持っています。また、単一回転、ジグジグ回転、ジグザグ回転、スプレイ、および挿入方法のメソッドもあります。

そして、ここに私のコンパレータクラスです：

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; 

    } 


} 

Answer 1

問題他のすべては、バイナリ検索ツリーと同じである場合。親ポインタを使用する場合は、

1）ノードの親がnullの場合は、ルート領域にあり、ルートを新しいノードに設定する必要がある場合に注意が必要です。親ポインタも更新してください。

2）親に右の子があり、その子をローテーションの一部として移動した場合。新しいノードを適切な子に設定します。親の左か右がケースかどうか確認する必要があります。

3）親ポインタを設定するときに、nullもチェックする必要があります。

親ポインタを使用している間、私は例外のカップルを持って、それがNPEのスタックトレースを投稿してくださいhere