CS61A Lab 9: Recursive Data - Trees and Sets

Week 9, 2012



General Trees (with infinite children)

Trees are a way we have of representing a hierarchy of information. A family tree is a good example of something with a tree structure. You have a matriarch and a patriarch followed by all the descendants. Alternately, we may want to organize a series of information geographically. At the very top, we have the world, but below that we have countries, then states, then cities. We can also decompose arithmetic operations into something much the same way.

The name “tree” comes from the branching structure of the pictures, like real trees in nature except that they’re drawn with the root at the top and the leaves at the bottom.

Terminology

	node 		-	a point in the tree. In these pictures, each node includes a label (value at each node)
	root 		- 	the node at the top. Every tree has one root node
	children	- 	the nodes directly beneath it. Arity is the number of children that node has.
	leaf 		- 	a node that has no children. (Arity of 0!) 
The following exercises are about itrees. To use the itree data abstraction,

In your terminal:

	cp ~cs61a/public_html/su12/lab/lab07/lab7.py .

Open the python interpreter:

	from lab7 import *

Take a moment to study the implementation of itrees. Look at the constructors, selectors, and printing methods. We give you some premade trees that you can work with for each section.

Now, after loading the file, the variable kennedy contains the following ree:

Use the correct series of selectors to return the value “Caroline” from the tree.

Mutual Recursion

Mutual Recursion occurs when you have a function that will deal with Trees, as well as a function that will deal with Forests (sequences of Trees). Both functions call each other to solve whatever problem is at hand.

def square_itree(itree):
    return make_itree(square(itree.label), *square_forest(itree_iter(itree)))

def square_forest(forest):
    new_forest = ()
    for itree in forest:
        new_forest += (square_itree(itree),)
    return new_forest

The variable t is defined in tree.py and is a itree of integers that you can use to test your functions. Try out the following to see how it works.

>>> print(itree_str(t))
_______________
>>> st = square_itree(t)
>>> print(itree_str(st))
_______________

Exercise: Draw your interpretation of this tree on a piece of paper

Question 1:

Define the function max_of_itree which takes in a itree as an argument and returns the max of all of the values of each node in the itree.

>>> print(itree_str(t))
4
|
+-2
| |
| +-8
| | |
| | +-7
| |
| +-3
|   |
|   +-1
|   |
|   +-6
|
+-1
| |
| +-5
|
+-3
  |
  +-2
  |
  +-9
>>> max_of_itree(t)
9

Question 2:

Define the function deep_tree_reverse, which takes a tree and reverses the given order.

>>> print(itree_str(deep_tree_reverse(t)))
4
|
+-3
| |
| +-9
| |
| +-2
|
+-1
| |
| +-5
|
+-2
  |
  +-3
  | |
  | +-6
  | |
  | +-1
  |
  +-8
    |
    +-7

Question 3:

Define the function filter_itree which takes in a itree as an argument and returns the same itree, but with items included or excluded based on the pred argument.

Note that there is ambiguity about what excluding a tree means. For this function, when you exclude a subtree, you exclude all of its children as well.

>>> print(itree_str(filter_itree(t, lambda x: x%2==0 )))
4
|
+-2
  |
  +-8
>>> print(itree_str(filter_itree(t, lambda x: x > 2 )))
4
|
+-3
  |
  +-9

Binary Search Trees

Binary Search Trees are a special case of regular Trees that are useful for organizing data and searching through it efficiently. Binary search trees have 2 special properties apart from regular trees:

To illustrate this, first, draw these trees out on a piece of paper. Then, determine if the trees are valid binary search trees. Some are solved for you, and the rest are given to you as an exercise.

Note: bst_str prints out the left subtree first, and then the right subtree.

  1. 
    VALID
    >>> print(bst_str(bst_a))
    3
    |
    +-1
    | |
    | +-0
    | |
    | +-empty_bst
    |
    +-5
      |
      +-empty_bst
      |
      +-6
      
  2. INVALID
    >>> print(bst_str(bst_b))
    3
    |
    +-1
    | |
    | +-empty_bst
    | |
    | +-0
    |
    +-5
      |
      +-empty_bst
      |
      +-6
    
  3. >>> print(bst_str(bst_c)) VALID
    6
    |
    +-5
    | |
    | +-4
    | | |
    | | +-3
    | | | |
    | | | +-2
    | | | | |
    | | | | +-1
    | | | | |
    | | | | +-empty_bst
    | | | |
    | | | +-empty_bst
    | | |
    | | +-empty_bst
    | |
    | +-empty_bst
    |
    +-empty_bst
    
  4. >>> print(bst_str(bst_d)) INVALID
    5
    |
    +-4
    | |
    | +-1
    | | |
    | | +-empty_bst
    | | |
    | | +-2
    | |
    | +-empty_bst
    |
    +-9
      |
      +-6
      | |
      | +-empty_bst
      | |
      | +-8
      |   |
      |   +-7
      |   |
      |   +-empty_bst
      |
      +-empty_bst
    

Question 1:

Write a function valid_bst, that takes a given bst, and returns True if the bst is a valid binary search tree; that is, for every node, that node's left children are less than the node, and that node's right children are greater than that node. Test your function with the given binary search trees from above (these are already typed out in the lab7.py file) to make sure your function works properly.

Question 2:

Write a function bst_count_num which takes two arguments, bst and max. bst_count should return the number of items in the tree that are less than the given max. Implement bst_count in the following ways:

  1. Using the bst_find function.
  2. Using recursion.
  3. ITERATION VERSION REMOVED BECAUSE TOO COMPLICATED

Question 3:

Write a function is_right_bigger, which takes a single argument bst, and returns whether or not the right subtree in this bst is larger (has more items) than the left subtree. Hint: You might want to use a helper function.

>>> is_right_bigger(bst_c)
False
>>> is_right_bigger(bst_d)
True