www.delorie.com/gnu/docs/avl/libavl_71.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

5.12.1 From Tree to Vine

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:

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:

This is all it takes:

 
/* Converts tree into a vine. */
static void 
tree_to_vine (struct bst_table *tree)
{ struct bst_node *q, *p; q = (struct bst_node *) &tree-&#62;bst_root; p = tree-&#62;bst_root; while (p != NULL) if (p-&#62;bst_link[1] == NULL)
{ q = p; p = p-&#62;bst_link[0]; } else
{ struct bst_node *r = p-&#62;bst_link[1]; p-&#62;bst_link[1] = r-&#62;bst_link[0]; r-&#62;bst_link[0] = p; p = r; q-&#62;bst_link[0] = r; } }
This code is included in @refalso{87

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