intervalsearch.cpp

区间树上的重叠区间查找算法:通过增加树结点的信息域将红黑树扩张为区间树

#include <iostream.h>
using namespace std;
#include <ctime>
#include <cstdlib>

enum Color{black,red}; //only two colors optional

typedef struct IntervalTree  //structure of a single node
{
	struct IntervalTree *p;    //pointer to parent
    struct IntervalTree *left, *right;   //pointer to left child and right child
	Color color;    //color field
	int max;
	int low;        //define interval [low,high]
    int high;
}IntervalTree,*INTT;

INTT Interval_Insert(INTT root, int low, int high);
INTT Interval_Insert_Fixup(INTT root, INTT z);
INTT Interval_Search_Min(INTT root, int low, int high);
void Left_Rotate(INTT x, INTT& root);
void Right_Rotate(INTT y, INTT& root);

void Left_Rotate(INTT x, INTT& root)
{
    int i,j;
    INTT y;
    y = x->right;       //set y
    i = x->max;         //save the x and y's original max value to i,j
    j = y->max;
    x->right  = y->left;  //Turn y's left subtree into x's right subtree
    if(y->left!=NULL)
    y->left->p = x;
    y->p = x->p;          //link x's parent to y
    if (x == root)
    root = y;
    else if (x == x->p->left)
         x->p->left = y;
    else x->p->right = y;
    y->left = x;           //put x on y's left
    x->p = y;
    //update max
    if(x->high>j)
	  x->max = x->high;
    else
      x->max = j;
    if(y->high>i)
	  y->max = y->high;
    else
      y->max = i;
}

void Right_Rotate(INTT y, INTT& root)
{
     INTT x;
     int i=0, j=0;
     x = y->left;           //set x
     y->left = x->right;    //Turn x's right subtree into y's left subtree
     if(x->right!=NULL)
        x->right->p = y;
     x->p = y->p;           //link y's parent to x
     if(y==root)
          root = x;
     else if(y==y->p->left)
          y->p->left = x;
     else y->p->right = x;
     x->right = y;           //put y on x's right
     y->p = x;
     //update max
     if(y->high>j)
	    y->max = y->high;
     else
        y->max = j;
     if(x->high>i)
	    x->max = x->high;
     else
        x->max = i;
}

INTT Interval_Insert(INTT root, int low, int high)
{   //allocate node for data and insert in a tree
    INTT x, y, z;
    if ((z = (INTT)malloc(sizeof(IntervalTree)))==NULL)
    {
        cout<<"Memory alloc error"<<endl;
        return NULL;
    }
    z->low = low;
    z->high= high;
    z->max = high;
    x = root, y = NULL;       //y always points to x's parent
    while(x!=NULL)
    {
       y = x;
       if(low < x->low)
            x = x->left;
       else x = x->right;
    }
    z->p = y;           //put z into the proper location
    if(y==NULL)
       root = z;
    else if(low < y->low)
            y->left = z;
       else y->right = z;
    z->left = NULL;       //set the children of z to NULL
    z->right = NULL;
    z->color = red;           //color newly insert node red
    Interval_Insert_Fixup(root,z);  //restore the red-black properties
}

INTT Interval_Insert_Fixup(INTT root, INTT z)
{
    INTT y, temp;
    temp = z;
    while (z!=root && z->p->color==red)
    {  //case 1~3, p[z] is p[p[z]]'s left child
        if (z->p==z->p->p->left)
        {
            y = z->p->p->right;  //set y as z's uncle
            if (y!=NULL && y->color==red)
            {
            //case1: if uncle is red, change color of parent,uncle and grandpa directly
                z->p->color = black;
                y->color = black;
                z->p->p->color = red;
            //trace to grandpa, check if violate the properties of Red-Black-Tree
                z = z->p->p;
            }
            else
            {   /*case2~3: if uncle is black, rotate to keep balance and change
                  the color of parent and grandpa   */
                if (z == z->p->right)
                {   //make z a left child
                    z = z->p;
                    Left_Rotate(z, root);
                }
                //recolor and rotate
                z->p->color = black;
                z->p->p->color = red;
                Right_Rotate(z->p->p, root);
            }
        }
        else
        //case 4~6, p[z] is p[p[z]]'s right child
        //mirror image of above code
        {
            y = z->p->p->left;
            if (y!=NULL && y->color==red)
            {   //uncle is red
                z->p->color = black;
                y->color = black;
                z->p->p->color = red;
                z = z->p->p;
            }
            else
            {   //uncle is black
                if (z == z->p->left)
                {
                    z = z->p;
                    Right_Rotate(z, root);
                }
                z->p->color = black;
                z->p->p->color = red;
                Left_Rotate(z->p->p, root);
            }
        }
    }
   while(temp->p!=NULL && temp->p->max<temp->max)   //update max
    {
    	temp->p->max = temp->max;
    	temp = temp->p;
    }
    root->color = black;
    return root;
}

