4.12.2 From Vine to Balanced Tree

Converting the vine, once we have it, into a balanced tree is the interesting and clever part of the balancing operation. However, at first it may be somewhat less than obvious how this is actually done. We will tackle the subject by presenting an example, then the generalized form.

Suppose we have a vine, as above, with 2**n - 1 nodes for positive integer n. For the sake of example, take n = 4, corresponding to a tree with 15 nodes. We convert this vine into a balanced tree by performing three successive compression (see compression) operations.

To perform the first compression, move down the vine, starting at the root. Conceptually assign each node a “color”, alternating between red and black and starting with red at the root.¹ Then, take each red node, except the bottommost, and remove it from the vine, making it the child of its black former child node.

After this transformation, we have something that looks a little more like a tree. Instead of a 15-node vine, we have a 7-node black vine with a 7-node red vine as its right children and a single red node as its left child. Graphically, this first compression step on a 15-node vine looks like this:

To perform the second compression, recolor all the red nodes to white, then change the color of alternate black nodes to red, starting at the root. As before, extract each red node, except the bottommost, and reattach it as the child of its black former child node. Attach each black node's right subtree as the left subtree of the corresponding red node. Thus, we have the following:

The third compression is the same as the first two. Nodes 12 and 4 are recolored red, then node 12 is removed and reattached as the right child of its black former child node 8, receiving node 8's right subtree as its left subtree:

The result is a fully balanced tree.

• Balancing General Trees
• Balancing Implementation
• Implementing Compression