Results 1 to 12 of 12
  1. #1
    amportugal is offline Member
    Join Date
    Mar 2012
    Posts
    13
    Rep Power
    0

    Default Binary Tree Data Structure

    I'm doing the Binary Tree Data Structure module, but there seems to be some trouble because it's not working with the method "set" and i doubt the "delete" method is correct.

    Please I need some urgent help. Here's the code:

    Java Code:
    public class AssociativeArray<T>{
     public class Node<T>{
     String key;
     T value;
     Node<T> left;
     Node<T> right;
     }
     Node root;
     int size;
     public AssociativeArray(int n){
      root=null;
      size=0;
     }
     public void set(String key, T value){
      Node n=new Node();
      n.key=key;
      n.value=value;
      if(root==null) root=n;
      else setNode(n, root);
      size++;
     }
     private void setNode(Node n, Node r){
      if(n.key.compareTo(r.key)<0){
       if(r.left!=null)
        setNode(n ,r.left);
       else
        r.left=n;
      }
      else
       if(r.right!=null)
        setNode(n,r.right);
       
     }
     public T get(String key){
      return getNode(key, root).value;
     }
     private Node<T> getNode(String key, Node r){
      if(r==null) return null;
      if(r.key.equals(key))
       return r;
      else if(key.compareTo(r.key)<0) return getNode(key, r.right);
      else return getNode(key, r.left);
     }
     public boolean exists(String k){
      try{
       getNode(k, root);
      }catch(AssertionError e){
       return false;
      }
      return true;
     }
     public void delete(String key){
             deleteNode(key, root, null);
      size--;
     }
     private void deleteNode(String key, Node r, Node p){
      if(r.key.compareTo(key)==0){
       if(r.left==null && r.right==null){
        if(p.left==r)
         p.left=null;
        if(p.right==r)
         p.right=null;
       }
       else if(r.left==null)
        r=r.right;
       else if (r.right==null)
        r=r.left;
       else{
        Node min=searchMinimum(r.right);
        deleteNode(key, min.right, min);
        min.left=r.left;
        min.right=r.right;
        r=min;
       }
      }
      else if(r.key.compareTo(key)<0) deleteNode(key, r.right, r);
      else if(r.key.compareTo(key)>0) deleteNode(key, r.left, r);
            }
     private Node searchMinimum(Node e){
      while(e.left!=null)
       e=e.left;
      return e;
     }
     public String[] keysToArray(){
      String[] keys=new String[size];
      keystoArrayInOrder(root, keys, 0);
      return keys;
     }
     private int keystoArrayInOrder(Node<T> n, String[] keys, int i){
      int next=i;
      if(n!=null)
      {
      keys[next]=n.key;
      if(n.left!=null)
       next=keystoArrayInOrder(n.left, keys, next+1);
      if(n.right!=null)
       next=keystoArrayInOrder(n.right, keys, next+1);
      }
      return next;
     }
     public void clear(){
      root=null;
      size=0;
     }
     public int size(){
      return size;
     }
     public boolean isEmpty(){
      return size==0;
     }
    }

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,524
    Blog Entries
    7
    Rep Power
    20

    Default Re: Binary Tree Data Structure

    Your setNode( ... ) method also isn't correct: it works out all possibilities if the new data is less than the data item in the current node, but it goofs for the opposite situation.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    amportugal is offline Member
    Join Date
    Mar 2012
    Posts
    13
    Rep Power
    0

    Default Re: Binary Tree Data Structure

    Done, thanks a lot.

    What about the delete method?
    I'm pretty sure it's wrong and I'm having lots of difficulty of implementing that type of delete algorithm.

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,524
    Blog Entries
    7
    Rep Power
    20

    Default Re: Binary Tree Data Structure

    System.out.println( ... ) is your friend here; put it everywhere where you suspect your implementation to be wrong; it's a perfect poor man's debugger.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    amportugal is offline Member
    Join Date
    Mar 2012
    Posts
    13
    Rep Power
    0

    Default Re: Binary Tree Data Structure

    Can someone aid on the code of the delete method?

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,524
    Blog Entries
    7
    Rep Power
    20

    Default Re: Binary Tree Data Structure

    Quote Originally Posted by amportugal View Post
    Can someone aid on the code of the delete method?
    Aid on what? Write down in words (not code) what your code has to do; suppose the node to be deleted is a leaf node; what to do? Suppose the node isn't a leaf node (so it has either a left or right sub tree); what to do?

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    amportugal is offline Member
    Join Date
    Mar 2012
    Posts
    13
    Rep Power
    0

    Default Re: Binary Tree Data Structure

    Ok then:
    If it's a leaf: simply eliminates it and the parent points to null where the refered leaf was;
    If it's a Node with one subtree: eliminates it and its Parent is connected to its "son";
    If it's a Node with two subtrees: eliminates it and substitute it with the Node with the minimum key (the "left'est") on its right subtree.

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,524
    Blog Entries
    7
    Rep Power
    20

    Default Re: Binary Tree Data Structure

    That's it; only the third point needs a bit of coding; the other two are just a few if-statements to figure out what to do exactly.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    amportugal is offline Member
    Join Date
    Mar 2012
    Posts
    13
    Rep Power
    0

    Default Re: Binary Tree Data Structure

    That's exactly what I'm feeling difficulties on, doing the third point...

  10. #10
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,524
    Blog Entries
    7
    Rep Power
    20

    Default Re: Binary Tree Data Structure

    Quote Originally Posted by amportugal View Post
    That's exactly what I'm feeling difficulties on, doing the third point...
    That's the point where you have to find the leftmost element in the right sub-tree. It would be something like this:

    Java Code:
    Node findLeftMost(Node r) {
       if (r.left == null) return r; // found it
       return findLeftMost(r.left); // it must be there
    }
    You can do it iteratively as well:

    Java Code:
    Node findLeftMost(Node r) {
       while (r.left != null) r= r.left; // move left as far as possible
       return r; // found it
    }
    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  11. #11
    amportugal is offline Member
    Join Date
    Mar 2012
    Posts
    13
    Rep Power
    0

    Default Re: Binary Tree Data Structure

    I've done that already, but thanks anyway :D

  12. #12
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,524
    Blog Entries
    7
    Rep Power
    20

    Default Re: Binary Tree Data Structure

    Quote Originally Posted by amportugal View Post
    I've done that already, but thanks anyway :D
    So there are no problems left anymore?

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Binary Tree Help - Find the largest sub-tree
    By joshhazel in forum New To Java
    Replies: 2
    Last Post: 01-30-2012, 02:08 AM
  2. Replies: 8
    Last Post: 10-17-2011, 09:17 AM
  3. Tree data structure
    By Nacao in forum New To Java
    Replies: 18
    Last Post: 08-23-2011, 06:26 PM
  4. Tree Structure
    By chiku in forum New To Java
    Replies: 2
    Last Post: 01-27-2011, 08:31 PM
  5. Replies: 0
    Last Post: 04-04-2010, 07:40 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •