6.001/Recitation 14

Rob Speer

Contents 1 Three ways to represent a table 2 Binary trees as tables 3 Comparison of orders of growth 4 Purely functional data structures 4.1 Stacks 4.2 Queues 4.3 Trees 5 Improving the worst case: red-black trees 5.1 Ways to fix a red-black tree

Three ways to represent a table

1. Association lists
2. Hash tables, as described in lecture
3. Binary trees

Binary trees as tables

• Advantage: keys are sorted
• Disadvantage: keys are sorted
• Often slower than hash tables, too

Comparison of orders of growth

                         Alist          Hash table           Binary tree

get (average case)

get (worst case)

put (average case)

put (worst case)

Purely functional data structures

This is Scheme. It's supposed to be a shining example of how functional programming makes you smarter, stronger, and an all around better person than imperative programming. So why do our data structures all seem to involve mutation?

It turns out that we can make some data structures that are purely functional (and referentially transparent!) that are comparable to their imperative equivalents.

Stacks

This is easy: Scheme lists are functional stacks.

Queues

You can't just use a list, of course. How about if you used two lists?

Discussing the runtime of this queue will require a new concept: the amortized cost of an operation. If your expensive operations can be guaranteed to not happen very often, they're not very expensive at all, so try guaranteeing that every expensive operation is "paid for" by a bunch of inexpensive ones that happen previously.

Trees

You can get away with duplicating parts of the tree, especially if the number of duplicated parts is only logarithmic in the size of the tree.

Improving the worst case: red-black trees

Well, that was fun, but now we're going to be seduced by mutation again so we can easily deal with unbalanced binary trees being inefficient.

You can make a binary tree stay balanced and avoid worst-case scenarios by enforcing some constraints. The result is known as a red-black tree.

1. A node is either red or black.
2. The root is black.
3. All leaves (which are null) are black.
4. Both children of every red node are black.
5. All the paths from a given node to any leaf contain the same number of red nodes.

To insert a node, you color it red and add it to the binary tree. Then you see if any constraints are violated. There are local ways to fix every constraint.

Ways to fix a red-black tree

1. If you're adding a node at the root of a tree, paint it black.

1. If the new node's parent is black, you don't have to fix anything. You're replacing a black leaf with a red node that has two black leaves as children.

1. If the node's parent is red and so is its uncle, you can repaint both the parent and the uncle black and paint the grandparent red. Now you've moved the problem up the tree, so deal with it there.

1. If the node's parent is red, its uncle is black, and it is a left child, you can do a right rotation around its parent and switch the colors of the parent and grandparent. (This is the messiest case, and it will need to be illustrated on the board.)

1. If the node's parent is red, its uncle is black, and it is a right child, do a left rotation around the new node and it will turn into a left child. Then you can handle it with case 4.

What are the runtimes of this structure for:

• get (average case)
• get (worst case)
• put (average case, assuming it's a new table entry)
• put (worst case, assuming it's a new table entry)

Guess what: even red-black trees can be made purely functional!