File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Binary Tree and Array Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Binary Tree and Array" Watch "Binary Tree and Array" New topic
Author

Binary Tree and Array

Alexis Heng
Greenhorn

Joined: Sep 05, 2005
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
Sheriff

Joined: Sep 28, 2004
Posts: 18715
    
  40

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


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Alexis Heng
Greenhorn

Joined: Sep 05, 2005
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

Joined: Jul 08, 2003
Posts: 24183
    
  34

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.


[Jess in Action][AskingGoodQuestions]
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 559
    
    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

Joined: Sep 17, 2006
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Binary Tree and Array