/*
* Copyright (c) 1997 Philip A. Nelson.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by Philip A. Nelson.
* 4. The name of Philip A. Nelson may not be used to endorse or promote
* products derived from this software without specific prior written
* permission.
*
* THIS SOFTWARE IS PROVIDED BY PHILIP NELSON ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL PHILIP NELSON BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/* avl.c: Routines for manipulation an avl tree.
*
* an include file should define the following minimum struct.:
* (Comments must be made into real comments.)
*
* typedef struct id_rec {
* / * The balanced binary tree fields. * /
* char *id; / * The name. * /
* short balance; / * For the balanced tree. * /
* struct id_rec *left, *right; / * Tree pointers. * /
*
* / * Other information fields. * /
* } id_rec;
*/
/* find_id returns a pointer to node in TREE that has the correct
ID. If there is no node in TREE with ID, NULL is returned. */
id_rec *
find_id (id_rec *tree, char *id)
{
int cmp_result;
/* Check for an empty tree. */
if (tree == NULL)
return NULL;
/* Recursively search the tree. */
cmp_result = strcmp (id, tree->id);
if (cmp_result == 0)
return tree; /* This is the item. */
else if (cmp_result < 0)
return find_id (tree->left, id);
else
return find_id (tree->right, id);
}
/* insert_id inserts a NEW_ID rec into the tree whose ROOT is
provided. insert_id returns TRUE if the tree height from
ROOT down is increased otherwise it returns FALSE. This is a
recursive balanced binary tree insertion algorithm. */
int insert_id (id_rec **root, id_rec *new_id)
{
id_rec *A, *B;
/* If root is NULL, this where it is to be inserted. */
if (*root == NULL)
{
*root = new_id;
new_id->left = NULL;
new_id->right = NULL;
new_id->balance = 0;
return (TRUE);
}
/* We need to search for a leaf. */
if (strcmp (new_id->id, (*root)->id) < 0)
{
/* Insert it on the left. */
if (insert_id (&((*root)->left), new_id))
{
/* The height increased. */
(*root)->balance--;
switch ((*root)->balance)
{
case 0: /* no height increase. */
return (FALSE);
case -1: /* height increase. */
return (TRUE);
case -2: /* we need to do a rebalancing act. */
A = *root;
B = (*root)->left;
if (B->balance <= 0)
{
/* Single Rotate. */
A->left = B->right;
B->right = A;
*root = B;
A->balance = 0;
B->balance = 0;
}
else
{
/* Double Rotate. */
*root = B->right;
B->right = (*root)->left;
A->left = (*root)->right;
(*root)->left = B;
(*root)->right = A;
switch ((*root)->balance)
{
case -1:
A->balance = 1;
B->balance = 0;
break;
case 0:
A->balance = 0;
B->balance = 0;
break;
case 1:
A->balance = 0;
B->balance = -1;
break;
}
(*root)->balance = 0;
}
}
}
}
else
{
/* Insert it on the right. */
if (insert_id (&((*root)->right), new_id))
{
/* The height increased. */
(*root)->balance++;
switch ((*root)->balance)
{
case 0: /* no height increase. */
return (FALSE);
case 1: /* height increase. */
return (TRUE);
case 2: /* we need to do a rebalancing act. */
A = *root;
B = (*root)->right;
if (B->balance >= 0)
{
/* Single Rotate. */
A->right = B->left;
B->left = A;
*root = B;
A->balance = 0;
B->balance = 0;
}
else
{
/* Double Rotate. */
*root = B->left;
B->left = (*root)->right;
A->right = (*root)->left;
(*root)->left = A;
(*root)->right = B;
switch ((*root)->balance)
{
case -1:
A->balance = 0;
B->balance = 1;
break;
case 0:
A->balance = 0;
B->balance = 0;
break;
case 1:
A->balance = -1;
B->balance = 0;
break;
}
(*root)->balance = 0;
}
}
}
}
/* If we fall through to here, the tree did not grow in height. */
return (FALSE);
}
