Discussion 4:

Trees & Mutability

CS 61A Summer 2019

DISC 104

Attendance: https://tinyurl.com/su19disc4

Announcements

• Midterm and Final will be held 6-9 PM PDT
• Conflicts? Fill out links.cs61a.org/mt-conflict or links.cs61a.org/final-conflict by 7/9 at 11:59 PM PDT
• Code Debugging
• Please use Office Hours/Piazza first
• If you're unable to find the help you need, then please send me an email/ask me in person

Deadlines

• Typing-test
• Phase 1/2 Due 7/12 @11:59PM
• Phase 3 Due 7/23 @11:59PM
• HW 3 Due 7/16 @11:59PM
• Lab 4/5 Due 7/12 @11:59PM

Agenda

• Trees
• Mutability

Trees

Intro

Tree is a data structure

​

For now, we'll implement them using an ADT

Definitions

1

2

3

4

5

6

1

2

3

4

5

6

Nodes

1

2

3

4

5

6

Labels

1

2

3

4

5

6

Parent

Node

Child

Nodes

1

2

3

4

5

6

Parent

Node

Child

Nodes

1

2

3

4

5

6

Root

Branch

Branch

1

2

3

4

5

6

Root

Branch

Branch

Leaf

Depth = 2

Depth = 1

Depth = 0

1

2

3

4

5

6

Height = 2

ADT Tree

Constructor

def tree(label, branches=[]):

for branch in branches:

assert is_tree(branches)

return [label] + list(branches)

Selectors

def label(tree):

return tree[0]

​

def branches(tree):

return tree[1:]

#For convenience

def is_leaf(tree):

return not branches(tree)

Defining a tree

1

2

3

4

5

Defining a tree

1

2

3

4

5

t = tree(1, [

tree(2, [

tree(4),

tree(5)]),

tree(3)])

t = tree(1, [tree(2, [tree(4), tree(5)]), tree(3)])

Sanity Check

For each question, what is the result? Does it violate the abstraction barrier?

​

• label(t)

​

• t[0]

​

• label(branches(t)[0])

​

• is_leaf(t[1:][1])

​

• [label(b) for b in branches(t)]

​

t = tree(1, [tree(2, [tree(4), tree(5)]), tree(3)])

Sanity Check

For each question, what is the result? Does it violate the abstraction barrier?

​

• label(t)

1

• t[0]

​

• label(branches(t)[0])

​

• is_leaf(t[1:][1])

​

• [label(b) for b in branches(t)]

​

t = tree(1, [tree(2, [tree(4), tree(5)]), tree(3)])

Sanity Check

For each question, what is the result? Does it violate the abstraction barrier?

​

• label(t)

1

• T[0] #violation

1

• label(branches(t)[0])

​

• is_leaf(t[1:][1])

​

• [label(b) for b in branches(t)]

​

t = tree(1, [tree(2, [tree(4), tree(5)]), tree(3)])

Sanity Check

For each question, what is the result? Does it violate the abstraction barrier?

​

• label(t)

1

• T[0] #violation

1

• label(branches(t)[0])

2

• is_leaf(t[1:][1])

​

• [label(b) for b in branches(t)]

​

t = tree(1, [tree(2, [tree(4), tree(5)]), tree(3)])

Sanity Check

For each question, what is the result? Does it violate the abstraction barrier?

​

• label(t)

1

• T[0] #violation

1

• label(branches(t)[0])

2

• is_leaf(t[1:][1]) #violation

True

• [label(b) for b in branches(t)]

​

t = tree(1, [tree(2, [tree(4), tree(5)]), tree(3)])

Sanity Check

For each question, what is the result? Does it violate the abstraction barrier?

​

• label(t)

1

• T[0] #violation

1

• label(branches(t)[0])

2

• is_leaf(t[1:][1]) #violation

True

• [label(b) for b in branches(t)]

[2, 3]

t = tree(1, [tree(2, [tree(4), tree(5)]), tree(3)])

Box and Pointer Diagrams

Example

lst = [1, 2, [3, 4]]

1

2

3

4

lst

Mutation

Definition

We say that some objects are mutable if their contents or state can be changed over the course of program execution

​

>>> lst = [1, 2, 3, 4]

>>> lst[0]

1

>>> lst[0] = 3

>>> lst[0]

3

Examples

Mutating Lists

.append(el)

Adds exactly one extra element to the list; uses pointer (b&pd) if the input doesn’t fit

​

>>> lst = [0]

>>> lst.append(1)

>>> lst

[0, 1]

>>> lst.append([2, 3])

>>> lst

[0, 1, [2, 3]]

.extend(seq)

Puts all elements from the sequence and adds it directly to the end of the original list

*takes in a sequence as an argument*

​

>>> lst = [1]

>>> lst.extend([2, 3, 4, 5])

>>> lst

[1, 2, 3, 4, 5]

​

Valid?

>>> lst = [1, 2]

>>> lst.append(3, 4)

​

​

>>> lst = [1, 2]

>>> lst.extend(3)

​

​

>>> lst = [1, 2]

>>> lst.append([3, 4])

Valid?

>>> lst = [1, 2]

>>> lst.append(3, 4)

​

​

>>> lst = [1, 2]

>>> lst.extend(3)

​

​

>>> lst = [1, 2]

>>> lst.append([3, 4])

Valid?

>>> lst = [1, 2]

>>> lst.append(3, 4)

​

​

>>> lst = [1, 2]

>>> lst.extend(3)

​

​

>>> lst = [1, 2]

>>> lst.append([3, 4])

Valid?

>>> lst = [1, 2]

>>> lst.append(3, 4)

​

​

>>> lst = [1, 2]

>>> lst.extend(3)

​

​

>>> lst = [1, 2]

>>> lst.append([3, 4])

A note on

+= and =+

"+=" and extend are the same thing (in terms of lists)

​

lst.extend([2, 3])

lst += [2, 3]

​

"=+" and extend ARE NOT the same thing (in terms of lists)

​

lst.extend([2, 3])

lst = lst + [2, 3]

​

Other useful mutation functions

.insert(i, elem)

• inserts "elem" in index i

.remove(elem)

• removes the first occurence of "elem" in list, otherwise errors

.pop(i)

• Removes and returns the element at index i (if no index provided, pop the last element)