• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • Devaka Cooray
  • Ron McLeod
  • Jeanne Boyarsky
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Martijn Verburg
  • Frits Walraven
  • Himai Minh

Deep copy in Java

 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi there,

I am writing my own binary tree class and came across a method to create a deep copy of the binary tree. However, I am confused why it actually works. In the code, you'll see that I am doing a recursive call to the treeCopy() method. Why does this recursive call create a deep copy? The reason I think it's a deep copy is this:

I created a binary tree with a source node that has a data node of "grandma" and a left node of "mom" and a right node of "aunt".
Then I activate create a copy of the binary tree and change the root node to "great grandma".
After this, the source tree and copy tree have different root nodes. The source node data is still "grandma" and the copy node data is "great grandma".

However, the parameter treeCopy(BTNode<E> source) is an object, and activating the method with an object argument activates the parameter to reference the same object as the argument. So, why does this create a deep copy?

As an FYI, the treeCopy() method is the final method (starting on row 182).

 
Saloon Keeper
Posts: 14505
325
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Do you mean that you don't understand why the method makes a deep copy of the tree because it doesn't copy source.data, but passes it directly to the constructor for the new tree root?

Well, in the case of a BTNode<String>, the data field of a node is a String, and strings are immutable so they don't really need to be copied. If E is a mutable type, then treeCopy() wouldn't REALLY create a deep copy of the tree, because you could edit the data in the original tree by editing it in the copy tree. By deep copy, they mean a deep copy of the tree structure, not a deep copy of the data it contains.
 
Mj Lewis
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Do you mean that you don't understand why the method makes a deep copy of the tree because it doesn't copy source.data, but passes it directly to the constructor for the new tree root?

Well, in the case of a BTNode<String>, the data field of a node is a String, and strings are immutable so they don't really need to be copied. If E is a mutable type, then treeCopy() wouldn't REALLY create a deep copy of the tree, because you could edit the data in the original tree by editing it in the copy tree. By deep copy, they mean a deep copy of the tree structure, not a deep copy of the data it contains.



Hi Stephan,

Thanks for your reply. I may be misunderstanding your response so I apologize if I am. For my benefit, I'll clarify what I am confused on and hopefully make this easier for me to understand. The reason I am saying it creates a deep copy is this. After I run the method, I have the original and copy tree. If I then go and say original.setData = "New String Name" and check what's in the copy.getLeft(), then copy.getLeft references what it was before modifying the original. For example:



The output of the above is:
Root: Great Grandma
Copy: Grandma

 
Marshal
Posts: 76884
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What is a BTNode? That sort of abbreviation can cause confusion; BT means British Telecom plc to me.

What Stephan means is that you have created a new tree with the same structure as the original, and all the nodes are discrete objects different from the original. If you confine yourself to immutable elements, like the Strings you are using, you will have a tree which behaves as a true copy. Unfortunately there is no universal system for marking objects as immutable or mutable, nor is there a universal system for creating deep copies. The nearest is Object#clone(), but that is problematic and necessitates implementing Cloneable. Actually the basic clone() implementation returns a shallow clone, too, unless you override it carefully. This means you cannot tell whether you need to clone, copy (shallowly or deeply) or share the elements in your tree. If the elements are mutable, however, they allow a change to the state of a copy of your tree to be reflected in the original and vice versa. It is only the tree part that is copied deeply in your example. If you add or remove elements to or from the tree, that change isn't reflected in the other tree. But change of the state of a mutable object is reflected in the other tree, so Stephan is right:-
  • All the branches and nodes are copied deeply and can be changed independently.
  • The elements haven't been copied at all and if any changes can be made, they will be reflected in the other tree.
  •  
    Stephan van Hulst
    Saloon Keeper
    Posts: 14505
    325
    • Likes 1
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I think I understand your question.

    Mj Lewis wrote:However, the parameter treeCopy(BTNode<E> source) is an object, and activating the method with an object argument activates the parameter to reference the same object as the argument.



    You asked how it is that the treeCopy() method is able to create a deep copy of the tree structure, when the parameter inside the method refers to the same object that you passed into the method. (Note that to avoid confusion, use the proper terminology: A method is 'called', not 'activated'.)

    It may be true that the source parameter refers to the original tree, but you don't return the original tree from the treeCopy() method. On line 189, you return a reference to a new object. That object itself also consists of deep copies, because you called the treeCopy() method for each of the sub-trees of the source node.

    If that's not what you're confused about, you need to tell us a little bit more what you expected the method to do instead, if not making a deep copy of the source tree.
     
    Mj Lewis
    Greenhorn
    Posts: 10
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:I think I understand your question.

    Mj Lewis wrote:However, the parameter treeCopy(BTNode<E> source) is an object, and activating the method with an object argument activates the parameter to reference the same object as the argument.



    You asked how it is that the treeCopy() method is able to create a deep copy of the tree structure, when the parameter inside the method refers to the same object that you passed into the method. (Note that to avoid confusion, use the proper terminology: A method is 'called', not 'activated'.)

    It may be true that the source parameter refers to the original tree, but you don't return the original tree from the treeCopy() method. On line 189, you return a reference to a new object. That object itself also consists of deep copies, because you called the treeCopy() method for each of the sub-trees of the source node.

    If that's not what you're confused about, you need to tell us a little bit more what you expected the method to do instead, if not making a deep copy of the source tree.



    Hi Stephan,

    Thanks again for all your help. This is exactly what is confusing me and I think I mostly understand the behavior now based on your response. To make sure I am understanding you properly, I'll summarize directly below...would you mind letting me know if I've understood you correctly?

    The reason that root.setData("new string") doesn't change the data within the copy is because copy is a new object. So, even though the argument given to the treeCopy() method is an object any changes to that object won't impact the copy (or vice versa) because copy actually references an entirely separate object (said differently, copy != source).
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 14505
    325
    • Likes 1
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    You got it.
     
    Mj Lewis
    Greenhorn
    Posts: 10
    • Likes 1
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:You got it.



    Thank you!
     
    I like tacos! And this tiny ad:
    the value of filler advertising in 2021
    https://coderanch.com/t/730886/filler-advertising
    reply
      Bookmark Topic Watch Topic
    • New Topic