Databases
StackOverflow2013
Postsdbo
POTrying to balance an AVL tree when adding (inserting) : Java
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POTrying to balance an AVL tree when adding (inserting) : Java
    primarykey
    data
    text
    <p>I'm trying to balance my AVL tree after I add a new item to the tree, but I keep getting NPEs. I believe I've narrowed it down to something to do with my balance() method, or possibly more specifically, my rotateLeft() and rotateRight() methods. Here's my AVLTree class:</p> <pre><code>package proj; import java.util.LinkedList; import java.util.Queue; public class AVLTree&lt;T extends Comparable&lt;T&gt;&gt; { private Queue&lt;Node&lt;T&gt;&gt; tree; private Node&lt;T&gt; root; private int size; public AVLTree(){ tree = new LinkedList&lt;Node&lt;T&gt;&gt;(); root = null; size = 0; } public void add(T value){ Node&lt;T&gt; n = new Node&lt;T&gt;(value); if(root == null){ root = n; tree.add(n); size++; } else{ add(root, value); } } //adds a new node to the tree then re-balances if necessary public void add(Node&lt;T&gt; subtree, T value){ Node&lt;T&gt; n = new Node&lt;T&gt;(value); if(subtree == null){ subtree = n; tree.add(n); size++; if(size()&gt;2){ balance(n.getParent()); } } else{ int difference = subtree.getValue().compareTo(n.getValue()); if(difference&lt;0){ if(subtree.getRightChild()==null){ subtree.setRightChild(n); n.setParent(subtree); tree.add(n); size++; if(size()&gt;2){ balance(n.getParent()); } } else{ add(subtree.getRightChild(), value); } } else if(difference&gt;0){ if(subtree.getLeftChild()==null){ subtree.setLeftChild(n); n.setParent(subtree); tree.add(n); size++; if(size()&gt;2){ balance(n.getParent()); } } else{ add(subtree.getLeftChild(), value); } } else if(difference==0){ return; } } } //balances the tree public void balance(Node&lt;T&gt; n){ if(balanceFactor(n) == -2){ if(balanceFactor(n.getRightChild())&lt;0){ rotateLeft(n); if(balanceFactor(n.getRightChild())==-1){ rotateLeft(n); rotateLeft(n.getRightChild()); } else if(balanceFactor(n.getRightChild())==1){ rotateRight(n.getRightChild()); rotateLeft(n); } } } else if(balanceFactor(n) == 2){ if(balanceFactor(n.getLeftChild())&gt;0){ rotateRight(n); if(balanceFactor(n.getLeftChild())==1){ rotateRight(n); rotateRight(n.getLeftChild()); } else if(balanceFactor(n.getLeftChild())==-1){ rotateLeft(n.getLeftChild()); rotateRight(n); } } } if(n.getParent() != null){ balance(n.getParent()); } } //performs a left rotation on the passed //subtree root public void rotateLeft(Node&lt;T&gt; subtree){ Node&lt;T&gt; temp = subtree.getRightChild(); subtree.setRightChild(temp.getLeftChild()); temp.setLeftChild(subtree); subtree = temp; } //performs a right rotation on the passed //subtree root public void rotateRight(Node&lt;T&gt; subtree){ Node&lt;T&gt; temp = subtree.getLeftChild(); subtree.setLeftChild(temp.getRightChild()); temp.setRightChild(subtree); subtree = temp; } //returns the tree in its current state public Queue&lt;Node&lt;T&gt;&gt; getTree(){ return tree; } //returns the root of the tree public Node&lt;T&gt; getRoot(){ return root; } //returns the size of the tree public int size(){ return size; } //returns the head of the queue public Node&lt;T&gt; peek(){ Node&lt;T&gt; current = root; while(current.getLeftChild() != null){ current = current.getLeftChild(); } return current; } //returns the height of the tree; returns -1 if the tree is empty public int height(Node&lt;T&gt; n){ if(n == null){ return -1; } return Math.max(height(n.getLeftChild()), height(n.getRightChild()))+ 1; } //returns the balance factor of the passed subtree public int balanceFactor(Node&lt;T&gt; subtree){ return height(subtree.getLeftChild()) - height(subtree.getRightChild()); } public static void main(String[] args){ AVLTree&lt;Integer&gt; avl = new AVLTree&lt;Integer&gt;(); avl.add(1); avl.add(2); avl.add(3); avl.add(4); avl.add(5); System.out.println("Root: " + avl.root.getValue()); System.out.println("Root's left: " + avl.root.getRightChild().getValue()); System.out.println("Root's balance factor: " + avl.balanceFactor(avl.getRoot())); System.out.println("Tree Size: " + avl.size()); for(Node&lt;Integer&gt; n : avl.tree){ System.out.println(n.getValue()); } } } </code></pre> <p>Am I doing the methods I mentioned incorrectly, or am I incorrectly adding to the tree before I even get to the balancing?</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USChris V.
    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. VO
      singulars
      1. POTrying to balance an AVL tree when adding (inserting) : Java
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIn which line do you get the NPE?
      singulars
      1. POTrying to balance an AVL tree when adding (inserting) : Java
      1. USAaron Digulla
    2. COreturn height(subtree.getLeftChild())-height(subtree.getRightChild());
      singulars
      1. POTrying to balance an AVL tree when adding (inserting) : Java
      1. USChris V.
    3. COI'm wondering if the way I did my balance method and my rotate methods are correct; I did them mostly according to the insertion description on the AVL Tree wiki
      singulars
      1. POTrying to balance an AVL tree when adding (inserting) : Java
      1. USChris V.
 

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