• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Binary Tree and Array

 
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!~
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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."
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
Ranch Hand
Posts: 1282
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic