Java Path compression

Question

Hi, I have to create a method find that would use a local Set to collect the objects and the root. Then, I would compress the object e (in the parameter) and have the roost as its parent. Then, I would return the reference to the root. I can use the Graph, Map, and set class since it was imported. But, how can I call the parent of the root? would I just put mapParent.get(e)?

EDIT The method's function is to have the node point to the root, and I want to use a Set to put together all the objects between the parameter and the object's root. Then, I would use path compression. Then, I have to return the reference to the object. So, I was wondering how I would call the parent for the object to somehow refer to the parent. So here is what I got:

public T find (T obj){
    //Set<E> s = new HashSet<E>(sizeOfRoot.size()); // i don't know how I would use the set yet
      T p = null;
      if (map.get(obj).equals(obj)) // I was trying to get the parent of e
       return obj; 
      else{
       p = find(map.get(obj)); // recursively call the method to path compress
      }

    return p; // return the reference to the node
  }

Can you please help steer me in the right direction?

Answer 1

The right way is to store parent with each node. If you can't do it for whatever reason then you should use a Map, rather than Set.

Somewhere in your code you would fill this map, by calling

mapParents.put(obj, parent)

Then later you can retrieve parent by calling

parent=mapParents.get(obj)

All this, assuming I understand your requirements correctly.