Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: Binary Search Tree implementation

  1. #1
    Junior Member
    Join Date
    Oct 2009
    Posts
    12
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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.
    Attached Files Attached Files
    Last edited by helloworld922; October 9th, 2009 at 12:44 AM.


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Binary Search Tree implementation

    Tell us what specifically you need help with.

  3. #3
    Junior Member
    Join Date
    Oct 2009
    Posts
    12
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Binary Search Tree implementation

    implement the RankBag interface in the RankBagBST class

    not sure on how i should start..

  4. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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:

    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.

Similar Threads

  1. recursive search of all local disks
    By ttsdinesh in forum Java Theory & Questions
    Replies: 4
    Last Post: September 27th, 2009, 09:23 AM
  2. Arrays.sort or iterative search?
    By igniteflow in forum Collections and Generics
    Replies: 1
    Last Post: September 16th, 2009, 03:07 AM
  3. How to highlight search keyword in text?
    By Mohd in forum JavaServer Pages: JSP & JSTL
    Replies: 4
    Last Post: February 1st, 2009, 06:35 AM
  4. Implementation of search function for Patricia Trie
    By javaguy in forum What's Wrong With My Code?
    Replies: 0
    Last Post: July 21st, 2008, 02:54 PM