How to do an inverted heap implementation in JAVA?

Simple B-Tree Implementation in Java

• Greetings, I've been working for a while on a pretty simple B-Tree implementation in Java...but my life just went crazy and I need a little help. I'm certainly not asking for source code that I can just pop in and have it work magically. All I need is some nicely written, Java/Object Oriented pseudocode. So, I'd really appreciate a hand. I promise to tip honorably according to how much I've been helped. :) If you feel I'm not offering enough, just tell me, I'm new to this kind of thing. It's OK if you copy + paste from another site as long as I have the reference. Here's the requirements: It's written in java. One can use any class from the API they need to (I know there's some TreeMaps and whatnot in the API). The B-tree is a standard M-ary tree of size M=5 with these properties (taken from a textbook): 1. Data can be stored at any level (not just the leaves). They data is the same as the keyvalue - an int between 1 an 99 (including them). 2. The nonleaf nodes store as many as M-1 keys to guide the searching; key i represents the smallest key in subtree i+1. 3. The root is either a leaf or has between 2 and M children. 4. All nonleaf nodes (Except the root) have between at most M/2 and M children. The data we input will be no more than enough to make 3 levels of the tree. Now, here's what the program needs to be able to do: A. Draw the tree, vertically (as in, root node grows down from the center top of the screen). Just using ASCII text (I code on a Linux text console). B. Delete a node at a given integer. C. Insert a given integer into the tree. D. Locate a given int and indicate a success/fail message E. Find the depth of any data item or report failure. That's it! Nothing really complex or fancy -- just your average B-tree. I need this no later than the afternoon of Thursday (the 21st). Of course, I'll tip more if I get something earlier :P I greatly, sincerely appreciate your help.

• Answer:

  Thanks buckdharma-ga. It's been a pleasure helping you. In summary, the following references may be able to help you with B-tree implementation in Java: 1) A very good algorithm description and implementation in C++: http://cis.stvincent.edu/swd/btree/btree.html 2) An implementation in Java (this pretty much does what you need in A, B, C-- D, E can be easily done by modifying the search function): http://www.hta-bi.bfh.ch/~ctr/archive/project1/BTree1/description/btreedocu.htm (download the zip file at end end: it contains the source AND tes codes). 3) Another algorithm description and example: http://bluerwhite.org/btree/ 4) Java applet demos: http://www.geocities.com/SiliconValley/Program/2864/File/btree.html http://sky.fit.qut.edu.au/~maire/baobab/baobab.html Also note that the Java collection support (TreeMap) is for Red-Black (binary) tree--not for the generalized B(Balanced)-tree you need. That's why the codes in my references have to specifically implement the B-tree. Thanks and best regards, studboy-ga