Treeset recursion methods question

[Syrne]

Hello!

I was given the task to finish writing the definitions of the Treeset class methods.

I'm currently at the headSet and tailSet functions and quite stumped.

Here's what they look like currently, with no logic:

@Override
  public SortedSet<E> headSet(E before){
      SortedSet<E> set = new SearchTreeSet<E>();
      headSet(root, before, set);
      return set;
  }
  private void headSet(Node n, E before, SortedSet<E> set){

  }
  
  @Override
  public SortedSet<E> tailSet(E from){
      SortedSet<E> set = new SearchTreeSet<E>();
      tailSet(root, from, set);
      return set;
  }
  
  private void tailSet(Node n, E from, SortedSet<E> set){    
  }

I am a little unsure what is going on there, why are there two declarations of the same method, but with different return types? I know that one is a 'helper' function, but I don't understand exactly what it's doing. Is the helper function what gets called initially and contains the base case? And since the private method contains the recursion, why is it void? Won't it be returning a call the function?

Also, if someone could help me out by explaining the logic of what these functions do (not writing code), that would be great as well.

Thank you!

[JamesCherrill]

I can't explain the logic, but the public method is the one that gets called initially (that's why it's public), and the private method is the "helper" (being private it can only be called from within the class).
There's no reason why a recursive method can't be void. Recursive just means that the method calls itself.
Two method declarations may have the same name, but they have different parameters, so they are quite different methods. In Java a method's "signature" is its name plus its parameters. Names may be duplicated within a class, but signatures cannot be duplicated. The scope (public vs private) and the return type are not part of the signature.

[Syrne]

Sorry for the late bump, but thank you for your response. It cleared up a lot about recursion functions for me.

I'd still like to learn about the logic for these functions, though. I know their general purpose is:

headSet returns the set where every element is less than the input.

tailSet returns the set where every element is more than the input.

I'm just not exactly sure how to go through the tree to achieve this. I'm guessing the recursion is what's continuing to check, in the case of headSet, if an element is more than the input, remove it and continue down the tree until a null node is found.

Is this correct? Would I just use this.left and this.right to venture through the tree?

Thanks again.

[Syrne]

I guess I can't edit my last post, but I've been playing around with the code and I found that I need to use a comparator to compare the data that's held in 'from' with the data of the current node.

public SortedSet<E> tailSet(E from){
      SortedSet<E> set = new SearchTreeSet<E>();
      tailSet(root, from, set);
      return set;
  }
  
  private void tailSet(Node n, E from, SortedSet<E> set){
      int comp = myCompare(n.data, from);
      if(n == null){
          System.out.println("Empty set.");                 
      }
      else
          if(comp < 0){
              remove(n.left);
          }
          else if(comp > 0){
              remove(n.right);
          }
  }

That's nowhere near finished, but I think I'm getting somewhere. This, though, causes the program to fail in so many ways. It states that these lines:

remove(n.left);
remove(n.right);

are "suspicious calls" to the remove function. Why is this?

Also, I need to find some way to move through the tree. I know with linked lists it's as simple as setting to the current node to node.next, but I'm not sure how it's done in a tree.

Thanks for any help.

EDIT:

I found that using this works much better:

remove(n.left.data);
remove(n.right.data);

Still unsure how to move through the tree, though.

[Syrne]

Another bump, sorry!

I think I finally wrapped my head around the logic of these treesets and these functions.

in tailSet, for instance, I have to return a set that includes only values that are greater than or equal to a given element.

In my head, I see it going like this:

Check if root is less than the element
If it is, remove the root and all subsequent nodes to the left of the root.
If it is equal, do the same operation, but preserve the root.
If the root has a greater value than the element, search through the left portion of the tree for a node with equal or less value and follow previous steps.

Does this sound right? If so, how would I traverse through the tree to check for this? I know it has something to do with recursion, but I'd like to know more.

Thank you!

[JamesCherrill]

Sorry not to reply - I've been away. I'll be back online soon.
J

[Syrne]

Sorry not to reply - I've been away. I'll be back online soon.
J

Oh, no problem. I'm not specifically asking for your time, just generally asking anyone for help.

Thank you regardless!