sfltree.c

短小精悍的C语言标准函数库。提供450个以上的可移植的算法和工具代码。

            sibling = tree-> parent-> right;
            if (sibling-> colour == RED)
              {
                sibling->       colour = BLACK;
                tree-> parent-> colour = RED;
                rotate_left (root, tree-> parent);
                sibling = tree-> parent-> right;
              }
            if ((sibling-> left->  colour == BLACK)
            &&  (sibling-> right-> colour == BLACK))
              {
                sibling-> colour = RED;
                tree = tree-> parent;
              }
            else
              {
                if (sibling-> right-> colour == BLACK)
                  {
                    sibling-> left-> colour = BLACK;
                    sibling->        colour = RED;
                    rotate_right (root, sibling);
                    sibling = tree-> parent-> right;
                  }
                sibling-> colour = tree-> parent-> colour;
                tree->    parent-> colour = BLACK;
                sibling-> right->  colour = BLACK;
                rotate_left (root, tree-> parent);
                tree = *root;
              }
          }
        else
          {
            sibling = tree-> parent-> left;
            if (sibling-> colour == RED)
              {
                sibling->       colour = BLACK;
                tree-> parent-> colour = RED;
                rotate_right (root, tree-> parent);
                sibling = tree-> parent-> left;
              }
            if ((sibling-> right-> colour == BLACK)
            &&  (sibling-> left->  colour == BLACK))
              {
                sibling-> colour = RED;
                tree = tree-> parent;
              }
            else
              {
                if (sibling-> left-> colour == BLACK)
                  {
                    sibling-> right-> colour = BLACK;
                    sibling->         colour = RED;
                    rotate_left (root, sibling);
                    sibling = tree-> parent-> left;
                  }
                sibling-> colour = tree-> parent-> colour;
                tree->    parent-> colour = BLACK;
                sibling-> left->   colour = BLACK;
                rotate_right (root, tree-> parent);
                tree = *root;
              }
          }
      }
    tree-> colour = BLACK;
}


/*  ---------------------------------------------------------------------[<]-
    Function: tree_find_eq

    Synopsis: Finds a node with data exactly matching that provided.
    ---------------------------------------------------------------------[>]-*/

void *tree_find_eq (TREE **root, void *tree, TREE_COMPARE *comp)
{
    TREE
       *current = *root,
       *found;

    found = NULL;
    while (current != TREE_NULL)
        switch ((comp) (current, tree))
          {
            case -1: current = current-> right; break;
            case  1: current = current-> left;  break;
            default: found = current;           /*  In case of duplicates,   */
                     current = current-> left;  /*  get the first one.       */
          }

    return found;
}


/*  ---------------------------------------------------------------------[<]-
    Function: tree_find_lt

    Synopsis: Finds node with data less than that provided.
    ---------------------------------------------------------------------[>]-*/

void *tree_find_lt (TREE **root, void *tree, TREE_COMPARE *comp)
{
    TREE
       *current = *root,
       *found;

    found = NULL;
    while (current != TREE_NULL)
        switch ((comp) (current, tree))
          {
            case -1: found = current;
                     current = current-> right; break;
            default: current = current-> left;
          }

    return found;
}


/*  ---------------------------------------------------------------------[<]-
    Function: tree_find_le

    Synopsis: Finds node with data less than or equal to that provided.
    ---------------------------------------------------------------------[>]-*/

void *tree_find_le (TREE **root, void *tree, TREE_COMPARE *comp)
{
    TREE
       *current = *root,
       *found;

    found = NULL;
    while (current != TREE_NULL)
        switch ((comp) (current, tree))
          {
            case 1 : current = current-> left;  break;
            default: found = current;
                     current = current-> right;
          }

    return found;
}


/*  ---------------------------------------------------------------------[<]-
    Function: tree_find_gt

    Synopsis: Finds node with data greater than that provided.
    ---------------------------------------------------------------------[>]-*/

