自底向上展开树展开中的java空指针异常

1 周，2 日 Questions & Answers 995

我正在尝试用java做一个自底向上的splay树。但不知何故，当我构建一棵树，添加几个元素，并尝试将插入的节点展开到顶部时，我的旋转方法中会出现空指针异常。有人能告诉我为什么我会犯这个错误吗

基本上，我有一个通用的SPTNode类，它有一个左指针、一个右指针、一个父指针、一个根节点和一个splayNode的保持器。它还提供了单旋转、Z字形旋转、Z字形旋转、splay和insert方法

这是我的比较器课程：

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;

    }


}

Python中文网

有 Java 编程相关的问题?

自底向上展开树展开中的java空指针异常

共 (1) 个答案

# 1 楼答案