Lecture 28 - Binary Tree Finale

As usual, create a directory to hold today's activities:

$mkdir ~/cs170/labs/lab28$ cd ~/cs170/labs/lab28

Trees

On Wednesday, we saw how we can search for information inside of a binary tree. That part of the lab went perfectly well. Deleting an element out of the tree, however, caused problems for many people. Before we get a new concept for today, I will go back over how we can delete information from a binary search tree. Keep in mind, the easy way to accomplish this is through BACKTRACKING again. Which means the easiest solution will be recursive.

The final new algorithm we are going to cover today is going to be a new traversal technique: Breadth-first traversal. This traversal technique allows us to see what nodes are at each level of the tree, which can be useful when trying to visualize the tree.

Lab Activity 1

We have added stuff to a binary search tree. However, we occasionally also need to be able to remove information from a binary search tree. Deletion of a leaf is very easy. Deletion of an internal node, however, is slightly more complicated.

Details

In your binary_tree.py file, write a new method in the BinarySearchTree class called delete(self, data). This function returns nothing. It only removes the node containing the data from the tree.

There are three cases for deleting a node N in the tree:

No Children
None should be put in place of N.
One Child
The remaining child should be put in place of N.
Two Children
Find the in-order successor of N in the tree. This is the left most value in the right sub tree of N. Place the successor value in the node N, then set the right child of N to be the result of recursively deleting successor starting at N.

Write a method called delete_helper(self, curr_node, data), which takes a node as a parameter as well. That is the node that all deletions will be done relative to. THIS METHOD SHOULD RETURN A NODE, which is the node that should replace curr_node in the modified tree. This is similar to the "easier" method of inserting a node into a tree, as shown in class today.

Example

my_list = [5, 3, 4, 1, 8, 7, 9]
my_tree = BinarySearchTree()
for element in my_list:
my_tree.insert(element)
print(my_tree.pre_order())
#5 3 1 4 8 7 9

my_tree.delete(4)
print(my_tree.pre_order())
#5 3 1 8 7 9

my_tree.delete(7)
print(my_tree.pre_order())
#5 3 1 8 9

my_tree.delete(3)
print(my_tree.pre_order())
#5 1 8 9

my_tree.delete(8)
print(my_tree.pre_order())
#5 1 9

my_tree.delete(5)
print(my_tree.pre_order())
#9 1

Hint

• Again, I hate thinking about this iteratively. But you could do it iteratively. My hints, however, will be about the recursive definition.

• To assist in deleting later, define a method called get_successor(self, curr_node). This method should return the value contained in the smallest value contained in the tree rooted at curr_node. This is the node that is the farthest "left" in this tree.
• Your delete method needs two phases. Phase 1 is finding the node to remove. This should be very similar to insert.

The second phase is deletion. This should be IN the base case for delete. You have 4 conditions: No children, only a left child, only a right child, and both children. In the no children case, your method should return none. In only left or only right, you return the defined child. Otherwise, you have you find the successor value of the current node, place that data in the current node. Then set the right child of the current node as the result of deleting the successor value from the right sub-tree.

Lab Activity 2

In depth first traversal, we always traversed all the way down one entire branch, before starting to explore another branch of the tree. This led us to having essentially three different forms of depth-first traversals: in-order, pre-order, and post-order. Another form of traversal is known and Breadth-First: It explores all of the nodes at the same depth, before exploring the nodes at a subsequent depth.

We saw this same mechanism at work in our paint bucket programs. If we used a stack, we would essentially try to fill in a weird spiral pattern. With a queue, we would radiate out from the central point. This analogue applies here as well: depth-first uses a stack, where breadth-first uses a queue.

Details

Add a new method to your BinarySearchTree class called breadth_first(self). This function should return a string, representing the breadth-first traversal of the current tree.

Example

>>> my_tree = BinaryTree()
>>> my_tree.insert(5)
>>> my_tree.insert(3)
>>> my_tree.insert(4)
>>> my_tree.insert(8)
>>> my_tree.insert(7)
>>> my_tree.insert(6)
5 3 8 4 7 6

Hint

• For once, I am going to urge you to not write this function recursively. It is possible, but adds unnecessary complications to the entire function.

• Create a queue at the beginning of the program, and add the root of the tree to the queue. This is going to be the initialization of your entire algorithm.

• You are going to loop through the entire queue. You will pull the front element off the queue, and concatenate that to the end of a string you will return from this function. Then, you will try to enqueue the two children of that node into the queue. Make sure you don't enqueue any None nodes!

Challenge

One of the issues with breadth-first traversal is it is unclear which elements are children of other elements. This is partially because an element could appear in multiple places in the tree, depending on when it was inserted. This is especially true for trees that are not well balanced: The tree structure is completely abstracted away!

One simple solution is to make sure that the entire tree is represented in the traversals....even "None" leaves. Write a new method called breadth_traversal_complete(self), which also inserts "None" into the output string for locations that terminate within the tree. Does this completely solve the problem?

Challenge

As you might have noticed, our trees can get quite out of balance. Especially if they are given a list of sorted elements. If we have a list of sorted elements inserted into the tree, our tree is going to almost look like a linked list. There are two ways to handle this issue: balance the trees, or randomly choose which elements to insert.

For now, let's take the simplified approach. Write a new method insert_randomly(self, a_list), which takes a list of elements to insert into the tree. Instead of iteratively inserting all of the elements of the list directly into the tree, insert them into the tree in some random order.

This only helps if it actually reduces how deep the tree actually is. Write a method height(self), which returns how long the longest branch of the tree is. Try inserting lists of size 100 into the tree. What is the average depth of the tree, using this random insert mechanism?

Submission

When you have finished, create a tar file of your lab28 directory. To create a tar file, execute the following commands:

cd ~/cs170/labs
tar czvf lab28.tgz lab28/

To submit your activity, go to inquire.roanoke.edu. You should see an available assignment called Lab Assignment 28. Make sure you include a header listing the authors of the file.