CSC148H lab -- week 6

Here are the instructions for the week 6 CSC148H lab. To earn your lab mark, you must actively participate in the lab. As always, you will work as a pair, taking turns being the driver and the navigator. The driver types, and the navigator watches for mistakes, thinking ahead. At the end of each exercise, show your TA what you've done, and then switch roles.

This week's exercises are on the topic of binary search trees and iterators.

Exercise 1: Understanding bst.py

Download the file bst.py. This is the implementation of the binary search tree that we looked at the past week in class. The delete method is split into two different cases. For the case in which N, the node being deleted, has 0 or 1 children, the delete method simply eliminates N by promoting its child up to N's current position.

However, for the case in which N has two children, the delete method has to do something more sophisticated in order to remove the node. Promoting one of N's child nodes is not an option, since the BST property may no longer hold. Instead, the delete method has to find another node in the tree that it can put in N's place. One such node that can be safely put in N's place is N's successor node S, which is the next larger node in the tree. S is the leftmost child in N's right subtree, and is guaranteed to have at most 1 child (in particular, it can only have a right child). This last property of the successor allows us to remove it from its current position quite easily. To place S in N's current position, S's left and right child attributes are updated to be the same as N's left and right child attributes, and then the left child (or right child, whichever is appropriate) of N's parent is set to point to S. This is essentially how the delete method of the TreeNode class in bst.py works. As discussed in lecture, however, the implementation of TreeNode in bst.py doesn't explicitly keep track of a node's parent. This means that whenever the delete method has to modify the parent of the node being deleted, it cannot do it by simply accessing the parent (as is done in the code in your textbook). To get around this problem, the delete method always returns the root node of the current subtree. Whenever a recursive call to delete is made on a node's child, the child attribute (i.e., left or right) is set to point to the value returned by the call. In this way, when the delete method is called on N (the node being deleted), the call will return S (the successor), and the parent node will assign its left child (or right child, whichever is appropriate) to point to S, as required. You can see the details of this in bst.py.

The only goal of this exercise is to ensure that you understand how the delete method in bst.py currently works. To this end, there are two questions in bst.py labelled as "# Ex1 Question: ... ". Answer these questions with your partner. Once you have done this and are convinced that you understand the code, you're ready to move to exercise 2. If you are having trouble understanding the code, ask the TA for assistance.

Exercise 2: Modifying the delete method to use the predecessor node

As some people noticed in lecture, whenever the node being deleted has two children, we don't necessarily have to replace it with its successor node. The predecessor node works just as well. The predecessor of a node N is the largest node smaller than N.

Recall that the successor of a node N that has two children is the leftmost child of N's right subtree. Where is the predecessor of a node N that has two children?

In the TreeNode class, implement the following method

_findMax(self, parent) - returns a two-element list [plargest, largest], where plargest is the parent of the largest node in the current subtree, and largest is the largest node in the current subtree.

Using this method, modify the delete method so that when the node being deleted has two children, it is replaced by its predecessor node instead of its successor. You can do this in a number of steps:

Replace the call to _findMin with an appropriate call to _findMax.
Modify the code that splices out the successor so that it splices out the predecessor
Reset the left and right child of the predecessor appropriately
Return the predecessor instead of the successor

Run bst.py and use the interactive command prompt to add a number of nodes to the tree. You can use the following commands:

put <key> - this adds the node with the label <key> to the tree. Replace <key> with an actual number, e.g. "put 5".
has_key <key> - checks whether the node with label <key> is in the tree. e.g. "has_key 10"
delete <key> - deletes the node with the label <key> from the tree. e.g. "delete 20"

Try deleting some nodes that have two children, and observe how the predecessor node takes the place of the node being deleted. Show your TA.

Exercise 3: Merging Binary Search Trees

Write an iterative function merge(tree1, tree2) that takes two instances of the class BinarySearchTree as arguments, and creates a new binary search tree containing all the nodes of both trees. Do this as follows

Create a new instance of BinarySearchTree
Iterate through the nodes of tree1 and tree2, adding each node's (key,value) pair to the new binary search tree (using the put method)

(The __iter__ method is defined on the BinarySearchTree class, so iterating through the elements should be easy. In particular, you can iterate through the elements of a BST in the same way you can iterate through elements of a Python list or dictionary. )

Test your code. You can print the resulting tree using the print_tree method supplied in bst.py. (Note: print_tree takes as an argument the root node of the tree, not the tree itself).

What do you notice about the general shape of the merged BST? Why does it take this shape? (Hint: consider the order in which the iterator returns nodes.)

Show your TA.

Exercise 4: Set Difference with Binary Search Trees

Write an iterative function diff(tree1, tree2) that takes two instances of the class BinarySearchTree as arguments, and creates a new binary search tree containing the (key,value) pairs from tree1 that are not also in tree2. Test your code and show your TA.

Exercise 5: Determining the depth of a node

In the BinarySearchTree class and the TreeNode classes, create a recursive method get_depth(self, key) that returns the depth of a node with the given key. You can assume the method will only be called when the key exists in the tree. Test your code and show your TA. (Recall that the depth of a node is the number of edges traversed on a path from the root to the node.)