$ mkdir ~/cs170/labs/lab27 $ cd ~/cs170/labs/lab27
You hopefully saw on Monday how we can build a binary tree following the rules of binary search. This is indicitive of how binary search is supposed to work: We know all of the relationships between all of the values in the tree. Today, we will see how that relationship applies to searching for values inside the tree as well. As you can imagine, it is related to how binary search works!
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 BinarySearchTree 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 = BinarySearchTree() >>> 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.
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 root of the tree that has had the information
requested removed. 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 search.
The second phase is deletion. 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.
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
lab27 directory. To create a tar
file, execute the following commands:
cd ~/cs170/labs tar czvf lab27.tgz lab27/
To submit your activity, go
to inquire.roanoke.edu. You
should see an available assignment called Lab Assignment
27. Make sure you include a header
listing the authors of the file.