Databases
StackOverflow2013
Postsdbo
PONull pointer exception in bottom up splay tree splaying
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PONull pointer exception in bottom up splay tree splaying
    primarykey
    data
    text
    <p>I am trying to do a bottom up splay tree in java. But somehow, I would get a null-pointer exception in my rotation method when I build a tree, add several elements, and try to splay the inserted node to the top. Can anyone tell me why I get that error?</p> <p>Basically, I have this generic SPTNode class with a left pointer, a right pointer, a parent pointer, a root node, and a holder for splayNode. It also has methods for single rotations, ZigZig rotations, ZigZag rotations, splay, and insert methods.</p> <p>And here is my comparator class:</p> <pre><code>import java.util.Comparator; public class SPTNode&lt;AnyType&gt; { private SPTNode&lt;AnyType&gt;left; private SPTNode&lt;AnyType&gt;right; private SPTNode&lt;AnyType&gt;parent; private SPTNode&lt;AnyType&gt;root; private AnyType value; private Comparator&lt;AnyType&gt;cmp; private SPTNode&lt;AnyType&gt;splayNode; public SPTNode(AnyType data, SPTNode&lt;AnyType&gt; l, SPTNode&lt;AnyType&gt; r, SPTNode&lt;AnyType&gt; p){ value=data; left=l; right=r; parent=p; } public SPTNode(AnyType data, Comparator&lt;AnyType&gt;c){ this(data,null,null,null); cmp=c; } private final int compare(AnyType a, AnyType b){ return cmp.compare(a,b); } public final SPTNode&lt;AnyType&gt; singleL(SPTNode&lt;AnyType&gt; n){ SPTNode&lt;AnyType&gt;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)&lt;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&lt;AnyType&gt;singleR(SPTNode&lt;AnyType&gt;n){ SPTNode&lt;AnyType&gt;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)&lt;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&lt;AnyType&gt;ZigZigL(SPTNode&lt;AnyType&gt;n){ n.parent=singleL(n.parent.parent); return singleL(n.parent); } public final SPTNode&lt;AnyType&gt;ZigZigR(SPTNode&lt;AnyType&gt;n){ n.parent=singleR(n.parent.parent); return singleR(n.parent); } public final SPTNode&lt;AnyType&gt;ZigZagL(SPTNode&lt;AnyType&gt;n){ return singleL(singleR(n.parent).parent); } public final SPTNode&lt;AnyType&gt;ZigZagR(SPTNode&lt;AnyType&gt;n){ return singleR(singleL(n.parent).parent); } public final SPTNode&lt;AnyType&gt; insert(AnyType value, SPTNode&lt;AnyType&gt; n){ if(n==null){ splayNode=new SPTNode&lt;AnyType&gt;(value,cmp); return splayNode; } int compare=compare(value,n.value); if(compare&lt;0){ n.left=insert(value,n.left); n.left.parent=n; } else if(compare&gt;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&lt;AnyType&gt; splay(SPTNode&lt;AnyType&gt; splayNode){ SPTNode&lt;AnyType&gt;p=splayNode.parent; while(p!=null){ SPTNode&lt;AnyType&gt;gp=p.parent; if(gp==null){ int compare=compare(splayNode.value,p.value); if(compare&lt;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&lt;0 &amp;&amp; compare2&lt;0) splayNode=ZigZigR(splayNode); else if(compare1&gt;0 &amp;&amp; compare2&gt;0) splayNode=ZigZigL(splayNode); else if(compare1&lt;0 &amp;&amp; compare2&gt;0) splayNode=ZigZagL(splayNode); else splayNode=ZigZagR(splayNode); } p=splayNode.parent; } return splayNode; } } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCharles Goodwin
    1. USspider
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COPlease post the stack trace of the NPE.
      singulars
      1. PONull pointer exception in bottom up splay tree splaying
      1. USPaul Bellora
    2. COI think I figure out what the problem is. In my original code, I update the newRoot.parent only if n.parent is not null. But I think I need to update newRoot.parent regardless of whether n.parent is null or not. Otherwise, the next call to rotate would not know that the parent of the splayNode would be. What do you think?
      singulars
      1. PONull pointer exception in bottom up splay tree splaying
      1. USspider
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload