You are being recorded and transcribed.
Approximate overview
Academic/Scholarly
Cultural
Peer
Wellness
Misc
NO! You do not get tokens for Wonderland Harris.
A tree is a data structure (or perhaps an ADT) (or perhaps just a way to think about information) that organizes information hierarchically.
In contrast with lists (and stacks and queueus and arrays and …), which we think of as one-dimensional, lists are somewhat two-dimensional.
A node in a tree contains a value (or, at times, a key/value pair), and zero or more subtrees. (Subtrees are also referred to as “children”.)
In a binary tree, each node has zero, one, or two subtrees. The subtrees are usually identified as left and right. (We will generally work with binary trees.)
Different policies on ordering the values (or keys, for key/value pairs) in a tree affect how we use them.
Suppose we want to visit (process, iterate) all the nodes in a tree. What are possible orderings?
We can go across the nodes at each level (breadth-first) or we can fully visit each subtree before visiting the other (depth-first).
We can visit the left subtree before the right (left-to-right) or the right subtree before the left (right-to-left).
We can visit/process a node before its subtrees (preorder), between the left and right subtrees (inorder), or after both subtrees (postorder). It turns out there can be value in each processing/iteration strategy.
We’ll explore these choices while writing iterators and similar things.
Explorations with a particular kind of binary tree.
Sam rambled about this for a bit.
I hear that the evening tutors had a bunch of basic questions last night (but not what they were). Note that Elene also had a mentor session on the MP.
What should the list look like when it’s empty?
One dummy node. Its
nextfield should refer to the dummy node. Itsprevfield should also refer to the dummy node.
Do I ever have to skip the fail fast check if I’m using the natural solution of having a “changes” field in both iterators and the list?
You should always do the fail fast check in any function in the iterator.
Should my failFast method change the count?
No. It’s not changing the list.
When do I increment the counter for the iterator in the list?
In
addandremove(but notset, at least as I understand it).
Do I have to check whether the list has changed before incrementing?
Yes, you should have. If you create a separate method, you can make that a precondition.
public void add(T val) throws SomeSortOfStateException {
failFast();
...
noteUpdate();
} // add(T)
Some strange things are happening in the experiments.
Check where you are starting your iterator. Is its prev field the dummy node and is its next field
prev.next?
Can we have some unit tests?
Already posted to Gradescope.
Any suggestions?
Draw pictures!
How long did it take Sam to do this assignment?
You don’t want to know.
Yes I do.
15 minutes to update DLL to CDLL.
2+ hours to write all the unit tests.
5 minutes to fix the errors in CDLL (which Sam should have noticed because it didn’t compile).
But Sam has been implementing doubly linked lists for longer than any of you have been alive.
Would have have been better off dumping the tree using in-order traversal?
pre-order, left->right, depth-first
in-order, left->right, depth-first