Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

Binary Tree and Array

Alexis Heng
Greenhorn
Posts: 6
Hi,

I am pretty new to binary tree, so I hope someone out there can help enlighten me a little.

Firstly, I have created an array(intArr) that stores data say [1, 5, 6, 8, 9, 11].

How can I go about using a binary tree to check which element is biggest?

For e.g I want to know between intAarr[2] to intArr[5], what is the biggest element and return the value?

I cannot see the link between the use of array and the binary tree. Can someone pls kindly shed some light on this? Thanks!~

Henry Wong
author
Marshal
Posts: 21122
78
I cannot see the link between the use of array and the binary tree. Can someone pls kindly shed some light on this? Thanks!~

I don't see the link either. Are you sure your instructor didn't mean "binary search"? Because that is a technique that can be used to search an already sorted array for a particular value.

Henry

Alexis Heng
Greenhorn
Posts: 6
The extract from the qns:

"Hints:

You should not create a binary tree to store the values. Instead,
the values are simply stored in an array and a binary tree should
be created to store information related to the values in the array
so that you can answer the queries in O(lg n) time."

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24211
35
This doesn't directly speak to what your instructor is after (which I don't quite understand, presumably because I haven't seen the whole thing) but I wanted to point out that you can easily store a binary tree in an array, and it's still commonly done. For example, one convention: the root of the tree is at element 0; its two children are at elements 1 and 2; the two children of the item at element one are in elements 3 and 4; the two children of 2 are at 5 and 6; and so on. There's a pattern here: the two children of element X are always stored in elements 2X+1 and 2X+2.

This obviously has a lot less storage overhead, and is a lot more efficient, then creating an actual Node class with pointers and things. This isn't used as much in Java as it is in non-object-oriented languages, but it's still a good itdea.

Steve Fahlbusch
Bartender
Posts: 605
7
From how I read it (and this is only as an instructor not THE instructor) we have an array of values (might be an array of objects that each object encapsulates a lot of values) and we want to create a binary tree off of the key values (what ever the key is) in the array. Very common and we don't want the array in order, but we still want to search the array in O ( ln x ).

Of course we sort of forget about the order of the effort to create the binary tree, but hey each search is O ( log n ) or really O ( ln n ).
[ October 15, 2006: Message edited by: Steve Fahlbusch ]

Nicholas Jordan
Ranch Hand
Posts: 1282
Originally posted by Alexis Heng:
I am pretty new to binary tree,......Thanks!~

This problem is an age-old problem in computer science and, since you a open enough to state new to binary tree, and request help, I will assume you are seeking the most fundamental and basic conceptual grounding.

Briefly, you will run into the "fixed array size problem" faster than you can solve the overall (program design). Binary trees are a method of searching something, like an array, in which the item, things, values are sorted before the search - this dramatically improves quite a number of issues.

I am using JDK 1.4 - I doubt there has been a new class BinaryTree introduced. What would be eventually discovered, after much fretting over how to change the size of the array if the number of elements is not known before runtime, is called (in Java) Collections.

These are tremendously effective tools, which generally implement a type of binary tree called a Map, behind the scenes, because it is so effective at solving many issues, the fixed array size problem being one of them.

As for binary trees, consider the idea that if you could start in the middle of a large dataset and repetitively eliminate half of the dataset from searching - without changing the content of the set - you would approach the desired element, value or object with fewer steps than iterating through all the elements of an array - where the array is dramiatically large. (thousands)

Hint, try starting off with an array in sorted order, with an odd number of elements, and find some element with code you write.