rb.c

稀疏矩阵、链表、图、队列、二叉树、多叉树、排序、遗传算法等的实现

/* rb - manipulates red-black trees.
   Derived from libavl for manipulation of binary trees.
   Copyright (C) 1998-2000 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   This program 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
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.

   The author may be contacted at <[e-mail]> on the Internet,
   or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA through
   more mundane means. */

#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* A node color. */
enum color {
  RB_RED,
  RB_BLACK
};

/* A red-black tree node. */
struct rb_node {
  struct rb_node *link[2];
  int data;
  enum color color;
};

/* A red-black tree. */
struct rb_tree {
  struct rb_node *root;
  int count;
};

/* Creates and returns a new red-black tree.  Returns a null pointer
   if a memory allocation error occurs. */
struct rb_tree *rb_create(void)
{
  struct rb_tree *tree = malloc(sizeof *tree);
  if (tree == NULL)
    return NULL;
  tree->root = NULL;
  tree->count = 0;
  return tree;
}

/* Searches TREE for matching ITEM.  Returns 1 if found, 0
   otherwise. */
int rb_search(const struct rb_tree *tree, int item)
{
  const struct rb_node *node;

  assert(tree != NULL);
  node = tree->root;
  for (;;) {
    if (node == NULL)
      return 0;
    else if (item == node->data)
      return 1;
    else if (item > node->data)
      node = node->link[1];
    else
      node = node->link[0];
  }
}

/* Allocates a new node in TREE at *NODE.  Sets the node's parent to
   PARENT and data to ITEM, and initializes the other fields
   appropriately. */
static struct rb_node *new_node(struct rb_tree *tree,
				int item, enum color color)
{
  struct rb_node *node = malloc(sizeof *node);
  if (node == NULL)
    return NULL;
  node->data = item;
  node->link[0] = node->link[1] = NULL;
  node->color = color;
  tree->count++;
  return node;
}

/* Inserts ITEM into TREE.  Returns 1 if the item was inserted, 2 if
   an identical item already existed in TREE, or 0 if a memory
   allocation error occurred. */
int rb_insert(struct rb_tree *tree, int item)
{
  struct rb_node *ap[48];
  int ad[48];
  int ak;

  struct rb_node *x, *y;

  assert(tree != NULL);
  if (tree->root == NULL) {
    tree->root = new_node(tree, item, RB_BLACK);
    return tree->root != NULL;
  }

  ad[0] = 0;
  ap[0] = (struct rb_node *) &tree->root;
  ak = 1;

  x = tree->root;
  for (;;) {
    int dir;

    if (item == x->data)
      return 2;
    dir = item > x->data;

    ap[ak] = x;
    ad[ak++] = dir;
    y = x->link[dir];
    if (y == NULL) {
      x = x->link[dir] = new_node(tree, item, RB_RED);
      if (x == NULL)
	return 0;
      break;
    }
    x = y;
  }

  while (ap[ak - 1]->color == RB_RED)
    if (ad[ak - 2] == 0) {
      y = ap[ak - 2]->link[1];
      if (y != NULL && y->color == RB_RED) {
	ap[--ak]->color = y->color = RB_BLACK;
	ap[--ak]->color = RB_RED;
      }
      else {
	if (ad[ak - 1] == 1) {
	  x = ap[ak - 1];
	  y = x->link[1];
	  x->link[1] = y->link[0];
	  y->link[0] = x;
	  ap[ak - 2]->link[0] = y;
	}
	else
	  y = ap[ak - 1];

	x = ap[ak - 2];
	x->color = RB_RED;
	y->color = RB_BLACK;

	x->link[0] = y->link[1];
	y->link[1] = x;
	ap[ak - 3]->link[ad[ak - 3]] = y;

	break;
      }
    }
    else {
      y = ap[ak - 2]->link[0];
      if (y != NULL && y->color == RB_RED) {
	ap[--ak]->color = y->color = RB_BLACK;
	ap[--ak]->color = RB_RED;
      }
      else {
	if (ad[ak - 1] == 0) {
	  x = ap[ak - 1];
	  y = x->link[0];
	  x->link[0] = y->link[1];
	  y->link[1] = x;
	  ap[ak - 2]->link[1] = y;
	}
	else
	  y = ap[ak - 1];

	x = ap[ak - 2];
	x->color = RB_RED;
	y->color = RB_BLACK;

	x->link[1] = y->link[0];
	y->link[0] = x;
	ap[ak - 3]->link[ad[ak - 3]] = y;
	break;
      }
    }

  tree->root->color = RB_BLACK;

  return 1;
}

