/*--------------------------------------------------------------*/
/*  Matt Michie                                                 */
/*  CS 372 - Extra Credit                                       */
/*  mmichie@cs.nmsu.edu                                         */
/*  November 15, 2001                                           */
/*                                                              */
/*  Filename: redblack.h                                        */
/*--------------------------------------------------------------*/

/*--------------------------------------------------------------*/
/*  Global constants & Type Defines                             */
/*--------------------------------------------------------------*/
typedef enum { black, red } ColorType;

typedef struct RedBlackTree {
	struct RedBlackTree *left;
	struct RedBlackTree *right;
	struct RedBlackTree *parent;
	ColorType color;
	int key;
} RedBlackTree;

#define NIL &sentinel

/*--------------------------------------------------------------*/
/*  Function Prototyping                                        */
/*--------------------------------------------------------------*/
void LeftRotate(RedBlackTree * x);
void RightRotate(RedBlackTree * x);
RedBlackTree *Insert(int key);
void DeleteFix(RedBlackTree * x);
void DeleteNode(RedBlackTree * z);
void Output(int Element);
void PrintTree(RedBlackTree * T);

/*--------------------------------------------------------------*/
/*  Global variables                                            */
/*--------------------------------------------------------------*/
RedBlackTree sentinel;
RedBlackTree *root;