Thread: 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.

Tell us what specifically you need help with.

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:

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).

headNode = new Node();

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.

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.