0

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

基本的に、左ポインター、右ポインター、親ポインター、ルート ノード、および splayNode のホルダーを持つこの汎用 SPTNode クラスがあります。また、単一回転、ZigZig 回転、ZigZag 回転、splay、および挿入メソッドのメソッドもあります。

そして、ここに私の比較クラスがあります:

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;

    }


}
4

1 に答える 1

0

他のすべてが二分探索木と同じ場合の問題。親ポインターを使用する場合は、次の場合に注意する必要があります。

1) ノードの親が null の場合、ルート領域にいるため、ルートを新しいノードに設定する必要があります。親ポインターも更新します。

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

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

親ポインターの使用中にいくつかの例外が発生し、ここで修正されました

于 2012-01-18T03:58:49.640 に答える