/*
 * Tree Package Version 1.0, April 25, 1989.
 * Implementation by Eric Giguere.
 *
 * avl.c
 *
 * An AVL (height-balanced) tree module.
 *
 * This code is in the public domain -- use and abuse
 * as you please, but check out the warning below first.
 *
 * This module defines functions for inserting, searching,
 * deleting and freeing nodes in an AVL tree.
 *
 * An AVL tree is a height-balanced tree where the difference
 * between the height of the left and right subtrees of any
 * node in the tree is either -1, 0 or 1.  An AVL tree places
 * an upper bound on the time to perform common operations on
 * a binary tree.  Searches and insertions are O(log N).
 * Deletions are more complicated in this implementation and
 * should be kept to a minimum.  See the external documentation
 * for details.
 *
 * The code in this module is based in part on the algorithms
 * discussed by Knuth in Vol. 3 of "the Art of Computer Programming"
 * and on the discussion of AVL trees in Reingold & Hansen's
 * "Data Structures in Pascal".  Modify this code at your own
 * risk!!! The deletion routine is especially brutal!
 *
 * External functions defined in this module:
 *
 *   avl_insert, avl_find, avl_delete, avl_burn, is_avl
 *
 */

#define _NO_AVL_PROTOTYPES_

#include <stdio.h>
#include "avl.h"

static void      rot_cleanup(), rebalance();
static avl_node *srot_left(), *srot_right();
static avl_node *drot_left(), *drot_right();
static void      srot_balance(), drot_balance();
static int       is_avlnode();

/*
 * avl_find -- Given a dummy node, find the corresponding
 *             node in the tree and return a pointer to it.
 *             Returns NULL if no such node exists in the tree.
 *             Must be passed a comparison function which
 *             returns zero if two keys are equal, a negative
 *             value if the first is smaller than the second,
 *             and a positive value otherwise.
 */

avl_node *avl_find( key_node, root, cmp )
  avl_node  *key_node, **root;
  int      (*cmp)();
  {
    avl_node *node;
    int       rel;

    /* A bit of error-checking... */

    if( key_node == NULL || root == NULL || *root == NULL || cmp == NULL )
        return( NULL );

    node = *root;

    while( node != NULL )
      {
        /* Do comparison */

        rel = (*cmp)( key_node, node );

        if( rel == 0 )
            return( node );

        if( rel < 0 )
            node = node->left;
        else
            node = node->right;
      }

    return( NULL );
  }

/*
 * avl_insert -- Inserts the given node into the given AVL tree,
 *               using the same comparison function as avl_find.
 *               Returns TRUE if insertion was successful, FALSE
 *               otherwise (a node with the same key must not
 *               already exist in the tree).
 *
 *     NOTE: The root of the tree may change on insertion so
 *           a double indirection is required to change the
 *           root pointer if necessary.
 */

int avl_insert( ins_node, root, cmp )
  avl_node  *ins_node, **root;
  int      (*cmp)();
  {
    avl_node *node, *parent, *rebal;
    int       rel;

    /* Error-checking... */

    if( ins_node == NULL || root == NULL || cmp == NULL )
        return( FALSE );

    /* Initialize the internals of the node.  None of these
       fields should be changed outside of this module. */

    ins_node->parent = NULL;
    ins_node->left   = NULL;
    ins_node->right  = NULL;
    ins_node->bal    = 0;

    /* First element in tree? */

    if( *root == NULL )
      {
        *root = ins_node;
        return( TRUE );
      }

    /* Tree is non-empty, find spot to insert.  This may
       require the tree to be rebalanced at one node in the
       search path so keep track of which node to pivot on. */

    node  = *root;
    rebal = NULL;

    for(;;)
      {
        rel = (*cmp)( ins_node, node );

        if( rel == 0 )
            return( FALSE ); /* Error -- key already in tree */

        if( rel < 0 )
          {
            if( node->left == NULL ) /* Insert new leaf */
              {
                node->left       = ins_node;
                ins_node->parent = node;
                break;
              }

            node  = node->left;
          }
        else
          {
            if( node->right == NULL ) /* Insert new leaf */
              {
                node->right      = ins_node;
                ins_node->parent = node;
                break;
              }

            node  = node->right;
          }

        /* Update pivot */

        if( node->bal != 0 )
            rebal = node->parent;
      }

    /* Now adjust the balance factors in the search path */

    parent = node;
    node   = ins_node;

    while( parent != NULL && parent != rebal )
      {
        /* Insertion occurred in left subtree */

        if( parent->left == node )
          {
            if( --parent->bal < -1 )
              {
                /* Rotate and exit */

                if( parent->left->bal < 0 )
                    srot_right( parent, root, TRUE );
                else
                    drot_right( parent, root );

                return( TRUE );
              }
          }
        else /* Insertion was in right subtree */
          {
            if( ++parent->bal > 1 )
              {
                /* Rotate and exit */

                if( parent->right->bal > 0 )
                    srot_left( parent, root, TRUE );
                else
                    drot_left( parent, root );

                return( TRUE );
              }
          }

        node   = parent;
        parent = parent->parent;
      }

    return( TRUE );
  }

/*
 * avl_burn -- Free all the nodes of an AVL tree.  This routine
 *             only detaches the nodes -- they must be deallocated
 *             by a user-supplied function.
 */

void avl_burn( node, func )
  avl_node  *node;
  void     (*func)();
  {
    if( node != NULL )
      {
        avl_burn( node->left, func );
        avl_burn( node->right, func );

        node->left   = NULL;
        node->parent = NULL;
        node->right  = NULL;
        node->bal    = 0;

        if( func != NULL )
            (*func)( node );
      }
  }

/*
 * avl_delete -- Delete the given node from the given AVL tree.
 *               This routine does not search for the node,
 *               avl_find can be used for that.  Returns a pointer
 *               to the deleted node, NULL if an error occurs.
 *
 *     NOTE: The root of the tree may change on deletion so
 *           a double indirection is required to change the
 *           root pointer if necessary.
 */

avl_node *avl_delete( node, root )
  avl_node *node, **root;
  {
    avl_node *left, *right, *parent, *succ;
    int       flag, rebal;
    avl_node *new_root, *b, *f, *d;
    int       d_bal, f_bal;

    rebal = FALSE;

    if( node == NULL || root == NULL || *root == NULL )
        return( node );

    left   = node->left;
    right  = node->right;
    parent = node->parent;

    /*
     * Case 1: The node to be deleted has no children.
     */

    if( left == NULL && right == NULL )
      {
        rebalance( node, root );

        if( node->parent == NULL )
            *root = NULL;
        else if( node->parent->left == node )
            node->parent->left = NULL;
        else
            node->parent->right = NULL;

        return( node );
      }

    /*
     * Case 2: The node has only a right child.
     */

    if( left == NULL )
      {
        if( parent == NULL )
          {
            *root = right;
            right->parent = NULL;
            return( node );
          }

        rebalance( node, root );

        if( node->parent->left == node )
            node->parent->left  = right;
        else
            node->parent->right = right;

        right->parent = node->parent;

        return( node );
      }

    /*
     * Case 3: The node has only a left child.
     */

    if( right == NULL )
      {
        if( parent == NULL )
          {
            *root = left;
            left->parent = NULL;
            return( node );
          }

        rebalance( node, root );

        if( node->parent->left == node )
            node->parent->left = left;
        else
            node->parent->right = left;

        left->parent  = node->parent;

        return( node );
      }

    /*
     * Case 4a: The node has two children, but the right child has
     *          no children or at most one right child.
     */

    if( right->left == NULL )
      {
        right->left   = left;
        left->parent  = right;
        right->parent = parent;
        right->bal    = node->bal - 1;

        flag = ( right->right != NULL );

        if( parent != NULL )
          {
            if( parent->left == node )
                parent->left  = right;
            else
                parent->right = right;
          }
        else
          {
            *root = right;
          }

        if( !flag ) /* no right child */
          {
            if( right->bal < -1 )
              {
                rebal = ( left->bal != 0 );

                if( left->bal < 0 )
                    new_root = srot_right( right, root, FALSE );
                else
                    new_root = drot_right( right, root );

                new_root->bal        = 0;
                new_root->left->bal  = 0;
                new_root->right->bal = 0;

                if( rebal )
                    rebalance( new_root, root );
                else
                  {
                    new_root->bal       = -1;
                    new_root->left->bal = -1;
                  }
              }

            return( node );
          }

        /* One right child only */

        b = node->right;
        d = node->left;
        f = node->left->right;

        if( node->bal != -1 )
          {
            if( b->bal == 0 )
                rebalance( b, root );

            return( node );
          }

        d_bal = d->bal;
        f_bal = f->bal;

        if( d_bal == -1 && f_bal == 0 )
          {
            new_root = srot_right( right, root, FALSE );
            d->bal = b->bal = f->bal = 0;
          }
        else if( d_bal == 0 && f_bal == 1 )
          {
            new_root = srot_right( right, root, FALSE );
            d->bal = f->bal = 1;
            b->bal = -1;
          }
        else
          {
            new_root = drot_right( right, root );

            if( f_bal == 0 )
              {
                b->bal = 0;
                d->bal = f->bal = ( d_bal - 1 );
              }
            else
              {
                f->bal = d_bal - 1;

                if( d_bal == 1 && f_bal == -1 )
                  {
                    d->bal = 0;
                    b->bal = 1;
                  }
                else if( d_bal == 1 && f_bal == 1 )
                  {
                    d->bal = -1;
                    b->bal = 0;
                  }
                else
                  {
                    d->bal = -1;
                    b->bal = 1;
                  }
              }
          }

        if( d_bal != 0 )
            rebalance( new_root, root );

        return( node );
      }

    /*
     * Case 4b: The node has two children and the right child has
     *          a left subtree.
     */

    for( succ = right->left; succ->left != NULL; succ = succ->left )
        ;

    rebalance( succ, root );

    succ->bal = node->bal;

    succ->parent->left = succ->right;

    if( succ->right != NULL )
        succ->right->parent = succ->parent;

    succ->left          = node->left;

    if( succ->left != NULL )
        succ->left->parent  = succ;

    succ->right         = node->right;

    if( succ->right != NULL )
        succ->right->parent = succ;

    succ->parent        = node->parent;

    if( succ->parent != NULL )
      {
        if( succ->parent->left == node )
            succ->parent->left = succ;
        else
            succ->parent->right = succ;
      }
    else
      {
        *root = succ;
      }

    return( node );
  }