/* Deletes any item matching ITEM from TREE.  Returns 1 if such an
   item was deleted, 0 if none was found. */
int rb_delete(struct rb_tree *tree, int item)
{
  struct rb_node *ap[48];
  int ad[48];
  int k;

  struct rb_node *w, *x, *y, *z;

  assert(tree != NULL);

  ad[0] = 0;
  ap[0] = (struct rb_node *) &tree->root;
  k = 1;

  z = tree->root;
  for (;;) {
    int dir;

    if (z == NULL)
      return 0;

    if (item == z->data)
      break;
    dir = item > z->data;

    ap[k] = z;
    ad[k++] = dir;
    z = z->link[dir];
  }
  tree->count--;

  if (z->link[0] == NULL || z->link[1] == NULL) {
    y = z;

    x = y->link[0];
    if (x == NULL)
      x = y->link[1];
  }
  else {
    ap[k] = z;
    ad[k++] = 1;
    y = z->link[1];

    while (y->link[0] != NULL) {
      ap[k] = y;
      ad[k++] = 0;
      y = y->link[0];
    }

    x = y->link[1];
    z->data = y->data;
  }
  ap[k - 1]->link[ad[k - 1]] = x;

  if (y->color == RB_RED) {
    free(y);
    return 1;
  }

  free(y);

  while (k > 1 && (x == NULL || x->color == RB_BLACK))
    if (ad[k - 1] == 0) {
      w = ap[k - 1]->link[1];

      if (w->color == RB_RED) {
	w->color = RB_BLACK;
	ap[k - 1]->color = RB_RED;

	ap[k - 1]->link[1] = w->link[0];
	w->link[0] = ap[k - 1];
	ap[k - 2]->link[ad[k - 2]] = w;

	ap[k] = ap[k - 1];
	ad[k] = 0;
	ap[k - 1] = w;
	k++;

	w = ap[k - 1]->link[1];
      }

      if ((w->link[0] == NULL || w->link[0]->color == RB_BLACK)
	  && (w->link[1] == NULL || w->link[1]->color == RB_BLACK)) {
	w->color = RB_RED;
	x = ap[k - 1];
	k--;
      }
      else {
	if (w->link[1] == NULL || w->link[1]->color == RB_BLACK) {
	  w->link[0]->color = RB_BLACK;
	  w->color = RB_RED;

	  y = w->link[0];
	  w->link[0] = y->link[1];
	  y->link[1] = w;

	  w = ap[k - 1]->link[1] = y;
	}

	w->color = ap[k - 1]->color;
	ap[k - 1]->color = RB_BLACK;
	w->link[1]->color = RB_BLACK;

	ap[k - 1]->link[1] = w->link[0];
	w->link[0] = ap[k - 1];
	ap[k - 2]->link[ad[k - 2]] = w;

	x = tree->root;
	break;
      }
    }
    else {
      w = ap[k - 1]->link[0];
      if (w->color == RB_RED) {
	w->color = RB_BLACK;
	ap[k - 1]->color = RB_RED;

	ap[k - 1]->link[0] = w->link[1];
	w->link[1] = ap[k - 1];
	ap[k - 2]->link[ad[k - 2]] = w;

	ap[k] = ap[k - 1];
	ad[k] = 1;
	ap[k - 1] = w;
	k++;

	w = ap[k - 1]->link[0];
      }

      if ((w->link[0] == NULL || w->link[0]->color == RB_BLACK)
	  && (w->link[1] == NULL || w->link[1]->color == RB_BLACK)) {
	w->color = RB_RED;
	x = ap[k - 1];