www.delorie.com/gnu/docs/avl/libavl_150.html

search

	Buy GNU books!

GNU libavl 2.0.1

8.11.2 From Vine to Balanced Tree

Transforming a vine into a balanced threaded BST is similar to the same operation on an unthreaded BST. We can use the same algorithm, adjusting it for presence of the threads. The following outline is similar to <@xref{\NODE\, , BST balance function.>,87}. In fact, we entirely reuse <@xref{\NODE\, , Calculate leaves.>,91}, just changing bst to tbst. We omit the final check on the tree's height, because none of the TBST functions are height-limited.

static void vine_to_tree (struct tbst_table *tree) { unsigned long vine; /* Number of nodes in main vine. */ unsigned long leaves; /* Nodes in incomplete bottom level, if any. */ int height; /* Height of produced balanced tree. */ <@xref{\NODE\, , Calculate leaves.>; bst => tbst,91} <@xref{\NODE\, , Reduce TBST vine general case to special case.>,287} <@xref{\NODE\, , Make special case TBST vine into balanced tree and count height.>,288} }

This code is included in @refalso{282

Not many changes are needed to adapt the algorithm to handle threads. Consider the basic right rotation transformation used during a compression:

The rotation does not disturb a or c, so the only node that can cause trouble is b. If b is a real child node, then there's no need to do anything differently. But if b is a thread, then we have to swap around the direction of the thread, like this:

After a rotation that involves a thread, the next rotation on B will not involve a thread. So after we perform a rotation that adjusts a thread in one place, the next one in the same place will not require a thread adjustment.

Every node in the vine we start with has a thread as its right link. This means that during the first pass along the main vine we must perform thread adjustments at every node, but subsequent passes along the vine must not perform any adjustments.

This simple idea is complicated by the initial partial compression pass in trees that do not have exactly one fewer than a power of two nodes. After a partial compression pass, the nodes at the top of the main vine no longer have right threads, but the ones farther down still do.

We deal with this complication by defining the compress() function so it can handle a mixture of rotations with and without right threads. The rotations that need thread adjustments will always be below the ones that do not, so this function simply takes a pair of parameters, the first specifying how many rotations without thread adjustment to perform, the next how many with thread adjustment. Compare this code to that for unthreaded BSTs:

/* Performs a nonthreaded compression operation nonthread times, then a threaded compression operation thread times, starting at root. */ static void compress (struct tbst_node *root, unsigned long nonthread, unsigned long thread) { assert (root != NULL); while (nonthread--) { struct tbst_node *red = root->tbst_link[0]; struct tbst_node *black = red->tbst_link[0]; root->tbst_link[0] = black; red->tbst_link[0] = black->tbst_link[1]; black->tbst_link[1] = red; root = black; } while (thread--) { struct tbst_node *red = root->tbst_link[0]; struct tbst_node *black = red->tbst_link[0]; root->tbst_link[0] = black; red->tbst_link[0] = black; red->tbst_tag[0] = TBST_THREAD; black->tbst_tag[1] = TBST_CHILD; root = black; } }

This code is included in @refalso{282

When we reduce the general case to the 2**n - 1 special case, all of the rotations adjust threads:

compress ((struct tbst_node *) &tree->tbst_root, 0, leaves);

This code is included in @refalso{285

We deal with the first compression specially, in order to clean up any remaining unadjusted threads:

vine = tree->tbst_count - leaves; height = 1 + (leaves > 0); if (vine > 1) { unsigned long nonleaves = vine / 2; leaves /= 2; if (leaves > nonleaves) { leaves = nonleaves; nonleaves = 0; } else nonleaves -= leaves; compress ((struct tbst_node *) &tree->tbst_root, leaves, nonleaves); vine /= 2; height++; }

See also @refalso{289 This code is included in @refalso{285

After this, all the remaining compressions use only rotations without thread adjustment, and we're done:

while (vine > 1) { compress ((struct tbst_node *) &tree->tbst_root, vine / 2, 0); vine /= 2; height++; }