$ mkdir ~/cs170/labs/lab29 $ cd ~/cs170/labs/lab29
You saw on Monday how we can build a binary tree following the rules of a binary tree. You also saw how to perform a pre-order, depth first traversal of a tree. I'll show you the other depth first traversals today in class. However, you should note that depth first is not the only way to traverse through a tree. There are also breadth first traversals. Depending on your goals, it might make more sense to perform one over the other.
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, which breadth-first uses a queue.
Copy your binary_tree.py file from last class into your current directory:
$ cd ~/cs170/labs/lab29 $ cp ../lab28/binary_tree.py .
Add a new method to your BinaryTree 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?
Now we can finally see why we would use a Binary Tree, other than just building them and playing around with them. A tree of the form we have been building is called a "Binary Search Tree." Essentially, they are trees that have the ordering property defined on them. This should mean that Binary Search should work pretty well on a Binary Search Tree. Let's try it out.
In your binary_tree.py file, write a new method in the BinaryTree class
called search(self, data). This function should return
True if data is in the binary tree, and False otherwise.
Again, there are two ways to accomplish this function: iteratively or recursively. Write any additional functions or methods you may need to accomplish your tasks. Write your estimation of the Big-Oh class of search, based on the number of nodes N in the tree, in the comments of your file.
>>> my_list = [5, 3, 4, 8, 9] >>> my_tree = BinaryTree() >>> for element in my_list: ... my_tree.insert(element) >>> print(my_tree.search(5)) True >>> print(my_tree.search(9)) True >>> print(my_tree.search(10)) False >>> print(my_tree.search(6)) False
Binary search on a list involved finding the middle element of the list. Such an element doesn't quite exists in a tree. Instead, you are going to look at the data of the current element, to decide if you should explore down the left sub-tree, or the right sub-tree.
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 lab29
directory. To create a tar file, execute the following commands:
cd ~/cs170/labs tar czvf lab29.tgz lab29/
To submit your activity, go to cseval.roanoke.edu. You should
see an available assignment called Lab Assignment 29.
Make sure you include a header listing the authors of the file.
Create a directory called week11_homework, which will hold your homework for this week:
$ cd ~/cs170/ $ mkdir week11_homework $ cd week11_homework
One of the applications of a binary search tree is the fact that it can be used to implement a relatively simple sorting algorithm. The process is pretty straight forward: insert all of the elements of the list to be sorted into the tree. Then, perform a in-order traversal to determine the order to put the items back into the list.
Create a file called tree_sort.py. You will need to import
your binary_tree.py file, so you can use your binary tree in
this problem. Write a function tree_sort(a_list), which
takes a list of integers, and returns a sorted copy of that list.
>>> print(tree_sort([4, 3, 5, 1, 2])) [1, 2, 3, 4, 5]
We have seen binary search on a python list. This was faster than linear search, because we knew how to get to the middle element directly. For a linked list, this is not the case. We can still write the algorithm for binary search, but it might not be as efficient anymore.
Write a function binary_search_linked(linked_list, element), which
takes a linked list as a paramter. It should return True if
the element is in the list, and false otherwise. You should perform
the typical binary search operations for this one: find the middle
element of the list, determine which half of the list to explore
further, then explore that half of the list.