Making binary tree: memory problem

[Juhan Voolaid]

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:

             (0,0)
           /       \
      (2,3)         (0,0)
      /   \          /     \
 (1,4)   (0,0)  (1,4)   (0,0)
 

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

class Tree {
 
        private int price;
        private int weight;
        private Tree left;
        private Tree right;
 
        Tree(){
                price=0;
                weight=0;
        }
 
        Tree(int price, int weight){
                this.price=price;
                this.weight=weight;
        }
        public void setLeft(Tree left){
                this.left=left;
        }
 
        public void setRight(Tree right){
                this.right=right;
        }
 
        public Tree getLeft(){
                return left;
        }
 
        public Tree getRight(){
                return right;
        }
        //other methods
}

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

class Mainclass {
        int[][] data;
        Tree tree;
 
        //other methods
 
        public void initTree(){
                tree = new Tree();
                tree=setChildren(0, tree);
 
        }
 
        public Tree setChildren(int i, Tree parent){
 
                if(i<data.length){
                        parent.setLeft(new Tree(data[i][0], data[i][1]));
                        parent.setRight(new Tree(0, 0));
                        i++;
                        setChildren(i, parent.getLeft());
                        setChildren(i, parent.getRight());
                }
 
                return parent;
        }
}

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]

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]

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]

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 ]

[Juhan Voolaid]

OK thanx. Now I now in which direction to move on.