In week 9, we learnt how to mutate BSTs. Basically, mutating a BST involves adding nodes to a BST. To do this, we were shown a class BTNode and initialization of three variables: data, left and right. And then, the professor showed us some code that basically inserted nodal values to form a tree. This was done using the insert function. This code shows the implementation of the insert function:
return_node = node
if not node:
return_node = BTNode(data)
elif data < node.data:
node.left = insert(node.left, data)
elif data > node.data:
node.right = insert(node.right, data)
else:
pass
return return_node
At first, I found this code confusing to understand as I didn't understand why an initial variable was created. But I read it over and over again and I even drew diagrams to try and understand it. Finally, I understood the code and realized that it was just recursion that was "appointed" once again to insert nodes to the left or right of data.
14
12
10
8
6
4
For example, if we were to insert a 2 into this tree, we would have to see if it passed certain conditions to determine where it should be situated. Firstly, there is a node here, so the base case is ignored. Then, we have to see if the data passed is less than node.data. In this case, is 2 less than 8? Yes, so we move it down the left side. Then, is 2 less than 4? Yes, so we situate 2 to the bottom left of 4.
14
12
10
8
6
4
2
The same thing can be done for values larger than node.data, except then, the values would be shifted right in the tree. As for the deletion of data from a BST, we have to check for certain conditions to see where to delete data and shift previously attached data.
This slog explain 3 cases encountered when deleting data from a BST. I found this explanation very helpful to understand on deleting data. It mentions about the base case, where only one node has to be deleted, a case where a node with only one child has to be deleted, and where recursion needs to be used in order to determine which data needs to be deleted. The person who wrote this slog also mentioned that this may not work when there are duplicate nodes. But one way to solve this is by passing the address of the node to be deleted, as the address of each node is unique. It was interesting to learn this important tip from this slog, and this is why I have included the link for it as well.
http://theremustbe.blogspot.ca/2015/03/week-9-mutating-bst.html
12
10
8
6
4
For example, if we were to insert a 2 into this tree, we would have to see if it passed certain conditions to determine where it should be situated. Firstly, there is a node here, so the base case is ignored. Then, we have to see if the data passed is less than node.data. In this case, is 2 less than 8? Yes, so we move it down the left side. Then, is 2 less than 4? Yes, so we situate 2 to the bottom left of 4.
14
12
10
8
6
4
2
The same thing can be done for values larger than node.data, except then, the values would be shifted right in the tree. As for the deletion of data from a BST, we have to check for certain conditions to see where to delete data and shift previously attached data.
This slog explain 3 cases encountered when deleting data from a BST. I found this explanation very helpful to understand on deleting data. It mentions about the base case, where only one node has to be deleted, a case where a node with only one child has to be deleted, and where recursion needs to be used in order to determine which data needs to be deleted. The person who wrote this slog also mentioned that this may not work when there are duplicate nodes. But one way to solve this is by passing the address of the node to be deleted, as the address of each node is unique. It was interesting to learn this important tip from this slog, and this is why I have included the link for it as well.
http://theremustbe.blogspot.ca/2015/03/week-9-mutating-bst.html
No comments:
Post a Comment