www.delorie.com/gnu/docs/avl/libavl_150.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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.
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:
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); |
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) |
After this, all the remaining compressions use only rotations without thread adjustment, and we're done:
while (vine > 1) |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |