eg_bbtree.c

Go to the documentation of this file.

/* EGlib "Efficient General Library" provides some basic structures and
 * algorithms commons in many optimization algorithms.
 *
 * Copyright (C) 2005 Daniel Espinoza and Marcos Goycoolea.
 * 
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
 * */
#include "eg_bbtree.h"
/** @file
 * @ingroup EGbbtree */
/** @{ */
/* ========================================================================= */

/* ========================================================================= */
/** @brief Defeault constructor.
 * @param mem EGmemPool_t* pointer to the memory pool from where we will
 * alocate all memory for internal structures.
 * @param compare EGcompare_f pointer to a comparison function, used to mantain
 * the tree structure.
 * @return EGbbtree_t pointer to an initialized bbtree.
 * @par Description:
 * Given a memory pool, and a comparison function, we create an empty (and
 * initialized) bbtree that works on elements comparable by the given function.
 * */
EGbbtree_t *EGnewBbtree (EGmemPool_t * mem,
                         EGcompare_f compare)
{
  EGbbtree_t *tree = EGmemPoolSMalloc (mem, EGbbtree_t, 1U);
  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  memset (tree, 0, sizeof (EGbbtree_t));
  tree->compare = compare;
  tree->mem = mem;
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return tree;
}

/* ========================================================================= */
/** @brief Defeault destructor.
 * @param tree EGbbtree_t pointer to the tree to be freed.
 * @par Description:
 * Given an initialized bbtree, this function free al internal data to the
 * local memory pool, but won't free the satelite data.
 * */
void EGfreeBbtree (void *tree)
{
  /* local variables */
  EGbbtreeNode_t *c_node;
  unsigned int stack_size = 4 * (1.5 + log2l ((long
                                               double) ((EGbbtree_t *) tree)->
                                              size + 1)),
    stack_pos = 0;
  EGbbtreeNode_t **stack = EGmemPoolSMalloc (((EGbbtree_t *) tree)->mem,
                                             EGbbtreeNode_t *, stack_size);

  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  /* init the stack */
  stack[stack_pos] = ((EGbbtree_t *) tree)->root;
  if (((EGbbtree_t *) tree)->size)
    while (~stack_pos)
    {
      c_node = stack[stack_pos];
      stack_pos--;
      if (c_node->left)
        stack[++stack_pos] = c_node->left;
      if (c_node->right)
        stack[++stack_pos] = c_node->right;
      EGmemPoolSFree (c_node, EGbbtreeNode_t, 1, ((EGbbtree_t *) tree)->mem);
    }
  ((EGbbtree_t *) tree)->size = 0;

  /* ending */
  EGmemPoolSFree (stack, EGbbtreeNode_t *, stack_size,
                  ((EGbbtree_t *) tree)->mem);
  EGmemPoolSFree (tree, EGbbtree_t, 1, ((EGbbtree_t *) tree)->mem);
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return;
}

/* ========================================================================= */
/** @brief Given an initialized bbtree, left it at it initial state (just after
 * EGnewBbtree).
 * @param tree EGbbtree_t* pointer to the tree to be reseted to its initial
 * state.
 * @param dataFree free function for the satelite data.
 * @return zero on success, non-zero otherwise.
 * @par Description:
 * Set the structure to its initiial state, free all internal data to the
 * memory pool, and apply the given free function to the satelite data.
 * */
int EGbbtreeClear (EGbbtree_t * tree,
                   EGfree_f dataFree)
{
  /* local variables */
  EGbbtreeNode_t *c_node;
  unsigned int stack_size = 4 * (1.5 + log2l ((long double) (tree->size + 1))),
    stack_pos = 0;
  EGbbtreeNode_t **stack = EGmemPoolSMalloc (tree->mem,
                                             EGbbtreeNode_t *, stack_size);

  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  /* init the stack */
  stack[stack_pos] = tree->root;
  if (tree->size)
    while (~stack_pos)
    {
      c_node = stack[stack_pos];
      stack_pos--;
      if (c_node->left)
        stack[++stack_pos] = c_node->left;
      if (c_node->right)
        stack[++stack_pos] = c_node->right;
      if (dataFree)
        dataFree (c_node->this);
      EGmemPoolSFree (c_node, EGbbtreeNode_t, 1, tree->mem);
    }
  tree->size = 0;
  tree->root = 0;

  /* ending */
  EGmemPoolSFree (stack, EGbbtreeNode_t *, stack_size, tree->mem);
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return 0;
}

