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."
author and iconoclast
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.
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 ]
Joined: Sep 17, 2006
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.