INTT Interval_Search_Min(INTT root, int low, int high)
{
    INTT x,y;
    x = root;
    if(x->left!=NULL &&x->left->max>=low) //the left subtree may contain an interval that overlaps i
    {  //recursively check left[x]'s left sub-tree
       y = Interval_Search_Min(x->left,low,high);
       if(y!=NULL)    //if found, return the node
       return y;
       else if(x!=NULL && (x->low<=high && low<=x->high))
       return x;
       else return NULL;
    }
    else if(x!=NULL && (x->low<=high && low<=x->high))//not found,but x overlaps i,return x
    return x;
    //neither x nor x's left sub-tree contains node that overlaps i,check right sub-tree
    else if(x->right==NULL)
    return NULL;
    else return Interval_Search_Min(x->right,low,high);
}

void Print_Node(INTT T)
{
    char* color[] = {"black", "red"};
    cout<<"color = "<<color[T->color]<<"  ";
    cout<<"low = "<<T->low<<"  ";
    cout<<"high = "<<T->high<<"  ";
    cout<<"max = "<<T->max<<"  ";
    if (T->p!=NULL)
    cout<<"parent = "<<T->p->low<<"  ";
    else cout<<"THE ROOT"<<"  ";
    if (T->left!=NULL)
    cout<<"left = "<<T->left->low<<"  ";
    if (T->right!=NULL)
    cout<<"right = "<<T->right->low<<"  ";
    cout<<endl;
}

void In_Order(INTT T)
{   //In_Order traversal Interval-Tree
    if (T!=NULL)
    {
        if (T->left!=NULL)
        In_Order(T->left);
        Print_Node(T);
        if (T->right!=NULL)
        In_Order(T->right);
    }
}

void Print_Tree(INTT T)
{
    cout<<"Display the Interval-Tree generated: "<<endl;
	cout<<"----------------------------------------------------"<<endl;
    In_Order(T);
    cout<<"----------------------------------------------------"<<endl;
    cout<<"INPUT: 1.'e' to quit"<<endl;
    cout<<"       2.'i' to insert a new node to the interval tree"<<endl;
    cout<<"       3.'f' to look for the overlapping interval"<<endl;
}

int main()
{
    srand(time(0));    //generate random number
    INTT root = NULL;
    INTT node = NULL;
	int size = 1;
	char op;          //define operations
	int low = 1;
	int high = 1;
	int node_low = 1;
	int node_high = 1;
	//generate a Interval-Tree at beginning
	cout<<"Please input a number to set the size of the Interval-Tree:"<<endl;
	cin>>size;
    int *A = new int[size];
        int *B = new int[size];
    for (int i=0;i<size;i++)
    {
      A[i]=1+rand()%50;   //random numbers as the lows of nodes in the tree
      B[i]=A[i]+1+rand()%50;
      root = Interval_Insert(root, A[i], B[i]);
	}	
    Print_Tree(root);
    
    while(cin>>op)
    switch(op)
    {
      case 'e': case 'E':
          return 0;
          break;
      case 'i': case 'I'://input some new numbers to add new nodes to the existing tree
          cout<<"Input 'low' and 'high' or input '0' to quit "<<endl;
         {
             cin>>node_low;
             if(node_low==0)   //if input "0",then quit
             break;
             else cin>>node_high;
             if(node_high>=node_low)
             {
                root = Interval_Insert(root, node_low, node_high);
                Print_Tree(root);
             }
             else cout<<"Error! High must be bigger than low!" <<endl;
         }
         break;
      case 'f': case 'F':  //look for the overlapping interval
          cout<<"Input 'low' and 'high' or input '0' to quit "<<endl;
         {
             cin>>low;
             if(low==0)   //if input "0",then quit
             break;
             else cin>>high;
             if(high>=low)
             {
      	         node = Interval_Search_Min(root,low,high);
      	         if(node!=NULL)
      	         {
	                cout<<"Interval ["<<low<<","<<high<<"]'s overlapping interval is："<<endl;
                    cout<<"["<<node->low<<","<<node->high<<"]"<<endl;
                 }
	            else
	            cout<<"Not Found!"<<endl;
             }
             else
             cout<<"Error! High must be bigger than low!" <<endl;
         }
           break;
       default:
         break;
    }
     delete [] A;
     delete [] B;
     return 0;
}