-1

A little background, I have three classes here in a project: Abstract super class called Tree. sub-class of Tree, called NotEmptyTree. sub-class of Tree, called EmptyTree.

All three classes follow a map like structure, where it takes in a generic any type K Key which implements (extends) comparable and a generic V value.

This is an untraditional BST because it holds other trees not nodes, which I could really use help understanding the whole concept of that, it confuses me a lot, I am so use to the Node structure of BST's.

Right now there is a method which I had help on creating. What it does is make a new copy of a BST without modifying the current object, so this copy is structurally independent. It's only one line but what's happening in the recursion confuses me a lot, I don't understand recursion all that well. I know it's a method that calls itself, while repetitively refining itself until it hits a base case, then it stops and cascades backward collecting all the stuff that its traversed previously. But this method I don't see a base case or the typical recursive structure that I'd see in say, fibonacci. The bulk of the work is in the NotEmptyTree class, the EmptyTree follows the singleton patten and has only that one instance variable for a static object of the class. I think the idea of the EmptyTree is to be a tree without any children at all, where the NotEmptyTree is one which has at least one or two children. But those children are other Trees not nodes.

Here is the method that is inside of the NonEmptyTree class:

@Override
public Tree<K, V> treeCopy() {
    return new NotEmptyTree<K, V>(key, value, leftSubTree.treeCopy(), rightSubTree.treeCopy());
}

I am very lost at what is happening here.

Why the "new"?

why are we creating a new NotEmptyTree?

why the K,V ?