/* ========================================================================= */
/** @brief Given an initialized bbtree, left it at it initial state (just after
 * EGnewBbtree).
 * @param tree EGbbtree_t* pointer to the tree to be reseted to its initial
 * state.
 * @param dataFree free function for the satelite data.
 * @param datamem pointer to the memory pool used to allocate the satelite
 * data.
 * @return zero on success, non-zero otherwise.
 * @par Description:
 * Set the structure to its initiial state, free all internal data to the
 * memory pool, and apply the given free function to the satelite data.
 * */
int EGbbtreeClearMP (EGbbtree_t * tree,
                     EGfreeMP_f dataFree,
                     EGmemPool_t * datamem)
{
  /* local variables */
  EGbbtreeNode_t *c_node;
  unsigned int stack_size = 4 * (1.5 + log2l ((long double) (tree->size + 1))),
    stack_pos = 0;
  EGbbtreeNode_t **stack = EGmemPoolSMalloc (tree->mem,
                                             EGbbtreeNode_t *, stack_size);

  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  /* init the stack */
  stack[stack_pos] = tree->root;
  if (tree->size)
    while (~stack_pos)
    {
      c_node = stack[stack_pos];
      stack_pos--;
      if (c_node->left)
        stack[++stack_pos] = c_node->left;
      if (c_node->right)
        stack[++stack_pos] = c_node->right;
      if (dataFree)
        dataFree (c_node->this, datamem);
      EGmemPoolSFree (c_node, EGbbtreeNode_t, 1, tree->mem);
    }
  tree->size = 0;
  tree->root = 0;

  /* ending */
  EGmemPoolSFree (stack, EGbbtreeNode_t *, stack_size, tree->mem);
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return 0;
}

/* ========================================================================= */
/** @brief Find an element in the tree.
 * @param tree EGbbtree_t* pointer to the tree where we will perform the
 * search.
 * @param elem void* pointer to the structure that we are looking for.
 * @return EGbbtreeNode_t pointer to the node in the tree containing the
 * element, if no such node exists, return NULL.
 * @par Description:
 * This function will searxh for the element in the tree that satisfy
 * compare(elem,found)==0. */
EGbbtreeNode_t *EGbbtreeFind (EGbbtree_t * tree,
                              const void *elem)
{
  /* local variables */
  EGbbtreeNode_t *c_node = tree->root;
  int rval = 0;

  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  /* now we iterate */
  while (c_node)
  {
    rval = tree->compare (elem, c_node->this);
    if (!rval)
      break;
    if (rval < 0)
      c_node = c_node->left;
    else
      c_node = c_node->right;
  }

  /* ending */
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return c_node;
}

/* ========================================================================= */
/** @brief Macro to access the depth of the left child of a nodo */
#define EGbbtreeLeftDepth(__node) ((__node)->left?(__node)->left->depth:0U)

/* ========================================================================= */
/** @brief Macro to access the depth of the right child of a nodo */
#define EGbbtreeRightDepth(__node) ((__node)->right?(__node)->right->depth:0U)

/* ========================================================================= */
/** @brief Update the depth of a node, this function assumes that the depth of
 * the sons of the node are correctly set-up */
static inline int EGbbtreeUpdateDepth (EGbbtreeNode_t * const p_node)
{
  p_node->depth = EGbbtreeLeftDepth (p_node);
  if (p_node->right && p_node->depth < p_node->right->depth)
    p_node->depth = p_node->right->depth;
  p_node->depth++;
  return 0;
}

