Error received:
Exception in thread "main" java.lang.StackOverflowError
at AVL.insert(AVL.java:45)
I am not familiar with the error I was given, but I do know that it only happens when the array being used to build the AVL tree is a vary large size and is occurring during insert when moving to the right side of the tree. I am not sure why this is happening though (in other words I do not know exactly what StackOverflowError is and why it is happening).
AVL class:
//AVL.java
import java.util.*;
import java.io.*;
public class AVL{
AvlNode root;
public void tree(int[] list){
for(int i=0; i<list.length; i++){
insertPrep(list[i]);
}
}
public void insertPrep(int data){
if (root==null){root = new AvlNode(data);}
else {
AvlNode newNode = new AvlNode(data);
root = insert(root, newNode);
root = rebalance(root);
adjustHeight(root);
}
}
public AvlNode insert(AvlNode node, AvlNode newNode){
if (node.key > newNode.key){
if(node.left!=null){node.left=insert(node.left , newNode);}
else{node.left=newNode;}
}
else if (node.key < newNode.key){
if(node.right!=null){node.right=insert(node.right, newNode);}
else{node.right=newNode;}
}
AvlNode result = rebalance(node);
adjustHeight(result);
return result;
}
public int height (AvlNode node ){
if (node == null){return 0;}
else {return node.height;}
}
public void adjustHeight (AvlNode node){
if (root != null){ root.height = 1+ Math.max(height(root.left),height(root.right));}
}
public AvlNode rebalance (AvlNode node){
AvlNode newAvlNode = node;
if (node.left != null && node.right != null){
if (node.left.height-node.right.height==2){
if (node.left.left.height>node.left.right.height){
AvlNode n2 = node.left;
AvlNode n3 = node;
n3.left = n2.right;
n2.right = n3;
adjustHeight(n3);
adjustHeight(n2);
newAvlNode = n2;
} else {
AvlNode n1 = node.left;
AvlNode n2 = node.left.right;
AvlNode n3 = node;
n1.right = n2.left;
n2.left = n1;
n3.left = n2.right;
n2.right = n3;
adjustHeight(n1);
adjustHeight(n3);
adjustHeight(n2);
newAvlNode = n2;
}
} else if (node.right.height-node.left.height==2){
if (node.right.right.height>node.right.left.height){
AvlNode n1 = node;
AvlNode n2 = node.right;
n1.right = n2.left;
n2.left = n1;
adjustHeight(n1);
adjustHeight(n2);
newAvlNode = n2;
} else {
AvlNode n1 = node;
AvlNode n2 = node.right.left;
AvlNode n3 = node.right;
n1.right = n2.left;
n2.left = n1;
n3.left = n2.right;
n2.right = n3;
adjustHeight(n1);
adjustHeight(n3);
adjustHeight(n2);
newAvlNode = n2;
}
}
}
return newAvlNode;
}
class AvlNode{
int key, height; //data for input numbers and height for height of nodes to keep balance
AvlNode left, right; //left for left side of tree and right for right side of tree
AvlNode(int data){
key = data;
}
}
}
Class using AVL:
//Tree.java
import java.io.*;
import java.util.*;
public class Tree{
public static void main(String[] args){
int n = 30000; //numbers to be in arrays
int a[] = new int[n]; //first array
for (int i=0; i<n; i++){
a[i] = i+1; //insert #'s 1-n; smallest to largest
}
//send arrays to be put in AVL trees
AVL avl = new AVL();
double timeSoFar = (double)System.nanoTime();
avl.tree(a);
double treeTime = (double)System.nanoTime() - timeSoFar;
printTime('a',treeTime, "AVL");
}
public static void printTime(char l, double treeTime, String tree){
double treeTimeMin = treeTime/600000;
treeTimeMin/=100000;
System.out.println("Elapsed time for building " + tree + " " + "Tree for array '" + l + "': " + treeTime + " nanoseconds, or: " + treeTimeMin + " minutes.");
}
}
Since your array is sorted from smallest to largest, when you try to insert the, say, 15000th node using insertPrep (see the loop in tree()), you are going to recursively call insert(AvlNode node, AvlNode newNode) 15000 times.
This is due to the test in insert
if (node.key > newNode.key){
if(node.left!=null){node.left=insert(node.left , newNode);}
else{node.left=newNode;}
}
The recursions are too deep
Recursion is probably not your best choice to find the location in the tree and you should resort to a loop which will be more efficient anyway because you do not have to accumulate the frames between the calls.
Alternatively, use a language such as Scala that knows about tail recursion and automatically unfolds tail recursions to loops at compile time.
EDIT The explanation for the Overflow is probably over simplistic. See comments below
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments