cmc-csci046

cmc-csci046 copied to clipboard

I'm encountering a memory management issue in my _remove function, and although I figured out how to resolve it, I don't understand why things work the way they do. Here is some code for the function:

1    @staticmethod
2      def _remove(node, value):
3          if node.value == value:
4              if node.left == None and node.right == None:5
5                  node = None
6              elif node.left and node.right == None:
7                  node = node.left
8              elif node.right and node.left == None:
9                  node.value = node.right.value
10                 node.right = node.right.right
11             else:
12                 succ = node.find_successor()
13                 node.value = succ
14         if node.left:
15             if value < node.value:
16                 return BST._remove(node.left, value)
17         if node.right: 
18            if value > node.value:
19                BST._remove(node.right, value)

When I use the notation on lines 5 and 7, of the form "node =" this does not actually alter the input node. However, I am able to fix this issue with the strategy I adopt in lines 9 and 10--altering the value and right child of the node actually does alter the input node itself. I am confused as to why this might be the case. Does anyone have any ideas?

Update: this is still an actual issue because in the case that both the left and right childs are None, I don't know a workaround for "node = None"-- just changing the value to None causes issues down the road.

Consider line 5, where you say:

5                  node = None

This does not delete the object that node references. Instead, it just makes node point to None. The previous parent of node still will be pointing to the object, and so you must delete the node inside the parent by setting it's left/right child to None.

That's an extremely brief explanation, but pictures and in-person conversation would be needed for a more detailed explanation.