/* Copyright (C) 1996 Bjoern Beutel. */

/* Description. =============================================================*/

/* This module implements AVL trees. */

/* Types. ===================================================================*/

typedef struct avl_node /* An AVL tree node. */
{ 
  struct avl_node *left, *right; /* Left and right son in AVL tree. */
  int_t balance; /* < 0 if left tree is deeper; > 0 if right tree is deeper. */
} avl_node_t;

typedef struct avln_node /* An AVL tree node sorted by its name. */
{ 
  struct avln_node *left, *right; /* Left and right son in AVL tree. */
  int_t balance; /* < 0 if left tree is deeper; > 0 if right tree is deeper. */
  /* The preceeding items must be identical to the ones in "avl_node_t" and
   * occur in the same order. */

  string_t name; /* Name of this node. It is considered case-insensitive. */
} avln_node_t;

/* Functions. ===============================================================*/

extern bool_t insert_avl_node( avl_node_t *node, avl_node_t **tree, 
                               int_t (*compare)( avl_node_t*, avl_node_t* ) );
/* Put NODE into TREE. Return TRUE iff TREE has grown. */

extern bool_t remove_avl_node( avl_node_t *node, avl_node_t **tree,
                               int_t (*compare)( avl_node_t*, avl_node_t* ) );
/* Remove NODE from TREE. Return TRUE iff TREE has shrunk. */

extern void insert_avln_node( avln_node_t *node, avln_node_t **tree );
/* Put NODE into TREE. */

extern void remove_avln_node( avln_node_t *node, avln_node_t **tree );
/* Remove NODE from TREE. */

extern avln_node_t *find_avln_node( string_t name, avln_node_t *tree );
/* Find and return the name node with NAME in TREE.
 * If no such node exists, return NULL. */

/* End of file. =============================================================*/