1 Attachment(s)

Binary Search Tree implementation

using a binary search tree (BST) as the data structure.

Your implementation:

will implement the RankBag interface in the RankBagBST class;

must use the provided Node class for the BST nodes (this class must not be modified in any way);

must not depend on the RankBagArray class; and

will not use any built-in collections to store the objects (with the exception of the uniqueSet() method).

Need help.

here to learn as much as i can. so please help if you can and explain the code too.

files in zip.

Re: Binary Search Tree implementation

Tell us what specifically you need help with.

Re: Binary Search Tree implementation

implement the RankBag interface in the RankBagBST class

not sure on how i should start..

Re: Binary Search Tree implementation

Hmm... it looks like you're using BlueJ. I don't know how that IDE works, but I know that Eclipse will automatically add all the required methods into the class for you. Implementing them is still up to you, but at least you know which ones you have to implement. Note: there is a slight problem here... bags typically aren't ordered and also can contain multiple incarnations of an element, but BST's are very much so in a specific order and typically contain one of a certain element (in theory, you can add multiple similar elements to a BST, but you run into all sorts of problems). What type of data structure are you trying to create here?

To do it manually, simply take all the methods as declared in the RankBag interface and do a copy/paste into your RanBagBST class. Again, you still have to implement the methods. I'll give you some pointers on how to implement each method and leave that up to you:

**add**

Here's the algorithm:

Code :

add (element)
currentNode = head
while ( currentNode is not empty):
compare element with currentNode
if Rank is less:
currentNode = currentNode.leftNode;
else if Rank is greater:
currentNode = currentNode.rightNode;
else
figure out what to do if ranks are equal
put element into the spot at currentNode

**clear**

This is surprisingly easy in Java because of the JVM's garbage collector. Simply set the head node to a new node, and the entire old tree will recursively be garbage collected (no work on your part necessary).

**contains**

Just traverse the tree down to where the element should be. If it's there, say true. If it's not, say false. The code for traversing the BST is found in the add pseudo-code.

**first**

the smallest element in a BST is as far-left as you can go.

Code :

currentNode = headNode
while currentNode.leftNode has something
currentNode = currentNode.leftNode

**is empty**

If the head node contains nothing, the tree is by definition empty.

**Kth**

This would be so easy if we had access to quick select... oh well. You'll just have to traverse your BST in-order (Left, node, right). This would be easiest to implement recursively

**remove**

Traverse the entire tree, removing every element that matches the one you want to remove

**remove first**

traverse the tree in-order, then remove the first element that matches the one you want to remove.

**size**

I would simply keep track of every element you added in/took out, but if you must compute it, then traverse the tree, counting each node you pass only once.

**Unique Set**

traverse the entire tree, looking for two elements next to each other. If you found any pairs, the set is not unique. else, the set is unique.