/*
 * srot_left -- Perform a single left rotation.
 */

static avl_node *srot_left( pivot, root, ins )
  avl_node *pivot, **root;
  int       ins;
  {
    avl_node *child, *parent;

    parent        = pivot->parent;
    child         = pivot->right;
    pivot->right  = child->left;
    child->left   = pivot;
    child->parent = parent;
    pivot->parent = child;

    srot_balance( pivot, child, 1, ins );
    rot_cleanup( pivot, child, root, parent, child );

    return( child );
  }

/*
 * srot_right -- Perform a single right rotation.
 */

static avl_node *srot_right( pivot, root, ins )
  avl_node *pivot, **root;
  int       ins;
  {
    avl_node *child, *parent;

    parent        = pivot->parent;
    child         = pivot->left;
    pivot->left   = child->right;
    child->right  = pivot;
    child->parent = parent;
    pivot->parent = child;

    srot_balance( pivot, child, -1, ins );
    rot_cleanup( pivot, child, root, parent, child );

    return( child );
  }

/*
 * drot_left -- Perform a double left rotation.
 */

static avl_node *drot_left( pivot, root )
  avl_node *pivot, **root;
  {
    avl_node *child, *gchild, *parent;

    parent         = pivot->parent;
    child          = pivot->right;
    gchild         = child->left;
    pivot->right   = gchild->left;
    child->left    = gchild->right;
    gchild->right  = child;
    gchild->left   = pivot;
    gchild->parent = parent;
    pivot->parent  = gchild;
    child->parent  = gchild;

    drot_balance( gchild );
    rot_cleanup( pivot, child, root, parent, gchild );

    return( gchild );
  }

/*
 * drot_right -- Perform a double right rotation.
 */

static avl_node *drot_right( pivot, root )
  avl_node *pivot, **root;
  {
    avl_node *child, *gchild, *parent;

    parent         = pivot->parent;
    child          = pivot->left;
    gchild         = child->right;
    pivot->left    = gchild->right;
    child->right   = gchild->left;
    gchild->left   = child;
    gchild->right  = pivot;
    gchild->parent = parent;
    pivot->parent  = gchild;
    child->parent  = gchild;

    drot_balance( gchild );
    rot_cleanup( pivot, child, root, parent, gchild );

    return( gchild );
  }