why the (key, value ?

why the leftSubTree.treeCopy() ? what happens in the recursive call? why the rightSubTree.treeCopy() ? what happens in the recursive call? Where is the base case?

This class has four instance variables:

private K key;
private V value;
private Tree<K,V> leftSubTree; // what are these doing?
private Tree<K,V> rightSubTree; // same

I don't understand the purpose of the Tree instance variables here. It confuses me how we have data structures from the parent inside of the child class. Not sure what is going on here, or why we need them. Please I need help understanding, I am so lost here.

Thank you

yre
  • 285
  • 4
  • 12
  • Then answeres are in the constructor of NonEmptyTree – stinepike Apr 10 '17 at 15:23
  • @StinePike the constructor is just a typical constructor it takes all the instance variables there and sets them to the ones in the parameters, nothing fancy. – yre Apr 10 '17 at 15:37
  • @StinePike the constructor of the EmptyTree just follow the singleton design pattern. A static shared instance variable with a private constructor which nothing in it. And a single getter method that returns a new instance of that class. – yre Apr 10 '17 at 15:38
  • Can you post the code of NotEmptyTree constructor also – stinepike Apr 10 '17 at 15:45
  • Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. [on topic](http://stackoverflow.com/help/on-topic) and [how to ask](http://stackoverflow.com/help/how-to-ask) apply here. StackOverflow is not a design, coding, research, or tutorial service. You should gain a stronger understanding of recursion before tackling this problem. Asking several generic questions suggests that you need half an hour with a local tutor, rather than Stack Overflow; this site is more for specific programming problems. – Prune Apr 10 '17 at 16:26
  • @StinePike public NotEmptyTree(K key, V value, Tree leftSub, Tree rightSub) { this.key = key; this.value = value; this.leftSubTree = leftSub; this.rightSubTree = rightSub; } – yre Apr 10 '17 at 16:31

1 Answers1

1

Some of the things before I answer your questions one-by-one

This is an untraditional BST because it holds other trees not nodes,

I think of it as a traditional tree with nodes which hold other nodes. Just change name of class Tree to Node, all will be clear. With only difference being, it's a special type of Node that doesn't hold the Data object, but holds a key value pair.

So you have a Node, with (Key,Value) instead of Data, you have leftNode and rightNode (which are named call leftSubTree, rightSubtree)

A subtree ends when it has both left and right nodes as null.

If you look at your 'tree' in above way, it clears many confusions.

Now coming to your questions:

Why the "new"?
why are we creating a new NotEmptyTree?

new, because you are doing a deep copy (read about deep copy). You have to create a new tree that resembles the old one but it should be totally a new object in the memory.

why the K,V ?

K,V because your new copy should resemble the tree you copied. So you need to have the same datatypes 

why the (key, value ?

Think in terms of 'node' for the Tree as I explained in the beginning. Assume that you are copying the Node. So you need to copy the data (i.e. key/value pair) AND the node's left and right children. 

why the leftSubTree.treeCopy() ? what happens in the recursive call? why the rightSubTree.treeCopy() ?

(thinking in terms of nodes again) You also need to copy the left & right node children of the node. Apparently, one constructor of the NotEmptyTree accepts the children and assigns them as children to the current node. what happens in the recursive call? Where is the base case? Base case is when leftSubtree and rightSubtree are null. In that case, a childless node (or tree if you prefer) is created and returned.

The way recursion occurs is as follows: When an arbitrary node node1 is being copied using treeCopy, a new node is created using data i.e (key,value) pair of node1. But the copy of node1's left and right children are also used to assign the respective children of new node. The leftSubTree.treeCopy() & rightSubTree.treeCopy() calls take care of recursing until the nodes with null children are met when the recursion can't repeat because there is no further call. You need to think a little bit about this to 'get' it, but it is not so difficult. You may try running the program in debug mode with 3-4 nodes and try seeing the code-flow.

Community
  • 1
  • 1
RajatJ
  • 163
  • 9
  • Thanks so much for taking the time to write this, it's appreciated! I am beginning to understand but there are a lot of things that still confuse me. This can all just be thought as Nodes like a traditional BST except here each node has two pieces of data in it, and the data is associated with each other. Key is associated with a Value, but a value isn't associated with a key it goes one way. And let's say a tree is already made, and then we call this treeCopy method on it. So like, bstObject.copyTree(); here it would take all the content out of that bstObject? – yre Apr 10 '17 at 20:49
  • What gets me is the signature not sure what this even really means. Where is that pairing of the K and V even happening? I don't see it anywhere in the code. Also I guess I could think of this like if I wanted to copy an arraylist like, ArrayList list = new ArrayList(); I've never actually filled in that (); area, so here when we put stuff inside of the (); that initialized the binary tree? So with an arraylist it would be like: If ArrayList had a constructor like that it would fill it like: ArraLIst(key, value, leftSub.copyTree(), rightSub.copyTree()) – yre Apr 10 '17 at 20:53
  • So then we are using the NonEmptyTree's constructor that has a key, a value, a leftSubTree, and a rightSubTree. And in order to properly get a separate object we must give the same signature as the object we are copying so it needs the in there just like ArrayList would need because that's what it stores, but since ArrayList has no state that (); area is never filled up. But here there is STATE with a tree, it has a key, a value, and a left and right sub tree full of (nodes) that have the same thing, right? – yre Apr 10 '17 at 20:57
  • So in the method we create a NEW object that is of the NonEmptyTree, it couldn't be an EmptyTree though could it? – yre Apr 10 '17 at 20:58
  • So we are basically just creating a new object of type NotEmptyTree and since this data structure is defined as having the signature we must match that just like ArrayList. If we say made that data structure with the class sig: public class ArrayList {} and if we gave it some state like private int stuff; private String special; and had the constructor like: public ArrayList(size s, int spe) { this.st = stuff; this.spe = special; If we initialized, it would be like: ArrayList list = ArrayLIst(stuff, special); – yre Apr 10 '17 at 21:08
  • The thing that is really getting me is, nothing is being passed into this method, so how does the method know what to copy? I could understand if a tree object was being passed in, like a copy constructor but here it just straight creates a new copy from nothing? – yre Apr 10 '17 at 21:14
  • Is anything ever passed into that part of the NotEmptyTree? Or is that more symbolic? Like if we were to create a new NotEmptyTree we wouldn't actually put anything in there? We would rather focus on putting stuff inside the constructor method on the right side of the new operator? – yre Apr 10 '17 at 21:33
  • I think I would be able to understand this whole signature if it was instead done through an ArrayList. If you could please write this I would be very grateful. This is confusing me so much. – yre Apr 10 '17 at 21:38
  • So this method returns a NEW deep copied version of the tree object that calls this method. So object.copyTree(); and once that is called this method extracts the content out of that tree that called this and returns a NEW deep copied version that is identical to that tree that called it, but is otherwise structurally independent. But when that method is called, is says: return new NonEmptyTree....I understand that much. It's the whose K? and whose V? how does the method know what to put in there? Is it somehow getting it from the caller object? I don't see how that is done. – yre Apr 10 '17 at 21:42
  • Say I created an arraylist and just for the sake of it I wrote: public class ArrayList extends list{ private K key; private V value; public ArrayList(Key k, Value v){ this.key = k; this.value = value; } public list copyList() { ArrayList copy = new ArrayList(key, value); return copy; } So it essentially copied all the content of the CURRENT object, because it's making the SAME thing as the class as an object, and passing in the same instance varaibles defined in the class, key, and value. – yre Apr 10 '17 at 21:47
  • But what if when we run the main method like: public static void main(String[] args) { ArrayList list = new ArrayList(12,3); list.copyList(); } So when the copyList method is called on the current object "list" it takes list and copies its contents into an entirely seperate arraylist. Is that right? – yre Apr 10 '17 at 21:51
  • But when main method runs and a new arrayList is made and then that arraylist object "list" calls the copyList method, where in the copyList method does know to copy all the contents of the method calling it? That's the leap I don't see. Like list.copyList() that gets called, but list isn't passed into that method? it's just caling it, how does the method copyList know how to extract all the content out of that "list" object? – yre Apr 10 '17 at 21:57
  • I think maybe it would make more sense if that copy method was like: public list copyList() { ArrayList copy = new ArrayList(this.key, this.value); return copy; } – yre Apr 10 '17 at 21:58
  • Or is the "this" part already inferred, since the current object would have to be calling it? – yre Apr 10 '17 at 21:59
  • So it essentially copies EVERYTHING from the CURRENT object, because the current object would be the only one that could call it because it would be CURRENT at that moment, So when it calls that method, the method knows that it will be the current object and when the operations are being carried out in that method all the stuff it there is being related/inferred to the CURRENT OBJECT calling it at that moment – yre Apr 10 '17 at 22:02
  • so all the "this's" I put in there would pretty much still be there but since it's already the current object calling it, the "this's" are not needed. So it just knows that's the current object calling it and the method follows along knowing that and picking out the content of the current object caller. Is that right? – yre Apr 10 '17 at 22:02
  • So the is the original signature because that's what it means to be a NotEmptyTree. It has to be there, that's what it is. And same with the call to its constructor, the call to that constructor is actually a call to the CURRENT OBJECTS constructor, and the is actually a mirroring of the of the CURRENT OBJECT. So since it's the current object it follows along and grabs all that stuff from the CALLER OBJECT. – yre Apr 10 '17 at 22:04
  • When that method gets called, it's infered the object that's calling it is the current object. So it takes the K,V and mirrors uses the same instance variables from the CALLER OBJECT, and then the stuff in the constructor it just takes that stuff from the CALLER OBJECT too, so it's all just inferred information from the CALLER OBJECT. – yre Apr 10 '17 at 22:06
  • The K,V....the caller object has, so it's mirrored. The key and value, the caller object has already, so it's just mirrored. The leftSubTree the caller object already has. The rightSubTree the caller object already has. But unlike the K,V and key and value, those are givens, no extra computations needs to be carried out. Except for the trees, because those have multiple steps/levels so a recursive operation must be carried out in order to get all that CONTENT. so the K,V and the Key, Values stay the same after each recursive call but the copyTree is repeatedly refined till two nulls are found. – yre Apr 10 '17 at 22:11
  • Due to lack of time, I won't be able to answer all of your questions, however I would suggest you read and practice more on generics, recursion, linked lists and tree traversals – RajatJ Apr 11 '17 at 18:17