Balanced Binary Search Trees:Rebalancing a Tree to Perfect Balance

Rebalancing a Tree to Perfect Balance

A basic operation is the rebalancing operation, which takes a binary tree as input and produces a balanced tree. This operation is important in itself, but it is also used as a subroutine in balancing schemes (see Section 10.6).

It is quite obvious that one can construct a perfectly balanced tree from an ordered tree, or a sorted list, in linear time. The most straightforward way is to put the elements in sorted order into an array, take the median as the root of the tree, and construct the left and right subtrees recursively from the upper and lower halves of the array. However, this is unnecessarily cumbersome in terms of time, space, and elegance.

A number of restructuring algorithms, from the type mentioned above to more elegant and efficient ones based on rotations, can be found in the literature [26, 27, 33, 54, 72]. Of these, the one by Stout and Warren [72] seems to be most efficient. It uses the following principle:

1. Skew. Make right rotations at the root until no left child remains. Continue down the right path making right rotations until the entire tree becomes one long rightmost path (a “vine”).

2. Split. Traverse down the vine a number of times, each time reducing the length of the vine by left rotations.

If we start with a vine of length 2p − 1, for some integer p, and make one rotation per visited node, the resulting vine will be of length 2p−1 − 1 after the first pass, 2p−2 − 1 after the second pass, etc., until the vine is reduced to a single node; the resulting tree is a perfectly balanced tree. If the size of the tree is 2p − 1 , this will work without any problem.

If, however, the size is not a power of two, we have to make some special arrangements during the first pass of left rotations. Stout and Warren solved the problem of how to make evenly distributed rotations along the vine in a rather complicated way, but there is a simpler one. It has never before been published in itself, but has been included in demo software and in published code [6, 11].

The central operation is a split operation that takes as parameters two numbers p1 and p2 and compresses a right-skewed path of p1 nodes into a path of p2 nodes (2p2 ≥ p1). The simple idea is to use a counter stepping from p1 − p2 to p2(p1 − p2) with increment p1 − p2.

Every time this counter reaches or exceeds a multiple of p2, a rotation is performed. In effect, the operation will make p1 − p2 evenly distributed left rotations.

With this split operation available, we can do as follows to rebalance a tree of size n (n internal nodes): First, skew the tree. Next, find the largest integer b such that b is an even power of 2 and b − 1 ≤ n. Then, if b − 1 < n, call Split with parameters n and b − 1. Now, the vine will have proper length and we can traverse it repeatedly, making a left rotation at each visited node, until only one node remains.

In contrast to the Stout-Warren algorithm, this algorithm is straightforward to implement.

most:

We illustrate it in Figure 10.4.

We describe the five trees, starting with the top-

1. A tree with 12 internal nodes to be balanced.

2. After Skew.

3. With n = 12 and b = 8, we call split with parameters 12 and 7, which implies that five evenly distributed rotations will be made. As the result, the vine will be of length 7, which fulfills the property of being 2p − 1.

4. The next split can be done by traversing the vine, making one left rotation at each node. As a result, we get a vine of length 3 (nodes 3, 6, and 10).

5. After the final split, the tree is perfectly balanced.