Lab 9: Mutable Trees, Linked Lists
Due by 11:59pm on Tuesday, July 25.
Starter Files
Download lab09.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.
Topics
Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.
Mutable Trees
We define a tree to be a recursive data abstraction that has a label
(the
value stored in the root of the tree) and branches
(a list of trees directly
underneath the root).
Previously we implemented trees by using a functional data abstraction, with the tree
constructor function and the label
and branches
selector functions. Now we implement trees by creating the Tree
class. Here is part of the class included in the lab.
class Tree:
"""
>>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
>>> t.label
3
>>> t.branches[0].label
2
>>> t.branches[1].is_leaf()
True
"""
def __init__(self, label, branches=[]):
for b in branches:
assert isinstance(b, Tree)
self.label = label
self.branches = list(branches)
def is_leaf(self):
return not self.branches
Even though this is a new implementation, everything we know about the functional tree data abstraction remains true. That means that solving problems involving trees as objects uses the same techniques that we developed when first studying the functional tree data abstraction (e.g. we can still use recursion on the branches!). The main difference, aside from syntax, is that tree objects are mutable.
Here is a summary of the differences between the tree data abstraction implemented as a functional abstraction vs. implemented as class:
- | Tree constructor and selector functions | Tree class |
---|---|---|
Constructing a tree | To construct a tree given a label and a list of branches , we call tree(label, branches) |
To construct a tree object given a label and a list of branches , we call Tree(label, branches) (which calls the Tree.__init__ method). |
Label and branches | To get the label or branches of a tree t , we call label(t) or branches(t) respectively |
To get the label or branches of a tree t , we access the instance attributes t.label or t.branches respectively. |
Mutability | The functional tree data abstraction is immutable because we cannot assign values to call expressions | The label and branches attributes of a Tree instance can be reassigned, mutating the tree. |
Checking if a tree is a leaf | To check whether a tree t is a leaf, we call the convenience function is_leaf(t) |
To check whether a tree t is a leaf, we call the bound method t.is_leaf() . This method can only be called on Tree objects. |
Linked Lists
We've learned that a Python list is one way to store sequential values. Another type of list is a linked list. A Python list stores all of its elements in a single object, and each element can be accessed by using its index. A linked list, on the other hand, is a recursive object that only stores two things: its first value and a reference to the rest of the list, which is another linked list.
We can implement a class, Link
, that represents a linked list object. Each
instance of Link
has two instance attributes, first
and rest
.
class Link:
"""A linked list.
>>> s = Link(1)
>>> s.first
1
>>> s.rest is Link.empty
True
>>> s = Link(2, Link(3, Link(4)))
>>> s.first = 5
>>> s.rest.first = 6
>>> s.rest.rest = Link.empty
>>> s # Displays the contents of repr(s)
Link(5, Link(6))
>>> s.rest = Link(7, Link(Link(8, Link(9))))
>>> s
Link(5, Link(7, Link(Link(8, Link(9)))))
>>> print(s) # Prints str(s)
<5 7 <8 9>>
"""
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
def __repr__(self):
if self.rest is not Link.empty:
rest_repr = ', ' + repr(self.rest)
else:
rest_repr = ''
return 'Link(' + repr(self.first) + rest_repr + ')'
def __str__(self):
string = '<'
while self.rest is not Link.empty:
string += str(self.first) + ' '
self = self.rest
return string + str(self.first) + '>'
A valid linked list can be one of the following:
- An empty linked list (
Link.empty
) - A
Link
object containing the first value of the linked list and a reference to the rest of the linked list
What makes a linked list recursive is that the rest
attribute of a single
Link
instance is another linked list! In the big picture, each Link
instance stores a single value of the list. When multiple Link
s are linked
together through each instance's rest
attribute, an entire sequence is
formed.
Note: This definition means that the
rest
attribute of anyLink
instance must be eitherLink.empty
or anotherLink
instance! This is enforced inLink.__init__
, which raises anAssertionError
if the value passed in forrest
is neither of these things.
To check if a linked list is empty, compare it against the class attribute
Link.empty
. For example, the function below prints out whether or not the
link it is handed is empty:
def test_empty(link):
if link is Link.empty:
print('This linked list is empty!')
else:
print('This linked list is not empty!')
Required Questions
Getting Started Videos
These videos may provide some helpful direction for tackling the coding problems on this assignment.
To see these videos, you should be logged into your berkeley.edu email.
Midsemester Survey
Q1: Mid-Semester Feedback
As part of this lab, please fill out the Mid-Semester Feedback form.
This survey is designed to help us make short term adjustments to the course so that it works better for you. We appreciate your feedback. We may not be able to make every change that you request, but we will read all the feedback and consider it.
Confidentiality: Your responses to the survey are confidential, and only the instructors and head TAs will be able to see this data unanonymized. More specifics on confidentiality can be found on the survey itself.
Once you finish the survey, you will be presented with a passphrase (if you miss
it, it should also be at the bottom of the confirmation email you receive). Put
this passphrase, as a string, on the line that says
passphrase = '*** PASSPHRASE HERE ***'
in the Python file for this assignment.
Use Ok to test your code:
python3 ok -q midsem_survey
Mutable Trees
Q2: Make Even
Define a function make_even
which takes in a tree
t
whose values are integers, and mutates the tree such that all the
odd integers are increased by 1 and all the even integers remain the same.
def make_even(t):
"""
>>> t = Tree(1, [Tree(2, [Tree(3)]), Tree(4), Tree(5)])
>>> make_even(t)
>>> t.label
2
>>> t.branches[0].branches[0].label
4
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q make_even
Q3: Delete
Implement delete
, which takes a Tree t
and deletes any occurrence of
x
within it. The order of the branches must be preserved.
Important: When a non-leaf node is deleted, the deleted node's children should be attached to the deleted node's parent. You may assume that the root of the tree will never be deleted.
def delete(t, x):
"""
Delete any occurrence of the 'x' within Tree 't'. When a non-leaf
node is deleted, the deleted node's children should be attached to
its parent. The order of the branches must be preserved.
Assume that the root will never be deleted.
>>> t = Tree(3, [Tree(2, [Tree(2), Tree(2)]), Tree(2), Tree(2, [Tree(2, [Tree(2), Tree(2)])])])
>>> delete(t, 2)
>>> t
Tree(3)
>>> t = Tree(1, [Tree(2, [Tree(4, [Tree(2)]), Tree(5)]), Tree(3, [Tree(6), Tree(2)]), Tree(4)])
>>> delete(t, 2)
>>> t
Tree(1, [Tree(4), Tree(5), Tree(3, [Tree(6)]), Tree(4)])
>>> t = Tree(1, [Tree(2, [Tree(4), Tree(5)]), Tree(3, [Tree(6), Tree(2)]), Tree(2, [Tree(6), Tree(2), Tree(7), Tree(8)]), Tree(4)])
>>> delete(t, 2)
>>> t
Tree(1, [Tree(4), Tree(5), Tree(3, [Tree(6)]), Tree(6), Tree(7), Tree(8), Tree(4)])
"""
new_branches = []
for _________ in ________________:
_______________________
if b.label == x:
__________________________________
else:
__________________________________
t.branches = ___________________
Use Ok to test your code:
python3 ok -q delete
Linked Lists
Q4: Flip Two
Write a recursive function flip_two
that takes as input a
linked list s
and mutates s
so that every pair of values in the linked list
is flipped.
def flip_two(s):
"""
>>> one_lnk = Link(1)
>>> flip_two(one_lnk)
>>> one_lnk
Link(1)
>>> lnk = Link(1, Link(2, Link(3, Link(4, Link(5)))))
>>> flip_two(lnk)
>>> lnk
Link(2, Link(1, Link(4, Link(3, Link(5)))))
"""
"*** YOUR CODE HERE ***"
# For an extra challenge, try writing out an iterative approach as well below!
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q flip_two
Check Your Score Locally
You can locally check your score on each question of this assignment by running
python3 ok --score
This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.
Submit
Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.
Optional Questions
Q5: Multiply Links
Write a function that takes in a Python list of linked lists and multiplies them element-wise. It should return a new linked list.
If not all of the Link
objects are of equal length, return a
linked list whose length is that of the shortest linked list given. You
may assume the Link
objects are shallow linked lists, and that
lst_of_lnks
contains at least one linked list.
def multiply_lnks(lst_of_lnks):
"""
>>> a = Link(2, Link(3, Link(5)))
>>> b = Link(6, Link(4, Link(2)))
>>> c = Link(4, Link(1, Link(0, Link(2))))
>>> p = multiply_lnks([a, b, c])
>>> p.first
48
>>> p.rest.first
12
>>> p.rest.rest.rest is Link.empty
True
"""
___________________ = ___________
for _________ in ________________:
if __________________________________________:
_________________________________
___________________
________________________________________________________
________________________________________________________
Use Ok to test your code:
python3 ok -q multiply_lnks
Q6: Level Mutation Link
As a reminder, the depth of a node is how far away the node is from the root. We define this as the number of edges between the root to the node. As there are no edges between the root and itself, the root has depth 0.
Given a tree t
and a linked list of one-argument functions funcs
, write a function that will mutate the labels of t
using the function from funcs
at the corresponding depth. For example, the label at the root node (with a depth of 0) will be mutated using the function at funcs.first
. Assume all of the functions in funcs
will be able to take in a label value and return a valid label value.
If t
is a leaf and there are more than 1 functions in funcs
, all of the remaining functions should be applied in order to the label of t
. (See the doctests for an example.) If funcs
is empty, the tree should remain unmodified.
def level_mutation_link(t, funcs):
"""Mutates t using the functions in the linked list funcs.
>>> t = Tree(1, [Tree(2, [Tree(3)])])
>>> funcs = Link(lambda x: x + 1, Link(lambda y: y * 5, Link(lambda z: z ** 2)))
>>> level_mutation_link(t, funcs)
>>> t
Tree(2, [Tree(10, [Tree(9)])])
>>> t2 = Tree(1, [Tree(2), Tree(3, [Tree(4)])])
>>> level_mutation_link(t2, funcs)
>>> t2
Tree(2, [Tree(100), Tree(15, [Tree(16)])])
>>> t3 = Tree(1, [Tree(2)])
>>> level_mutation_link(t3, funcs)
>>> t3
Tree(2, [Tree(100)])
"""
if _____________________:
return
t.label = _____________________
remaining = _____________________
if __________________ and __________________:
while _____________________:
_____________________
remaining = remaining.rest
for b in t.branches:
_____________________
Use Ok to test your code:
python3 ok -q level_mutation_link