/* ========================================================================= */
/** @brief Rotate the given node to the right, and update the correspondig
 * depths.
 * @param p_node EGbbtreeNode_t** pointer to the pointer of the tree to rotate.
 * @param tree EGbbtree_t* pointer to the tree where the rotation is being
 * performed.
 * @return zero on success, non-zero otherwise. */
static inline int EGbbtreeRotateRight (EGbbtree_t * tree,
                                       EGbbtreeNode_t ** p_node)
{
  /* local variables */
  EGbbtreeNode_t *c_node = (*p_node)->left;
  MESSAGE (EG_BBTREE_DEBUGL, "entering at node %p", (void *) (*p_node));
  /* note that only c_node->right change relative positions, and *p_node, and
   * their parents. */
  if (!(c_node->parent = (*p_node)->parent))
    tree->root = c_node;
  else
  {
    if ((*p_node)->parent->left == (*p_node))
      (*p_node)->parent->left = c_node;
    else
      (*p_node)->parent->right = c_node;
  }
  if (((*p_node)->left = c_node->right))
    (*p_node)->left->parent = (*p_node);
  c_node->right = (*p_node);
  (*p_node)->parent = c_node;
  /* now we recalculate the depth of *p_node */
  EGbbtreeUpdateDepth (*p_node);
  /* update *p_node to c_node, i.e. to the root of the sub-tree */
  (*p_node) = c_node;
  /* now we recalculate the depth of *p_node */
  EGbbtreeUpdateDepth (*p_node);
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return 0;
}

/* ========================================================================= */
/** @brief Rotate the given node to the left, and update the correspondig
 * depths.
 * @param p_node EGbbtreeNode_t** pointer to the pointer of the tree to rotate.
 * @param tree EGbbtree_t* pointer to the tree where the rotation is being
 * performed.
 * @return zero on success, non-zero otherwise. */
static inline int EGbbtreeRotateLeft (EGbbtree_t * tree,
                                      EGbbtreeNode_t ** p_node)
{
  /* local variables */
  EGbbtreeNode_t *c_node = (*p_node)->right;
  MESSAGE (EG_BBTREE_DEBUGL, "entering at node %p", (void *) (*p_node));
  /* note that only c_node->left change relative positions, and *p_node, and
   * their parents. */
  if (!(c_node->parent = (*p_node)->parent))
    tree->root = c_node;
  else
  {
    if ((*p_node)->parent->left == (*p_node))
      (*p_node)->parent->left = c_node;
    else
      (*p_node)->parent->right = c_node;
  }
  if (((*p_node)->right = c_node->left))
    (*p_node)->right->parent = (*p_node);
  c_node->left = (*p_node);
  (*p_node)->parent = c_node;
  /* now we recalculate the depth of *p_node */
  EGbbtreeUpdateDepth (*p_node);
  /* update *p_node to c_node, i.e. to the root of the sub-tree */
  (*p_node) = c_node;
  /* now we recalculate the depth of *p_node */
  EGbbtreeUpdateDepth (*p_node);
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return 0;
}

/* ========================================================================= */
/** @brief This function balances a tree by rotations, starting in the given
 * node and working upwards.
 * @param p_node EGbbtreeNode_t** pointer to the pointer of the tree to rotate.
 * @param tree EGbbtree_t* pointer to the tree where the rotation is being
 * performed.
 * @return zero on success, non-zero otherwise.
 * */
