aspose file tools*
The moose likes Java in General and the fly likes Binary Search Trees Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Binary Search Trees" Watch "Binary Search Trees" New topic
Author

Binary Search Trees

kevin comario
Ranch Hand

Joined: Jun 29, 2002
Posts: 65
I have a question on binary search trees i am pretty much lost on how to add and remove: I am in an CS algorithms class but the book we have assigned is insufficent. Our professor has recomended another book by Thomas H. Cormen called "Introduction to Algorithms" the problem that i have right now is that i can't afford the book right now, so i have to make do with what I've got. So I've come to my favorite forum to ask for help.
Here is what I have been give:

Here is what I've done:

All I have done so far is extend BinarySearchTree and override the methods. I was hoping to get help on the add method. How should i go about it fromthe book i have i know that if the root is null then add to the root, if the root is not null then send the file left if <= and right if >= to root(how do i do this) then check to see if the left or right children are > or < and move acordingly changing so children into parents.
I personaly am very confused any help would be apprecitated.
James Chegwidden
Author
Ranch Hand

Joined: Oct 06, 2002
Posts: 201
As an instructor, I would look in your University Library for DS books. Usually the code will be written in somebook and usually you will have to translate it (ie. C to Java or C++ to Java) A lot of people have done binary trees so look it up.
Also, check search engines-you never know were you can find code to help


Author and Instructor, my book
Aditya Jha
Greenhorn

Joined: Dec 13, 2001
Posts: 2
Hi,
As you might have learned, a BST is defined recursively, i.e., its definition is something like 'A Binary Tree is an entity storing some value, and having two associated trees (say, left tree and right tree). A BST is a Binary Tree having some convention between the value and left & child sub-trees. For example, value of left-subtree will always be less than the value of tree, and that of right-subtree will always be greater.'
Hope I'm making sense.
So, applying this, we can write a simple BST as below:

The same approach can be taken for 'remove' method. Also, as you might have guessed, incorporating level-count, returning sub-trees, maintaing node-count etc. are quite easier with this approach.
Downside - It uses recursion. I personally try to avoid it.
Practically, all your assignments can be smoothely done, as they don't need a huge amount of memory-storage for each recursive call.
kevin comario
Ranch Hand

Joined: Jun 29, 2002
Posts: 65
thanks for the help Aditya Jha but i am still very lost. You see i have to use this code specifically:

I'm having trouble using your code since my add method is your insert that takes a comparable object and mine takes an Integer object. and the nodes i have are from my BinaryTreeNode class. my question is, is the abstract class BinarySearchTree my tree? I understand the properties of a search tree but am lost in how to implement them in java. I was hoping to recieve help in my add method so i can see how its done.
one again thank you Aditya Jha but can you please give me a little more guidance.
Thanks in advance.
William Barnes
Ranch Hand

Joined: Mar 16, 2001
Posts: 984

Random thoughts here:
> The code which Aditya posted is important. Do you know how to traverse a binay tree? That code shows you how.
> Your "add" method doesn't do anything if the tree is more than one layer deep.
> Your node is made up of two "pointers" and piece of data. In this case that data is an int.
> The add method takes a new piece of data (an int) and your job is to insert that into the tree. So you need to compare this new piece of data with the data already in your tree. These comparisons will let you know if you need to go left or right.
> Have you searched google for more information?


Please ignore post, I have no idea what I am talking about.
Norm Miller
Ranch Hand

Joined: May 21, 2002
Posts: 56
Kevin,
Back when I was trying to learn to algorithm stuff, "The Art of Computer Programming" by Donald Knuth was the Bible. I bought all three volumes available. I know he did a great job with trees of various kinds. You owe it to yourself to see if it is available in your college/university library. You don't have to buy every book you need. Once you understand the algorithm, the coding is a lot more obvious.
kevin comario
Ranch Hand

Joined: Jun 29, 2002
Posts: 65
Thanks for your help William Barnes and Miller, I went out and got the book Introduction to Algorithms by Thomas H. Cormen. The question i still have is how do i get my pointers to point. Thats where I'm having problems. That is why i was hoping for help using what has been given to me, so please forgive my ignorance in nodes I just really don't understand them.
James Chegwidden
Author
Ranch Hand

Joined: Oct 06, 2002
Posts: 201
What do you mean by "your pointers to point" there are no pointers in Java
Show us where in particular you are having a problem.
kevin comario
Ranch Hand

Joined: Jun 29, 2002
Posts: 65
well my problem mostly lies with these nodes:

I really dont get how to use this class how am i supposed to place integers in them if they hold nothing. I know java doesnt have pointers but how do i get them to link. Thats my question. like for instance if i wanted to set the left child of the root to ten
would i set root.left.value = 10? my question is how do this work how is it stored?
[ October 25, 2002: Message edited by: kevin comario ]
kevin comario
Ranch Hand

Joined: Jun 29, 2002
Posts: 65
Here are some of the changes i have made:

when i try to run this code i get a null pointer exception. I know it is becuase of the nodes, can someone please help.
thanks in advace.
[ October 26, 2002: Message edited by: kevin comario ]
William Barnes
Ranch Hand

Joined: Mar 16, 2001
Posts: 984

You are on the right track here.
But I don't think you have the idea of a binary tree yet. The tree is composed of "nodes", and in your case the node contains information about the nodes to the "left", "right", "parent", and an integer.
So the only real data in the node is the integer. The node is also a separate class, which makes OO sense.
So to "add" a node to a tree first you need to find where to add it, which you seem to be doing correctly. Than you need to create the node, and load it with data. That is the part you are missing. You need to create the node, hook it into the tree and set the int.
[ October 26, 2002: Message edited by: William Barnes ]
kevin comario
Ranch Hand

Joined: Jun 29, 2002
Posts: 65
Here Are the changes I have made:

I am still getting a logic error I think i messed-up on the add method because when i call my inorder method i get the wrong result. for instance in my test case i passed 2,1,3,5,7,8
my root should be 2 but i get 7, can somone please tell me what I'm doing wrong.
William Barnes
Ranch Hand

Joined: Mar 16, 2001
Posts: 984

Well a couple of things.
Make your code more read-able. This will help you in the long run.

This is a bit redundent. Try this:

To know what is happening you want to add some print statements. I know this is a pain but it will help clear up what is actually happening. So code which outputs something like this:

And I don't know what your "inorder" code is doing. Almost all of it is commented out. Do you have code that is able to walk the entire tree?
I don't see anything wrong with your "add" method.
William Barnes
Ranch Hand

Joined: Mar 16, 2001
Posts: 984

Looking at your "inorder" code again let me say this: you are not going to be able "cheat" by using a while loop to walk your tree. You are able to use a while loop to add nodes because you are only walking one branch of the tree. To walk the entire tree you will need to use recursion.
William Barnes
Ranch Hand

Joined: Mar 16, 2001
Posts: 984

C++ example code
William Barnes
Ranch Hand

Joined: Mar 16, 2001
Posts: 984

java code examples
Got all these with a quick google search.
kevin comario
Ranch Hand

Joined: Jun 29, 2002
Posts: 65
Thanks for the help i finally got it.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Binary Search Trees
 
Similar Threads
about binary tree
Binary search tree
Path of TreeSelectionEvent
Paint Binary Search Tree to Scroll Pane in GUI
cannot make static reference to non-static Integer