CODEWITHSUNDEEP
pythonclass
meto
meto

Reputation: 3719

Nodes of a graph in Python

I am trying to figure out the best way of coding a Node Class (to be used in a binary tree) that would contain the attributes key, left and right.

I thought I would do something like

class Node:
    def __init__(self, key):
        self.key= key
        self.left = None
        self.right = None

and then do

a = Node('A')
b = Node('B') 
c = Node('C')   
a.left = b
a.right = c

Here I am a little bit confused: are (under the hood) left and right pointers? Or is a containing a copy of the whole tree?

If I add

d = Node('B') # same key as before, but an entirely different node
c.right = d

then are b and d two different objects even if they have the same attributes? I would think so because they don't share any memory.

Finally, if I want to do a deep copy of one of my nodes, is

e = Node(a.key))

sufficient?

Upvotes: 0

Views: 679

Answers (3)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477686

Python is dynamically typed, so you can't say left and right are references. One can also store an integer, or float in them. You can even first store an integer then a reference to an object and later a float in them, so the type might vary over time. But if you perform an assignment to an object. That will indeed result in a pointer (this is a huge semantical difference with your question).

For your second question, it depends on how you see deep copying. If your node contains references to other nodes, do you want to copy these nodes as well?

If you are interested only in generating a new node with the same value but with references to the same other nodes, then use: copy.copy, otherwise use copy.deepcopy.

The difference is:

B <- A -> C       B' <- D -> C'
^         ^
|         |
 \-- S --/

With S a shallow copy and D a deep copy. Note that a deep copy thus results in new nodes B' and C'. You can imagine that if you deep copy a huge tree this can result in a large memory and CPU footprint.

Your code

e = Node(a.key))

Is not completely correct since you don't copy (potential) references to your left and right node, and furthermore it's not good design since you can attach more items to the node and you need to modify your copy function(s) each time. Using the copy.copy-functions is thus more safe.

Upvotes: 3

hyades
hyades

Reputation: 3170

Yes these are just references to the left or right object. Everytime you do Node("some_str), a new object is created. So b & d will be different, and a new object gets created for e = Node(a.key)). Doing a e = Node('E') and doing f = e will be the same, with f and e referring to the same object.

Upvotes: 0

Malik Brahimi
Malik Brahimi

Reputation: 16721

Yes b and d have the same attributes, but they are two independent instances. To see this:

print id(b) # one number
print id(d) # new number

This proves that they are two different objects in memory. To see that a.right is the same object as c use the same technique, checking for equivalent id values.

print id(a.right)
print id(c) # same

Upvotes: 2

Related Questions