static inline int EGbbtreeBalance (EGbbtree_t * tree,
                                   EGbbtreeNode_t ** p_node)
{
  /* local variables */
  unsigned diff;
  int rval = 0;
  MESSAGE (EG_BBTREE_DEBUGL, "entering");

  /* mian loop */
  while (*p_node)
  {
    /* first we set the depth of p_node */
    EGbbtreeUpdateDepth (*p_node);
    diff = EGbbtreeLeftDepth (*p_node) - EGbbtreeRightDepth (*p_node);
    /* here we test if we have to rotate */
    switch (diff)
    {
      /* case that the left side is deeper */
    case 2U:
      if (EGbbtreeRightDepth ((*p_node)->left) >
          EGbbtreeLeftDepth ((*p_node)->left))
      {
        (*p_node) = (*p_node)->left;
        rval = EGbbtreeRotateLeft (tree, p_node);
        CHECKRVAL (rval);
        (*p_node) = (*p_node)->parent;
      }
      rval = EGbbtreeRotateRight (tree, p_node);
      CHECKRVAL (rval);
      break;
      /* case the right side is deeper */
    case (-2U):
      if (EGbbtreeLeftDepth ((*p_node)->right) >
          EGbbtreeRightDepth ((*p_node)->right))
      {
        (*p_node) = (*p_node)->right;
        rval = EGbbtreeRotateRight (tree, p_node);
        CHECKRVAL (rval);
        (*p_node) = (*p_node)->parent;
      }
      rval = EGbbtreeRotateLeft (tree, p_node);
      CHECKRVAL (rval);
      break;
      /* if the difference in depth is no more than one, do nothing */
    case 1U:
    case 0U:
    case (-1U):
      break;
      /* if the difference is non of the above, throw an exception and exit */
    default:
      rval = 1;
      TESTG (1, CLEANUP, "unknown depth difference %u, fix the code!", diff);
      break;

    }
    MESSAGE (EG_BBTREE_DEBUGL, "  setting pnode(%p) to parent (%p)",
             (void *) (*p_node), (void *) ((*p_node)->parent));
    (*p_node) = (*p_node)->parent;
  }
CLEANUP:
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return rval;
}

/* ========================================================================= */
/** @brief Add a new element to the tree.
 * @param tree EGbbtree_t* pointer to the tree where we will add the new
 * element.
 * @param elem void* pointer to the element to be added to the tree.
 * @return EGbbtreeNode_t* pointer to the newly created node containing the
 * inserted element, if the eement already existed, we return NULL.
 * @par Description:
 * Add a new element (according to the comopare function) to the tree and
 * maintain the balance on the tree. If the element is repeated on the tree, it
 * will return NULL.
 * */
EGbbtreeNode_t *EGbbtreeAdd (EGbbtree_t * tree,
                             void *elem)
{
  /* local variables */
  EGbbtreeNode_t *c_node = tree->root,
   *p_node = 0;
  int rval = 0;
  MESSAGE (EG_BBTREE_DEBUGL, "entering");

  /* now we iterate */
  while (c_node)
  {
    rval = tree->compare (elem, c_node->this);
    p_node = c_node;
    c_node = (rval < 0) ? c_node->left : ((rval > 0) ? c_node->right : 0);
  }
  /* now p_node is the parent of the node where we will add the element, and
   * rval stores the value of compare(elem,p_node->this) if p_node is not NULL
   * ,i.e. if we are not addiing at the root of the tree. */
  if (p_node)
  {
    if (rval < 0)
      p_node->left = c_node = EGmemPoolSMalloc (tree->mem, EGbbtreeNode_t, 1U);
    else
      p_node->right = c_node = EGmemPoolSMalloc (tree->mem, EGbbtreeNode_t, 1U);
  }
  else
  {
    tree->root = c_node = EGmemPoolSMalloc (tree->mem, EGbbtreeNode_t, 1U);
  }
  memset (c_node, 0, sizeof (EGbbtreeNode_t));
  c_node->this = elem;
  c_node->parent = p_node;
  c_node->depth = 1;
  tree->size++;

  /* now we need to balance the tree */
  rval = EGbbtreeBalance (tree, &p_node);
  ADVCHECKRVAL (rval, 0);

  /* ending */
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return c_node;
}

/* ========================================================================= */
/** @brief, get the predecessor of the current node.
 * @param node EGbbtreeNode_t* pointer to the node to wich we are looking for
 * its predecessor.
 * @return EGbbtreeNode_t* pointer to the predecessor of the given node.
 * @par Description:
 * This function try to find the predecessor of the given node, if no such
 * node exists, return NULL.
 * */
