aspose file tools*
The moose likes Java in General and the fly likes Making binary tree: memory problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Making binary tree: memory problem" Watch "Making binary tree: memory problem" New topic
Author

Making binary tree: memory problem

Juhan Voolaid
Ranch Hand

Joined: Nov 18, 2003
Posts: 179
I need to construct a binary tree, but I get java.lang.OutOfMemoryError: Java heap space exception. In other words I have memory leak in my code.

What I want, is to contruct a binary tree of array values, so that right child has the array values and left has zero values. So if array looks like that:
data[0][0]=2
data[0][1]=3
data[1][0]=1
data[1][1]=4

- the tree should look like this:


How I have done this is so that I made a Tree class:


And I have the main class where I construct the tree with the following methods:



This works when the length of my array is 10 for example, but when I try with data[100][2] - array that has a length of 100, I get the java.lang.OutOfMemoryError: Java heap space exception.

So how should I solve my problem, what am I doing wrong?

I have heard one solution that the tree should be presented as (int) array - not as the big tree structure object. Is this the most normal way or can I fix my solution, because I like it (OO kind of thinking) more


thanx

[ October 18, 2005: Message edited by: Juhan Voolaid ]

[ October 18, 2005: Message edited by: Juhan Voolaid ]

[ October 18, 2005: Message edited by: Juhan Voolaid ]

[ October 19, 2005: Message edited by: Juhan Voolaid ]
[ October 19, 2005: Message edited by: Juhan Voolaid ]
Vlado Zajac
Ranch Hand

Joined: Aug 03, 2004
Posts: 245
The problem is that the tree is too big.

Complete binary tree with depth 100 can't fit in memory of any today's computer in any normal representation. It has about 1267650600000000000000000000000 leaves.
[ October 18, 2005: Message edited by: Vlado Zajac ]
Juhan Voolaid
Ranch Hand

Joined: Nov 18, 2003
Posts: 179
OK
If I would represent a tree in array int[][] dataTree and there are (2^100)-1 nodes in binary tree. So if I do dataTree=new int[(2^100)-1][2];
Do I ran out of memory allso? What if data.length is not 100 but 3000?

How would experienced programmer deal with that problem?
[ October 19, 2005: Message edited by: Juhan Voolaid ]
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14156
    
  19

First of all,

dataTree = new int[(2^100)-1][2];

is valid syntax in Java, but it does not mean what you think it means. The "^" is the XOR (exclusive OR) operator, it does not compute powers.

Assuming you meant 2 to the power of 100, your statement would be equal to:

dataTree = new int[1267650600228229401496703205375][2];

Now I don't know how much memory your computer has, but it probably does not have 10,141,204,801,825,835,211,973,625,643,008 bytes of free memory, so ofcourse you'll get an OutOfMemoryError if you try this. I'm not going to calculate for you what the numbers are if you use 3,000 instead of 100.

How an experienced programmer would deal with this problem? An experienced programmer would note that this is impossible and that a different solution or algorithm should be chosen to solve the problem that the program is written for.

By the way: Your question is not about a memory leak - that's something different.
[ October 19, 2005: Message edited by: Jesper de Jong ]

Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
Juhan Voolaid
Ranch Hand

Joined: Nov 18, 2003
Posts: 179
OK thanx. Now I now in which direction to move on.
 
Don't get me started about those stupid light bulbs.
 
subject: Making binary tree: memory problem