intervaltree.h

数据结构中区间树（红黑树的扩展出来的一种数据结构）的C语言实现。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2

typedef int status;
typedef enum color
{
	red,black
}color;
typedef struct IntervalTreeNode
{
	int low;
	int high;
	int max;
	color clr;
	struct IntervalTreeNode *parent;
	struct IntervalTreeNode *lChild;
	struct IntervalTreeNode *rChild;
}IntervalTNode,*pIntervalTNode;

int Max(pIntervalTNode x,pIntervalTNode y,pIntervalTNode z)
{
	int maximum;
	if(x!=NULL)
	{
		maximum=x->max;
		if(y!=NULL)
		{
			maximum=maximum>=y->max?x->max:y->max;
			if(z!=NULL)
				maximum=maximum>=z->max?maximum:z->max;
		}
		return maximum;
	}
	else if(y!=NULL)
	{
		maximum=y->max;
		if(z!=NULL)
				maximum=maximum>=z->max?maximum:z->max;
		return maximum;
	}
	else if(z!=NULL)
		return z->max;
	else 
		return FALSE;
}

status LeftRotate(IntervalTNode **tRoot,pIntervalTNode x)
{
	if(x!=NULL&&x->rChild!=NULL)
	{
		pIntervalTNode y;
		y=x->rChild;
		y->max=x->max;
		x->max=Max(x,x->lChild,y->lChild);
		x->rChild=y->lChild;
		if(y->lChild!=NULL)
			y->lChild->parent=x;
		y->parent=x->parent;
		if(x->parent==NULL)
		{
			(*tRoot)=y;
			y->parent=NULL;
		}
		else if(x==x->parent->lChild)
			x->parent->lChild=y;
		else
			x->parent->rChild=y;
		y->lChild=x;
		x->parent=y;
		return OK;
	}
	else return FALSE;
}

status RightRotate(IntervalTNode **tRoot,pIntervalTNode y)
{
	if(y!=NULL&&y->lChild!=NULL)
	{
		pIntervalTNode x=y->lChild;
		x->max=y->max;
		y->max=Max(y,y->rChild,x->rChild);
		y->lChild=x->rChild;
		if(x->rChild!=NULL)
			x->rChild->parent=y;
		x->parent=y->parent;
		if(y->parent==NULL)
		{
			(*tRoot)=x;
			x->parent=NULL;
		}
		else if(y==y->parent->lChild)
			y->parent->lChild=x;
		else
			y->parent->rChild=x;
		x->rChild=y;
		y->parent=x;
		return OK;
	}
	else return FALSE;
}

status RBTInsertFixup(IntervalTNode **tRoot,pIntervalTNode z)
{
	pIntervalTNode y;
	while(z->parent!=NULL&&z->parent->clr==red)
	{
		if(z->parent==z->parent->parent->lChild)
		{
			y=z->parent->parent->rChild;
			if(y!=NULL&&y->clr==red)
			{
				z->parent->clr=black;
				y->clr=black;
				z->parent->parent->clr=red;
				z=z->parent->parent;

			}
			else
			{
				if(z==z->parent->rChild)
				{
					z=z->parent;
					LeftRotate(tRoot,z);
				}
				z->parent->clr=black;
				z->parent->parent->clr=red;
				RightRotate(tRoot,z->parent->parent);
			}
		}
		else
		{
			y=z->parent->parent->lChild;
			if(y!=NULL&&y->clr==red)
			{
				z->parent->clr=black;
				y->clr=black;
				z->parent->parent->clr=red;
				z=z->parent->parent;

			}
			else
			{
				if(z==z->parent->lChild)
				{
					z=z->parent;
					RightRotate(tRoot,z);
				}
				z->parent->clr=black;
				z->parent->parent->clr=red;
				LeftRotate(tRoot,z->parent->parent);
			}
		}
	}
	(*tRoot)->clr=black;
	return OK;
}

status IntervalTInsertFixup(IntervalTNode **tRoot,pIntervalTNode z)
{
	pIntervalTNode y;
	while(z->parent!=NULL&&z->parent->clr==red)
	{
		if(z->parent==z->parent->parent->lChild)
		{
			y=z->parent->parent->rChild;
			if(y!=NULL&&y->clr==red)
			{
				z->parent->clr=black;
				y->clr=black;
				z->parent->parent->clr=red;
				z=z->parent->parent;

			}
			else
			{
				if(z==z->parent->rChild)
				{
					z=z->parent;
					LeftRotate(tRoot,z);
				}
				z->parent->clr=black;
				z->parent->parent->clr=red;
				RightRotate(tRoot,z->parent->parent);
			}
		}
		else
		{
			y=z->parent->parent->lChild;
			if(y!=NULL&&y->clr==red)
			{
				z->parent->clr=black;
				y->clr=black;
				z->parent->parent->clr=red;
				z=z->parent->parent;

			}
			else
			{
				if(z==z->parent->lChild)
				{
					z=z->parent;
					RightRotate(tRoot,z);
				}
				z->parent->clr=black;
				z->parent->parent->clr=red;
				LeftRotate(tRoot,z->parent->parent);
			}
		}
	}
	(*tRoot)->clr=black;
	return OK;
}

status IntervalTInsert(IntervalTNode **tRoot,pIntervalTNode z)
{
	pIntervalTNode y=NULL;
	pIntervalTNode x=*tRoot;
	while(x!=NULL)
	{
		y=x;
		if(z->low<x->low)
		{
			if(z->high>x->max)
				x->max=z->high;
			x=x->lChild;
		}
		else
		{
			if(z->high>x->max)
				x->max=z->high;
			x=x->rChild;
		}
	}
	z->parent=y;
	if(y==NULL)
	{
		*tRoot=z;
		z->parent=NULL;
	}
	else if(z->low<y->low)
		y->lChild=z;
	else
		y->rChild=z;
	z->max=z->high;
	z->lChild=NULL;
	z->rChild=NULL;
	z->clr=red;
	IntervalTInsertFixup(tRoot,z);
	return OK;
}

int Overlap(pIntervalTNode x,pIntervalTNode y)
{
	if(x->low<=y->high&&y->low<=x->high)
		return OK;
	else
		return FALSE;
}
pIntervalTNode IntervalSearch(pIntervalTNode tRoot,int iLow,int iHigh)
{
	pIntervalTNode x,y;
	x=tRoot;
	IntervalTNode temp;
	temp.low=iLow;
	temp.high=iHigh;
	y=&temp;
	int i=Overlap(x,y);
	while(x!=NULL&&i==0)
	{
		if(x->lChild!=NULL&&x->lChild->max>=iLow)
			x=x->lChild;
		else
			x=x->rChild;
		i=Overlap(x,y);
	}
	return x;
}

status InorderIntTWalk(pIntervalTNode tRoot)
{
	if(tRoot!=NULL)
	{
		InorderIntTWalk(tRoot->lChild);
		printf("low=%d,high=%d,max=%d,color=%d ",tRoot->low,tRoot->high,tRoot->max,(int)tRoot->clr);
		InorderIntTWalk(tRoot->rChild);
	}
	return OK;
}