Studio 11: Practice with Balanced Trees

Today, we'll practice some of the tricks we recently saw for maintaining balanced trees, including AVL trees and 2-3-4 trees. We'll also consider how to delete a node from a 2-3-4 tree.

Part A: AVL Tree Practice

For this section and the next, you should try to answer each question by hand, using what you know about AVL trees. Once you have an answer, use this AVL tree visualizer to check yourself. Make sure you can explain to your TA how you got the tree at each step.

To begin, construct an AVL tree from the following list of keys:

2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24

Choose an order to insert these keys* so that the resulting tree looks exactly like the following:

AVL tree

Question A1: what order did you insert the keys? Is this the only order that could produce this tree?

Next, let's practice a few insertions with rebalancing operations. For each operation, compute the resulting tree and list the rotations (direction and subtree root) that must be performed to rebalance.

Question A2: Insert 17 into the tree resulting from A1.

Question A3: Insert 19 into the tree resulting from A2.

Question A4: Insert 15 into the tree resulting from A3.

Finally, let's practice a few deletions. For each, give the same information as for the insertions.

Question A5: Remove 2 from the tree resulting from A4.

Question A6: Remove both 22 and 24 from the tree resulting from A5.

Part B: 2-3-4 Tree Practice

Next, we'll practice insertions into a 2-3-4 tree, paying attention to the splitting rule described in class. For this section, use this B-tree visualizer and set its "max degree" selector to 4, which corresponds to 2-3-4 trees. Again, try to answer the questions yourself first, and check your answers with the visualizer only afterwards.

For each of the following questions, give the final tree and list all the splits that occur during the insertion sequence. First, build a 2-3-4 tree by inserting the following keys in the order given:

3, 9, 15, 6, 12, 18

Question B1: what is the tree you get from this sequence of insertions?

Question B2: Add keys 1, 2, and 4 to the tree resulting from B1.

Question B3: Add keys 19 and 20 to the tree resulting from B2.

There is more than one 2-3-4 tree visualizer available online. Once you've used the visualizer above to check your work, repeat the constructions for questions B1-B3 using this alternate visualizer.

Question B4: how does the result differ from the first visualizer? What decisions is the second visualizer making differently from the first?

The insertion procedure for 2-3-4 trees, unlike that for AVL trees, involves ambiguity. An algorithm can sometimes make more than one choice, each of which results in a different, equally valid tree.

Part C: Deleting a Key from a 2-3-4 Tree

We now consider a problem we didn't address in class: how to remove a key from a 2-3-4 tree. We'll assume that we remove a key at a leaf of the tree, since (as for BSTs) removing a non-leaf key can be achieved by swapping the key with its successor, and then recursively removing the successor.

Question C1: in a 2-3-4 tree, the successor of a non-leaf node must appear in a leaf node. Why is this true, and why isn't it true for binary search trees?

To get started on this section, rebuild the tree you had at the end of Question B3 (including all insertions from Part B), using the first visualizer (the one that follows our lecture notes).

Deleting a key from a leaf node is easy provided that the node has at least two keys. As an illustration, delete 4 from the tree you just built and see what happens. The challenge comes when we want to delete the sole key in a leaf of size 1, such as key 15 in your example tree.

Question C2: why can't we simply remove the leaf containing 15 from the tree?

2-3-4 tree deletion seeks to add another key to a node of size 1 so that we can remove the key we want without leaving an empty node. We will consider a series of increasingly invasive options to move a key from elsewhere in the tree into the target node.

The first option, if we can do it, is to move keys around in a way that does not actually change the tree structure (its nodes and edges) at all.

Question C3: propose a way to move a key from a nearby node into the leaf containing key 15, so that 15 can be deleted.

Hint: try something analogous to rotation involving an adjacent leaf.

When you think you have a solution, try removing 15 in the visualizer and see if you get the same result.

Question C4: under what circumstance could this procedure result in two alternatives for how to move a key into the target leaf?

Next, we'll consider how to remove key 18 from the tree left over after we've removed 15.

Question C5: why can't we use the option from C3 in this case?

Question C6: how can we move a key from the parent of key 18's leaf down into that leaf? In particular, what do we have to do to fix the tree structure after moving a key down?

Once again, try deleting 18 in the visualizer and see if your idea matches its behavior.

Finally, we'll consider how to remove key 3 from the tree left over after we've removed 18. Again, removing 3 requires that we add a key to the node containing it.

Question C7: why can't we use the options from C3 or C6 this case?

As in C6, we will move down a key from the parent of the target leaf. However, doing so leaves a hole (i.e. an empty internal node) in the tree, because the parent itself has only one key.

Question C8: delete key 3 from the tree in the visualizer, and watch what happens. How did deletion fill the hole left in the parent of the target leaf?

Use the "Skip back" button if you need to repeat the remove operation multiple times to figure out what is going on. Also, you can slide the "animation speed" slider to the left to slow down the process, so that you can better follow each step.

We can actually use any of the options considered above to fill a hole in a non-leaf node. For example, skip back to the state of the tree before deleting 3, then add keys 13 and 14. Now try to delete 3 again.

Question C9: Which option did the algorithm use to fill the hole left in 3's parent this time?

In general, 2-3-4 tree deletion considers each of the options in C1 (which only works at leaves), C3, and C6 to remove a node with minimal change to the tree structure. If all of these options fail, it creates a hole in the node's parent, then recursively tries to find a way to fill it using options analogous to C3 and C6 (rotation and "unsplitting", respectively). If neither option is possible, the hole is pushed up to the next level of the tree, and so forth until it either reaches the root or disappears. If, as in C8, the hole reaches the root, the tree shrinks by one level.