$ mkdir ~/cs170/labs/lab28 $ cd ~/cs170/labs/lab28
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.
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.
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:
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.
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
Again, I hate thinking about this iteratively. But you could do it iteratively. My hints, however, will be about the recursive definition.
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.
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.
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.
>>> 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) >>> print(my_tree.breadth_first()) 5 3 8 4 7 6
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.
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 : 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?
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?
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.