www.delorie.com/gnu/docs/avl/libavl_71.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The first stage of balancing converts a binary tree into a linear structure resembling a linked list, called a vine (see vine). The vines we will create have the greatest value in the binary tree at the root and decrease descending to the left. Any binary search tree that contains a particular set of values, no matter its shape, corresponds to the same vine of this type. For instance, all binary search trees of the integers 0...4 will be transformed into the following vine:
The method for transforming a tree into a vine of this type is similar to that used for destroying a tree by rotation (see section 5.11.1 Destruction by Rotation). We step pointer p through the tree, starting at the root of the tree, maintaining pointer q as p's parent. (Because we're building a vine, p is always the left child of q.) At each step, we do one of two things:
where a, b, and c are arbitrary subtrees or empty trees. Node r then becomes the new p. If c is an empty tree, then, in the next step, we will continue down the tree. Otherwise, the right subtree of p is smaller (contains fewer nodes) than previously, so we're on the right track.
This is all it takes:
See also: [ Stout 1986], tree_to_vine procedure.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster donations bookstore | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |