Functional Sets, Part 2: Rotation

Elm 0.18 · Updated February 15, 2018 · 5 Minute Read · ∞ Permalink

Last time we started making a set using a binary search tree. Let’s keep moving!

Quick Recap

We’re modeling binary search trees like this in Elm:

type Set comparable
    = Tree comparable (Set comparable) (Set comparable)
    | Empty

We can create empty sets using empty, sets from a single item using singleton, and bigger sets by using insert or fromList.

Off Balance

Unfortunately, the insert function we wrote last time has a problem. It will keep all our values organized, but if you insert values in a certain order you get a very inefficient structure back.

The simplest place this happens is when you try to create a set from a list that’s already in order. When we run fromList [1, 2, 3, 4, 5] we’d want to get this:

But instead, we get:

Think about how we’d retrieve 5 from these sets.

In the nice balanced tree above:

1. We’d see that the head is 2.
2. Ok, so look in the right subtree, where the head is 4.
3. 5 is greater than 4, so right subtree again, and we’ve found it.

Three steps, not terrible. But what about the unbalanced tree?

1. The head is 1, so look in the right.
2. The next head is 2, so look in the right.
3. The next head is 3, so look in the right.
4. You get the point. Right again.
5. Finally, we find our 5.

So three steps versus five. That doesn’t make a huge difference for small sets, but imagine if you had 1,000 items in your set… you don’t want to look through all of them!

It turns out that for balanced trees, looking up an item in a set of size n takes log2(n) operations. For a set of 1,000 items, that means about 10 operations instead of 1,000. This is a huge difference!

So, to get the benefits, let’s make sure that our data structure stays balanced. We’ll do this by rotating our tree!

Tree Rotation

Tree rotation means rearranging the values in a tree in a way that preserves order, but changes the relative height of each side of the tree. Wikipedia has an amazing GIF to explain it:

In words: to rotate left, we have to have a tree with a non-empty subtree as it’s right subtree. For the sake of clarity, we’re going to call the original head head and the subtree’s head subHead.

Remember how all the values to the left of a subtree are less than the head, and the values to the right are greater? Well, that means that the left subtree of the right subtree (the yellow B in the graphic above) contains values between the two heads! We’ll use that property to our advantage here. Let’s refer to the left subtree of the original tree as lessThans, and the left and right subtrees of the subtree as betweens and greaterThans.

Now that we’ve got a plan, let’s rotate left (right is just reversing this.) We’ll create a new Tree, with subHead as the head. The left subtree will be another new tree, with head as the head, lessThans as the left subtree, and betweens as the right subtree. Last, we attach greaterThans as the right subtree.

Whew! That’s a ton of words to describe something that’s fairly succinct in code:

rotateLeft : Set comparable -> Set comparable
rotateLeft set =
    case set of
        Tree head lessThans (Tree subHead betweens greaterThans) ->
            tree subHead (tree head lessThans betweens) greaterThans

        _ ->
            set


rotateRight : Set comparable -> Set comparable
rotateRight set =
    case set of
        Tree head (Tree subHead lessThans betweens) greaterThans ->
            tree subHead lessThans (tree head betweens greaterThans)

        _ ->
            set

We always put lessThans, betweens and greaterThans in order in the source. If these ever get out of order, we’re going to be breaking our guarantees about structure!

Next time, we’ll fgure out how to apply these rotations automatically. But for now…

Make Your Own Trees!

It can be really difficult to get all this in your head. When I was learning this, it really helped to visualize it. So, here’s a program that you can use to do the same!

Enter any string value in the box below, and you’ll see the output of our sets so far. Purple circles indicate empty sets, and you can rotate the tree left and right.

Things to try:

• Enter 1, 2, and 3 as the values. Rotate the tree and see how that works.
• Enter 2, 3, 1 in order. Hey, the insert code does what we said it would!
• Enter a through z. Trace the operations you’d take to get to any given letter.