• 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

Trees

 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hey guys.I am new to java and I am abit confused.I am given an assignment to make a BTree.I read about BTrees and have an idea of what to do.But the problem comes when instead of creating a my new node class the instructor says I should create an integer objects.



This is the skeleton that I am given.My question is how would I make the Nodes.In java what is the difference between a parameter as "int" or "Integer".

Thanks.
 
booker jones
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sorry I omitted some functions.How would the skeleton of your node be.

 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Welcome to the Ranch

Did the instructor say to use Integers or integers? They are different. I would suggest you start with ints, which are integers but only with a small i. Mainly because ints are easy to understand You can then later enhance your tree to take Integers, or even anything which is Comparable or which you can apply a Comparator to. You can read all about comparisons in the Java Tutorials. you end up with two constructors (or more), as in java.util.TreeSet.

Back to your ordinary tree. Try it out with ints, but start by drawing a diagram of the tree. Draw what happens when you create an empty tree, then add a number to it, and write down what happens, as well as adding the new number to your diagram. Repeat with a few more numbers. Leave out traversals or depths for the time being. You can add those things later. Decide what happens when you add the same number twice. Does it vanish (in which case you have a set) or do you add it to a list, or do you count how many times it is added (which is rather like a List)?
Those instructions as to how to add numbers to your tree will give you the pseudo‑code to write the actual program.
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Unless you already understand exactly how such a tree works, you should not have any functions (they are called methods) nor any skeleton for your node. You only consider that sort of thing when you understand the workings of trees. Look at this FAQ.
 
booker jones
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Campbell,
Thanks for the input.I have been reading about BTrees the whole day.If i made a node class like this will it be sufficient.The last time I tried coding I made a wrong node tree and had to change everything.

Here is what I gathered.

Make a node class to hold keys and pointers.


Please am I on the right track here.

edit*
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am afraid, if you go back to your diagram you will see that is miles out.
 
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
Well actually, if in this case we are implementing a trivial b-Tree - where the Key = Data (in other words, all if the data is encompassed by the key) then this could be a very valid implementation of a node.

But i would like to see some discussion around what the relationship between the keys and children (at any one point).

-steve
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Do trees make any distinction between key and datum?
 
Steve Fahlbusch
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
Campbell,

In theory no, but in reality yes.

It helps to remember the usage of b-trees kind of only makes sence supporting indexes into either index sequential files or index to database tables (ie: the indexs are a separate table that finds the data). The reason why we want only the keys in the index file makes use of the fact that disc access is slow, but each time we read from a disk, the entire buffer is read from the drive. So normally the datam part of a b-tree is the key and a reference (or record number) to the underlying data. And of course we make each block size (or node in this case) to be as large as possible but where size ( n * keys ) + ( n+1 * pointers ) <= disc buffer size. Now in this case there is no additional data, so the key is the entire data and we need not even have a reference to some underlying file. And as such the above Node could be a valid implementation.

-steve

 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic