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:

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;

}

}

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

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.

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

Re: Binary Tree Data Structure

Can someone aid on the code of the delete method?

Re: Binary Tree Data Structure

Quote:

Originally Posted by

**amportugal** 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

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.

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

Re: Binary Tree Data Structure

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

Re: Binary Tree Data Structure

Quote:

Originally Posted by

**amportugal** 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:

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:

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

Re: Binary Tree Data Structure

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

Re: Binary Tree Data Structure

Quote:

Originally Posted by

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

So there are no problems left anymore?

kind regards,

Jos