void *tree_find_gt (TREE **root, void *tree, TREE_COMPARE *comp)
{
    TREE
       *current = *root,
       *found;

    found = NULL;
    while (current != TREE_NULL)
        switch ((comp) (current, tree))
          {
            case 1 : found = current;
                     current = current-> left; break;
            default: current = current-> right;
          }

    return found;
}


/*  ---------------------------------------------------------------------[<]-
    Function: tree_find_ge

    Synopsis: Finds node with data greater than or equal to that provided.
    ---------------------------------------------------------------------[>]-*/

void *tree_find_ge (TREE **root, void *tree, TREE_COMPARE *comp)
{
    TREE
       *current = *root,
       *found;

    found = NULL;
    while (current != TREE_NULL)
        switch ((comp) (current, tree))
          {
            case -1: current = current-> right; break;
            default: found = current;
                     current = current-> left;
          }

    return found;
}


/*  ---------------------------------------------------------------------[<]-
    Function: tree_traverse

    Synopsis: Traverse the tree, calling a processing function at each
    node.
    ---------------------------------------------------------------------[>]-*/

void tree_traverse (void *tree, TREE_PROCESS *process, int method)
{
    if ((!tree)
    ||  (tree == TREE_NULL))
        return;

    if (method == 1)
      {
        (process) (tree);
        tree_traverse (((TREE *) tree)-> left,  process, method);
        tree_traverse (((TREE *) tree)-> right, process, method);
      }
    else if (method == 2)
      {
        tree_traverse (((TREE *) tree)-> left,  process, method);
        tree_traverse (((TREE *) tree)-> right, process, method);
        (process) (tree);
      }
    else
      {
        tree_traverse (((TREE *) tree)-> left,  process, method);
        (process) (tree);
        tree_traverse (((TREE *) tree)-> right, process, method);
      }
}


/*  ---------------------------------------------------------------------[<]-
    Function: tree_first

    Synopsis: Finds and returns the first node in a (sub-)tree.
    ---------------------------------------------------------------------[>]-*/

void *tree_first (void *tree)
{
    TREE
       *current;

    if ((!tree)
    ||  (tree == TREE_NULL))
        return NULL;

    current = tree;
    while (current-> left != TREE_NULL)
        current = current-> left;

    return current;
}


/*  ---------------------------------------------------------------------[<]-
    Function: tree_last

    Synopsis: Finds and returns the last node in a (sub-)tree.
    ---------------------------------------------------------------------[>]-*/

void *tree_last (void *tree)
{
    TREE
       *current;

    if ((!tree)
    ||  (tree == TREE_NULL))
        return NULL;

    current = tree;
    while (current-> right != TREE_NULL)
        current = current-> right;

    return current;
}


/*  ---------------------------------------------------------------------[<]-
    Function: tree_next

    Synopsis: Finds and returns the next node in a tree.
    ---------------------------------------------------------------------[>]-*/

void *tree_next (void *tree)
{
    TREE
       *current,
       *child;

    if ((!tree)
    ||  (tree == TREE_NULL))
        return NULL;

    current = tree;
    if (current-> right != TREE_NULL)
        return tree_first (current-> right);
    else
      {
        current = tree;
        child   = TREE_NULL;
        while ((current-> parent)
           &&  (current-> right == child))
          {
            child = current;
            current = current-> parent;
          }
        if (current-> right != child)
            return current;
        else
            return NULL;
      }
}


/*  ---------------------------------------------------------------------[<]-
    Function: tree_prev

    Synopsis: Finds and returns the previous node in a tree.
    ---------------------------------------------------------------------[>]-*/

void *tree_prev (void *tree)
{
    TREE
       *current,
       *child;

    if ((!tree)
    ||  (tree == TREE_NULL))
        return NULL;

    current = tree;
    if (current-> left != TREE_NULL)
        return tree_last (current-> left);
    else
      {
        current = tree;
        child   = TREE_NULL;
        while ((current-> parent)
           &&  (current-> left == child))
          {
            child = current;
            current = current-> parent;
          }
        if (current-> left != child)
            return current;
        else
            return NULL;
      }
}