4.12.1 From Tree to Vine [ToC] [Index]     [Skip Fwd]     [Prev] [Up] [Next]

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:

[Click here for plain-text rendering]

The method for transforming a tree into a vine of this type is similar to that used for destroying a tree by rotation (see Destroying a BST 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:

This is all it takes:

90. <BST to vine function 90> =
/* Converts tree into a vine. */
static void 
tree_to_vine (struct bst_table *tree)
{ struct bst_node *q, *p; q = (struct bst_node *) &tree->bst_root; p = tree->bst_root; while (p != NULL) if (p->bst_link[1] == NULL)
      { q = p; p = p->bst_link[0]; } else
      { struct bst_node *r = p->bst_link[1]; p->bst_link[1] = r->bst_link[0]; r->bst_link[0] = p; p = r; q->bst_link[0] = r; } }

This code is included in 88, 513, and 681.

See also:  [Stout 1986], tree_to_vine procedure.