/* 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. =============================================================*/