Исключение из-за нулевого указателя при отображении дерева вверх-вниз - PullRequest
Новая
       45

Исключение из-за нулевого указателя при отображении дерева вверх-вниз

0 голосов
/ 12 октября 2011

Я пытаюсь сделать восходящее дерево в Java.Но каким-то образом я получаю исключение с нулевым указателем в моем методе поворота, когда я строю дерево, добавляю несколько элементов и пытаюсь развернуть вставленный узел вверх.Может кто-нибудь сказать мне, почему я получаю эту ошибку?

По сути, у меня есть этот общий класс SPTNode с указателем влево, указателем вправо, указателем родителя, корневым узлом и держателем для splayNode.У него также есть методы для одиночных вращений, вращений ZigZig, вращений ZigZag, методов 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;

    }


}

1 Ответ

0 голосов
/ 18 января 2012

Проблема, если все остальное такое же, как у двоичного дерева поиска. При использовании родительского указателя вы должны быть осторожны, если

1) родительский узел является нулевым, тогда вы находитесь в корневой области и вам нужно установить корень для вашего нового узла. Также обновите родительские указатели.

2) Если у родителя есть правильный ребенок, и вы переместили этого ребенка как часть ротации. Установите новый узел, чтобы быть правильным потомком. Необходимо проверить, был ли родитель слева или справа.

3) Нужно также проверять наличие нуля при установке родительских указателей.

Я получил пару исключений при использовании родительских указателей и исправил их здесь

...