Java Binary tree implemented using an array

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Java Binary tree implemented using an array

Postby Berengal » Thu Oct 09, 2008 4:39 pm UTC

So I just got an assignment centered on binary trees. Fine, I know what a binary tree is, and I know how to implement one. We're supposed to implement it using an array. Okay, I can do that too. The array's not supposed to have any holes, any child that's added is going in the first free spot. Okay, I can do that, but not without creating a Node class to put the data in, as I now need meta-data about the tree in each node. Is this somehow useful? I mean, the usual way of just having the nodes link to their children directly has the disadvantage that every node is allocated on a possibly fragmented heap. Using an array to implement the tree puts all the data sequentially, but since an array is just a big block of raw data, you need some way of figuring out where in the tree each bit of data is, like saying that the Left -> Left -> Right node is the sixth node, which can lead to empty indexes in the array if the tree's not full. Removing this option means putting the data back into wrapper nodes carrying meta-data about the tree (needed, because there are several ways of constructing the same tree, but in this case they'll each yield differing resulting arrays), which gives us back the fragmented heap problem of the linked tree, but in addition keeps an array of references to the nodes. I really don't see the benefit of this array, so unless I'm missing something, this assignment has some weird requirements.

Later we're parsing some basic arithmetic expressions into the tree, so yes, the tree can be incomplete, and new nodes can be added wherever there's room for them, not in any specific pattern.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

Re: Java Binary tree implemented using an array

Postby segmentation fault » Thu Oct 09, 2008 5:15 pm UTC

im not sure i fully understand your issue. what meta-data are you trying to store?

edit: oh wait...is this just a normal regular binary tree?
people are like LDL cholesterol for the internet

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Java Binary tree implemented using an array

Postby jaap » Thu Oct 09, 2008 5:42 pm UTC

segmentation fault wrote:im not sure i fully understand your issue. what meta-data are you trying to store?

edit: oh wait...is this just a normal regular binary tree?


If it is a regular binary tree then there is no need to store links or other metadata. The index into the array gives you the information of where it is in the tree.
index 0: root node of the tree, level 0
index 1-2: children of root, level 1
index 3-6: level 2
index 7-14: level 3
etc.

The only kind of metadata you need is whether or not an array index is in use (contains data) or is empty. As long as the data you are using has a value that can represent an unused entry, you're fine.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Java Binary tree implemented using an array

Postby Berengal » Thu Oct 09, 2008 6:45 pm UTC

Berengal wrote:The array's not supposed to have any holes, any child that's added is going in the first free spot.

There's no mention anywhere that the tree has to be full or proper, and from the wording of the assignment, I take that it doesn't have to be. The following tree can be produced in several ways:

Code: Select all

        1
      /   \
    2      3
  /  \
4      5

Code: Select all

tree = new Tree();
one = tree.addRoot(1);
two = tree.addChild(one, 2);
four = tree.addChild(two, 4);
five = tree.addChild(two, 5);
three = tree.addChild(one, 3);

Giving the array:
[1,2,4,5,3]

Or:
tree = new Tree();
one = tree.addRoot(1);
two = tree.addChild(one, 2);
three = tree.addChild(one, 3);
four = tree.addChild(two, 4);
five = tree.addChild(two, 5);

Giving the array:
[1,2,3,4,5]


The tree is fully general, so it can store anything.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Java Binary tree implemented using an array

Postby Xanthir » Thu Oct 09, 2008 6:53 pm UTC

I'm not sure why you need a fragmented heap. Just have each node store the array offsets of its children, in addition to its data. This way you're not implementing a linked tree, but you have the functionality of the same, without any holes in the array. The resultant array will indeed look different when constructed in different ways, but the structure imposed by the children-offsets will be identical.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Java Binary tree implemented using an array

Postby Berengal » Thu Oct 09, 2008 7:44 pm UTC

Yeah, I know that, but the problem with that is having to wrap the data in Node objects. The same goes for the linked tree, but not for the array tree described by jaap: The structure of the tree would be implicit in the position of the data elements in the array, and so you wouldn't have to wrap them in objects containing information about the structure. Since this is Java, primitive types need to be boxed for use in generic structures, and the array would only hold references to objects, not raw data, sequential access is ruined anyway, but let's pretend we can actually make a Tree<int> object:
Using predefined (decided through a deterministic algorithm) offsets for nodes in certain positions, you could have an array of ints stored sequentially: [1,2,3,4,5], and have all the benefits of locality of reference. If each node also has to hold information about it's children's offsets, then we'd actually get an array that looked something like [NodeObject(1), NodeObject(2), NodeObject(3), NodeObject(4), NodeObject(5)]. Each of these node objects are allocated on the heap, with no guarantee of locality of reference. Additionally, the Node class would look something like "class Node<E> {E data; int leftChild; int rightChild;}". The linked tree's Node class looks something like "class Node<E> {E data; Node<E> leftChild; Node<E> rightChild;}", which is practically identical (ints and references are the same size in java), but the linked tree has the additional benefit that it doesn't require an array lookup to find the actual child nodes, as it's right there in it's fields, and it doesn't waste an array on keeping references that could just as easily have been stored in the nodes themselves, or bookkeeping to keep the array large enough (I'm going to use an ArrayList for the actual array, of course, but the point still stands). Our assignment explicitly states that being able to remove nodes from the tree is not a requirement, but it's clear that a linked tree would do this easier as well.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Java Binary tree implemented using an array

Postby Xanthir » Thu Oct 09, 2008 8:27 pm UTC

Ah, right. Sorry. Forgot about Java's weirdness with the distinction between objects and primitives, and how that affects storage.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Java Binary tree implemented using an array

Postby Berengal » Mon Oct 13, 2008 1:02 pm UTC

I just got an email from my professor saying that nodes shouldn't have references to their children, as that would make the tree a linked structure and thus make the array useless. I'm guessing that means storing the indexes is out of the question as well, and that storing the values directly in the array is the way to go (if, on the other hand, java had structs, this would be a viable option). Anyway, this indicates that I've missed something somewhere, but I can't figure out what.

I could try to impose a certain structure on the tree by rearranging it as new nodes are added, so that a given tree will always produce the same array, but I can't find a good way to do this. What I'm thinking is letting null be the only leaf node, and for all other nodes, the node at i+1 is the left child of the node at i. The right node would then become the first node after the left sub-tree has gotten all it's leaves. (e.g, the tree (1 (2 (3) (4)) 5) would look like [1 | 2 | 3 | null | null | 4 | null | null | 5 | null | null],) but this doesn't seem like a really good solution to me. It uses more space, and is much less efficient to traverse than any other kind of binary tree I can think of, not to mention having to restructure the array every time a node is added.

My only hope is a set of lecture notes I found on google which uses array indexes, but that's in c, and it uses structs; the exact thing that won't work in java. (Well, it will, but then you might as well use the references themselves directly).
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
wr3cktangle
Posts: 75
Joined: Tue Aug 01, 2006 5:03 pm UTC

Re: Java Binary tree implemented using an array

Postby wr3cktangle » Wed Oct 15, 2008 2:51 am UTC

here's my thoughts

If you just append each new node onto the end of the array, its parent node will be
tree[Math.floor((i-1) * 0.5)] where i is the current node's index. Every node's children (if existent) will be found at tree[2 * i + 1] and tree[2 * i + 2].

I think this is kinda what jaap is going at.

I hope this helps.
Maxim 33. When faced with the unusual, self-destruct.
My blog

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Java Binary tree implemented using an array

Postby Berengal » Wed Oct 15, 2008 3:22 am UTC

That only holdes true if you add nodes in the tree sequentially from top to bottom, from left to right, and the tree is full. My implementation has to be able to support the adding of a node, then immediately the adding of it's left child. If that node is the 10th node, then it's child will be found at index 10, not index 19 or 20. If you see one of my above posts, you'll see an example of how the same tree produces differing internal arrays.

I sort of solved it by just using two arrays. Not sure if it's the optimal solution... Anyway, I've got an array dataArray to hold the data, and an array structureArray to inform me of the structure of the tree. The structure array is twice as big as the data array, and for a node with index i, it's children's indexes are stored at i*2 and i*2+1 in the structureArray. I'm also using Node objects, but only for interacting with the tree: They're not stored in the array, but instead only created when someone asks for it. It contains only the data and it's index in the dataArray array.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
wr3cktangle
Posts: 75
Joined: Tue Aug 01, 2006 5:03 pm UTC

Re: Java Binary tree implemented using an array

Postby wr3cktangle » Wed Oct 15, 2008 4:10 am UTC

I see.
That's what reading when tired get's ya, partial comprehension.
Maxim 33. When faced with the unusual, self-destruct.
My blog

qbg
Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

Re: Java Binary tree implemented using an array

Postby qbg » Wed Oct 15, 2008 5:10 am UTC

Berengal wrote:That only holdes true if you add nodes in the tree sequentially from top to bottom, from left to right, and the tree is full. My implementation has to be able to support the adding of a node, then immediately the adding of it's left child. If that node is the 10th node, then it's child will be found at index 10, not index 19 or 20. If you see one of my above posts, you'll see an example of how the same tree produces differing internal arrays.

I sort of solved it by just using two arrays. Not sure if it's the optimal solution... Anyway, I've got an array dataArray to hold the data, and an array structureArray to inform me of the structure of the tree. The structure array is twice as big as the data array, and for a node with index i, it's children's indexes are stored at i*2 and i*2+1 in the structureArray. I'm also using Node objects, but only for interacting with the tree: They're not stored in the array, but instead only created when someone asks for it. It contains only the data and it's index in the dataArray array.

If this is still true: "I'm guessing that means storing the indexes is out of the question as well", then you really haven't solved the problem. At that point, you could just do something like [root-value|left-value|child-index|right-value|child-index|...etc...], where the left child's value is stored at child-index and the right child's value is stored at child-index+2, etc.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Java Binary tree implemented using an array

Postby Berengal » Wed Oct 15, 2008 6:15 am UTC

That needs some more explanation I think. The way I understand it, you're proposing putting both the left and right child of a node next to each other in the array, with the indexes in between them. It could work. It would leave open holes in the array, but that's justifiable by letting leaf nodes be null, not a branch with no children, but a with a value. The problem with doing this, however, is that it would only work if the values were ints, which makes it somewhat less generic than what is required. I could make it an Object array and store Integers in it, but that smells somewhat fishy. If I could do this, however, I'd rather do [value | left-index | right-index | value | left-index | right-index | etc].

By "storing indexes" I meant storing the child indexes in Node objects, and have the data array be a Node<T> array. It wasn't explicitly stated that this wasn't allowed, but I reasoned that since storing references to the children in the Node objects was no good, indexes would be no good too. The reason for this is that it simply adds unnecessary indirection to the child lookup, and by replacing the child index with the child's reference you'd get the exact same functionality, but get rid of the extra lookup and the array. If java had structs or tuples or some other way of specifying an array of different types in a specific pattern like the one you suggested, then that's what I would've done, but it doesn't.
By storing the child indexes in a separate structure array I'm able to traverse the tree by only looking at that array, without referencing any objects but the array, and I actually get the benefits of using an array instead of a linked structure. It's better than storing the index in Node objects, and it's better than letting the array be, e.g the preorder traversal of the tree (potentially this could require major restructuring of the array for every insert, and a bunch of explicit null values as leaves).
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

chibu
Posts: 15
Joined: Sat Oct 11, 2008 4:38 pm UTC

Re: Java Binary tree implemented using an array

Postby chibu » Wed Oct 15, 2008 2:52 pm UTC

Well, I know it's already been suggested, but if you're going to be working with all full or at least complete trees, then the correct way to store a binary tree (with no holes) in an array is to use the Parent = i, left = 2 * i, Right = 2 * i + 1 method.

It's pretty easy. Have you asked your prof if that's the right way to do it? I helped teach a Data Structures and Algorithms class using a book called "Data Structures and other Objects Using Java" last year. Something similar to what you're asking about was one of the homework assignments, and well, that's how we taught it... What you're doing seems alot more complicated than what the assignment sounds like it should be. If you're in some kind of 200 level Data Structures class, this is probably the solution. But again, I would advise speaking with your professor about it.

Yeah, I know that you plan to parse arithmetic expressions with it later which will, undoubtedly make the tree incomplete leaving holes in the array, but, as fas as i know this is the only way to do it with a single array.

Anyway, sorry I'm not really being much help and just rehashing old posts.

~ Chibu

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Java Binary tree implemented using an array

Postby Berengal » Wed Oct 15, 2008 2:58 pm UTC

We're using "Data structures and Objects in Java" as well, and the assignments explicitly states "Do not do it the way they're doing it in the book. Use a different method that doesn't leave holes."
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

demon
Posts: 170
Joined: Tue Feb 06, 2007 8:13 pm UTC

Re: Java Binary tree implemented using an array

Postby demon » Wed Oct 15, 2008 9:51 pm UTC

I'm pretty sure it's not even possible to do if you can't store the indices or leave holes. The way I'd do it (and one I'd probably use in C if I wanted to avoid dynamic memory allocation) would most likely be to convert the whole array to an array-stored stack and then basically use it as a custom allocator - that is upon creating a new node, I'd yank the first free index and on delete I'd put it back. That would give you at most one hole at any point, you could make it 0 holes if you switched the tree-node with the highest array-index with the hole, should be easily doable in constant time. That would give you a solution that works on-line and doesn't break any of the computational complexities you'd expect from a binary tree. But you'd still need the children-indices in the Node.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Java Binary tree implemented using an array

Postby Berengal » Wed Oct 15, 2008 10:40 pm UTC

It's possible if you store the tree as e.g. the result of the preorder traversal of that tree, with leaves being a special sentinel node (null, for instance). This breaks all kinds of computational complexities however, and requires moving stuff around whenever you add something that's not a child node of the last node in the array, and in most cases it also uses more space than the simpler array-based solution even when that one might have a bunch of holes in it.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

chibu
Posts: 15
Joined: Sat Oct 11, 2008 4:38 pm UTC

Re: Java Binary tree implemented using an array

Postby chibu » Wed Oct 15, 2008 11:46 pm UTC

Yeah, I've been thinking about this all day, and I have no idea what your prof is looking for really. So, I guess I can't really help. I'll keep thinking about it and post again if I can figure anything out. But good luck otherwise.

~ Chibu

mrkite
Posts: 336
Joined: Tue Sep 04, 2007 8:48 pm UTC

Re: Java Binary tree implemented using an array

Postby mrkite » Thu Oct 16, 2008 4:44 am UTC

As far as I can tell, what your professor is asking for is impossible.

If there are no null nodes, then it's impossible to determine whether a node has 2 children, 1 child, or is a leaf.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Java Binary tree implemented using an array

Postby Berengal » Thu Oct 16, 2008 6:20 am UTC

If null is the only leaf, then it's possible, but rather unwieldy. I'll probably see what kind of solution my professor had in mind on Tuesday, as it's the first lecture after the due date on this assignment.

As a side note, whoever thought forcing explicit type annotations was a good idea when type inference was an alternative? One of the methods in my assignment:

Code: Select all

   private static String parseSubexpression(
           String expressionString,
           ArrayBinaryTree<ExpressionTerm> tree,
           ArrayBinaryTree<ExpressionTerm>.ArrayBinaryTreeNode<ExpressionTerm> node,
           boolean addLeft) throws ParseException {
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
wr3cktangle
Posts: 75
Joined: Tue Aug 01, 2006 5:03 pm UTC

Re: Java Binary tree implemented using an array

Postby wr3cktangle » Thu Oct 16, 2008 6:17 pm UTC

let me (and possibly a collective us, but i've never really met the other posters, so i can't speak with any authority about their collective or individual desires) know what your teacher was looking for when you find out. I'm curious.
Maxim 33. When faced with the unusual, self-destruct.
My blog

Notch
Posts: 318
Joined: Tue Dec 12, 2006 5:52 pm UTC
Location: Stockholm, Sweden
Contact:

Re: Java Binary tree implemented using an array

Postby Notch » Sat Oct 18, 2008 8:41 am UTC

Berengal wrote:

Code: Select all

        1
      /   \
    2      3
  /  \
4      5

Code: Select all

tree = new Tree();
one = tree.addRoot(1);
two = tree.addChild(one, 2);
four = tree.addChild(two, 4);
five = tree.addChild(two, 5);
three = tree.addChild(one, 3);

Giving the array:
[1,2,4,5,3]

Or:
tree = new Tree();
one = tree.addRoot(1);
two = tree.addChild(one, 2);
three = tree.addChild(one, 3);
four = tree.addChild(two, 4);
five = tree.addChild(two, 5);

Giving the array:
[1,2,3,4,5]


If the only data you're allowed to store is the actual array, then it's _really_ impossible to do, since several different trees would produce the same array depending on how you build them. There's no way for a parser to know that [1,2,4,5,3] is the same as [1,2,3,4,5] and not

Code: Select all

        1
      /   \
    2      4
  /  \
5      3


inserted in the same way as [1,2,3,4,5] was.

Some kind of meta data is obviously needed.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 8 guests