/*
 * drot_balance -- Adjust balance factors after a double rotation.
 */

static void drot_balance( new_root )
  avl_node *new_root;
  {
    new_root->left->bal  = 0;
    new_root->right->bal = 0;

    if( new_root->bal < 0 )
        new_root->right->bal = 1;
    else if( new_root->bal > 0 )
        new_root->left->bal = -1;

    new_root->bal = 0;
  }

/*
 * srot_balance -- Adjust balance factors after a single rotation.
 */

static void srot_balance( pivot, child, bal, ins )
  avl_node *pivot, *child;
  int       bal, ins;
  {
    if( pivot->bal < 0 )
        pivot->bal = -1;
    else if( pivot->bal > 0 )
        pivot->bal = 1;

    if( ins == TRUE || pivot->bal == child->bal )
      {
        pivot->bal = 0;
        child->bal = 0;
      }
    else
      {
        child->bal = -pivot->bal;
      }
  }

/*
 * rot_cleanup -- Cleanup some miscellaneous pointers after
 *                performing a single or double rotation.
 */

static void rot_cleanup( pivot, child, root, parent, new_root )
  avl_node  *pivot, *child;
  avl_node **root;
  avl_node  *parent, *new_root;
  {
    if( pivot->left != NULL )
        pivot->left->parent = pivot;

    if( pivot->right != NULL )
        pivot->right->parent = pivot;

    if( child->left != NULL )
        child->left->parent = child;

    if( child->right != NULL )
        child->right->parent = child;

    if( *root == pivot )
        *root = new_root;

    if( parent != NULL )
      {
        if( parent->left == pivot )
            parent->left = new_root;
        else
            parent->right = new_root;
      }
  }

/*
 * rebalance -- Rebalance the tree after a deletion.
 */

static void rebalance( child, root )
  avl_node *child, **root;
  {
    avl_node *curr;
    int       left;

    /* More error-checking... */

    if( child == NULL || root == NULL || *root == NULL )
        return;

    /* Starting at the current node, rebalance the parent
       until we have an AVL tree again */

    for( curr = child->parent; curr != NULL; curr = child->parent )
      {
        left = ( child == curr->left );

        /* Height was 0, deleting an element on the left or
           right still leaves it as an AVL tree so quit */

        if( curr->bal == 0 )
          {
            if( left )
                curr->bal = 1;
            else
                curr->bal = -1;

            return;
          }

        if( ( curr->bal > 0 && left == FALSE ) ||
            ( curr->bal < 0 && left == TRUE ) )
          {
            curr->bal = 0;
            child     = curr;
            continue;
          }

        if( curr->bal > 0 && left == TRUE )
          {
            if( curr->right->bal == 0 )
              {
                srot_left( curr, root, FALSE );
                return;
              }
            else if( curr->right->bal > 0 )
              {
                child = srot_left( curr, root, FALSE );
                continue;
              }
            else
              {
                child = drot_left( curr, root );
                continue;
              }
          }
        else
          {
            if( curr->left->bal == 0 )
              {
                srot_right( curr, root, FALSE );
                return;
              }
            else if( curr->left->bal < 0 )
              {
                child = srot_right( curr, root, FALSE );
                continue;
              }
            else
              {
                child = drot_right( curr, root );
                continue;
              }
          }
      }

    return;
  }

/*
 * is_avl -- Returns TRUE if the given tree is an AVL tree.
 */

int is_avl( node )
  avl_node *node;
  {
    if( is_avlnode( node ) < 0 )
        return( FALSE );

    return( TRUE );
  }

/*
 * is_avlnode -- Ensure that each node is height-balanced.
 */

static int is_avlnode( node )
  avl_node *node;
  {
    int h, rh, lh;

    /* No node --> height = 0 */

    if( node == NULL )
        return( 0 );

    /* Leaf node --> height = 1 */

    if( node->left == NULL && node->right == NULL )
        return( 1 );

    /* Get the heights of left & right subtrees */

    lh = is_avlnode( node->left );
    rh = is_avlnode( node->right );

    h = rh - lh;

    /* If something isn't right, return a negative value */

    if( lh < 0 || rh < 0 || node->bal != h || h < -1 || h > 1 )
        return( -1 );

    /* Return the height of the tallest subtree + 1 */

    return( ( ( rh > lh ) ? rh : lh ) + 1 );
  }