EGbbtreeNode_t *EGbbtreePredecessor (EGbbtreeNode_t * node)
{
  /* local variables */
  EGbbtreeNode_t *c_node = node->left,
   *x_node = node;
  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  if (c_node)
  {
    while (c_node->right)
      c_node = c_node->right;
    MESSAGE (EG_BBTREE_DEBUGL, "done");
    return c_node;
  }
  c_node = node->parent;
  while (c_node && x_node == c_node->left)
  {
    x_node = c_node;
    c_node = c_node->parent;
  }
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return c_node;
}

/* ========================================================================= */
/** @brief, get the successor of the current node.
 * @param node EGbbtreeNode_t* pointer to the node to wich we are looking for
 * its successor.
 * @return EGbbtreeNode_t* pointer to the successor of the given node.
 * @par Description:
 * This function try to find the successor of the given node, if no such node
 * exists, return NULL.
 * */
EGbbtreeNode_t *EGbbtreeSuccessor (EGbbtreeNode_t * node)
{
  /* local variables */
  EGbbtreeNode_t *c_node = node->right,
   *x_node = node;
  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  if (c_node)
  {
    while (c_node->left)
      c_node = c_node->left;
    MESSAGE (EG_BBTREE_DEBUGL, "done");
    return c_node;
  }
  c_node = node->parent;
  while (c_node && x_node == c_node->right)
  {
    x_node = c_node;
    c_node = c_node->parent;
  }
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return c_node;
}

/* ========================================================================= */
/** @brief Delete an element from the tree.
 * @param tree EGbbtree_t* pointer to the tree from where we will eliminate the
 * given node.
 * @param node EGbbtreeNode_t* pointer to the node of the tree to be
 * eliminated.
 * @return zero on success, non-zero otherwise.
 * @par Description:
 * Given an initialized tree, and a ode pertaianing to it (the code won't check
 * this), it will eliminate the node form the tree. If an error occour, it will
 * return non-zero. Note that this funcion won't free the internal satelite
 * data of the given node, this should be done by the caller of the function
 * __BEFORE__ using this function.
 * */
int EGbbtreeRemove (EGbbtree_t * tree,
                    EGbbtreeNode_t * node)
{
  /* local variables */
  EGbbtreeNode_t *p_node = node->parent;
  EGbbtreeNode_t *n_node;
  MESSAGE (EG_BBTREE_DEBUGL, "entering");

  /* there are three cases to follow, the dirs is that the current node has
   * both left and right childrends, in this case we move it so that it now has
   * either a left child or a right child, but no both. */
  if (node->left && node->right)
  {
    n_node = EGbbtreePredecessor (node);
    /* we handle in a different manner the case where the predecesor of node is
     * its left son */
    /* set n_node<->parent connections */
    if (n_node->parent == node)
    {
      if ((n_node->parent = node->parent))
      {
        if (node->parent->left == node)
          node->parent->left = n_node;
        else
          node->parent->right = n_node;
      }
      else
        tree->root = n_node;
      /* set n_node<->right connections */
      n_node->right = node->right;
      n_node->right->parent = n_node;
      p_node = n_node;
      EGbbtreeUpdateDepth (n_node);
      goto END;
    }
    /* set n_node->parent and reverse connection */
    p_node = n_node->parent;
    if ((n_node->parent = node->parent))
    {
      if (node->parent->left == node)
        node->parent->left = n_node;
      else
        node->parent->right = n_node;
    }
    else
      tree->root = n_node;
    /* set node->parent and reverse connection */
    EXIT (node == p_node, "node and p_node are equal");
    node->parent = p_node;
    if (node->parent->left == n_node)
      node->parent->left = node;
    else
      node->parent->right = node;
    /* set node->left */
    n_node->right = node->left;
    if ((node->left = n_node->left))
      node->left->parent = node;
    /* set n_node->left */
    if ((n_node->left = n_node->right))
      n_node->left->parent = n_node;
    /* set n_node->right */
    if ((n_node->right = node->right))
      node->right->parent = n_node;
    /* set node->right */
    node->right = 0;
    /* update depths */
    EGbbtreeUpdateDepth (n_node);
    EGbbtreeUpdateDepth (node);
  }

  /* now node has either one or none child */
  if (node->right)
  {
    if (p_node)
    {
      if (p_node->left == node)
        p_node->left = node->right;
      else
        p_node->right = node->right;
      node->right->parent = p_node;
    }
    else
    {
      tree->root = node->right;
      node->right->parent = 0;
    }
  }
  else if (node->left)
  {
    if (p_node)
    {
      if (p_node->left == node)
        p_node->left = node->left;
      else
        p_node->right = node->left;
      node->left->parent = p_node;
    }
    else
    {
      tree->root = node->left;
      node->left->parent = 0;
    }
  }
  /* this is the easiest case, we just eliminate the node, and balance its
   * parent. */
  else
  {
    if (p_node)
    {
      if (p_node->left == node)
        p_node->left = 0;
      else
        p_node->right = 0;
    }
    else
      tree->root = 0;
  }
END:
  /* this are common steps to follow */
  EGmemPoolSFree (node, EGbbtreeNode_t, 1, tree->mem);
  tree->size--;
  /* and to finish we balance the tree */
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return EGbbtreeBalance (tree, &p_node);
}

/* ========================================================================= */
/** @brief Display function for the tree.
 * @param tree EGbbtree_t* pointer to the tree to be displayed.
 * @param dataDisplay EGdisplay_f function that display the internal data (can
 * be NULL).
 * @param file FILE* pointer to the output stream.
 * @par Description: Display information of the tree, it's nodes, and the
 * internal data.
 * */
void EGbbtreeDisplay (EGbbtree_t * tree,
                      EGdisplay_f dataDisplay,
                      FILE * file)
{
  /* local variables */
  EGbbtreeNode_t *c_node;
  unsigned int stack_size = 4 * (1.5 + log2l ((long double) (tree->size + 1))),
    stack_pos = 0;
  EGbbtreeNode_t **stack = EGmemPoolSMalloc (tree->mem,
                                             EGbbtreeNode_t *, stack_size);
  MESSAGE (EG_BBTREE_DEBUGL, "entering");

  /* init the stack */
  stack[stack_pos] = tree->root;

  /* display the general information first */
  fprintf (file, "\nTree %p:\n"
           "\tNodes  :  %u\n"
           "\tPool   :  %p\n"
           "\tCompare:  %tX\n", (void *) tree, tree->size,
           (void *) tree->mem, (size_t) (tree->compare));

  if (tree->size)
    while (~stack_pos)
    {
      c_node = stack[stack_pos];
      stack_pos--;
      if (c_node->left)
        stack[++stack_pos] = c_node->left;
      if (c_node->right)
        stack[++stack_pos] = c_node->right;
      fprintf (file, "  Node %p (DP:%d,THS:%p)\n", (void *) c_node,
               c_node->depth, c_node->this);
      if (dataDisplay)
        dataDisplay (c_node->this, file);
    }

  /* ending */
  EGmemPoolSFree (stack, EGbbtreeNode_t *, stack_size,
                  ((EGbbtree_t *) tree)->mem);
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return;
}

/* ========================================================================= */
/** @brief Return the minimum element in the tree.
 * @param tree EGbbtree_t* pointer to the tree to be displayed.
 * @return pointer to the treeNode pointing to the minimum element.
 * @par Description:
 * Given a tree, return the minimum eloement on the tree (pointer to the
 * connector).
 * */
EGbbtreeNode_t *EGbbtreeMin (EGbbtree_t * tree)
{
  EGbbtreeNode_t *root = tree->root;
  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  while (root && root->left)
    root = root->left;
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return root;
}

/* ========================================================================= */
/** @brief Return the maximum element in the tree.
 * @param tree EGbbtree_t* pointer to the tree to be displayed.
 * @return pointer to the treeNode pointing to the maximum element.
 * @par Description:
 * Given a tree, return the maximum eloement on the tree (pointer to the
 * connector).
 * */
EGbbtreeNode_t *EGbbtreeMax (EGbbtree_t * tree)
{
  EGbbtreeNode_t *root = tree->root;
  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  while (root && root->right)
    root = root->right;
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return root;
}



/* ========================================================================= */
/** } */
/* end of eg_bbtree.c */

---