//#include "std_lib_facilities.h"
//#include<windows.h>
//#include "fstream"
//using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef unsigned long long ULL;
#define red 0
#define black 1
#define max 600
typedef struct Node{
int color;//0-red 1-black
int size;
int low;
int high;
int maxnum;
Node* left;
Node* right;
Node* p;
}Node_RB;
typedef struct{
Node_RB* root;
int black_height;
int node_num;
Node* NIL;
}*RB_tree;
void PrintError () {
printf ("\n程序运行出错!!!\n");
}
void PrintMenu () {
printf ("===红黑树===\n\n");
printf ("00------exit\n");
printf ("01------创建\n");
printf ("02------中序遍历\n");
printf ("03------查找一组重叠\n");
printf ("04------删除区间\n");
printf ("05------查找全部重叠\n");
printf ("\n请输入所选菜单序号(0-05):");
}
void right_rotate(RB_tree &T, Node_RB* x)
{
Node_RB *y = x->left;
x->left = y->right;
if (y->right != T->NIL)
y->right->p = x;
y->p = x->p;
if (x->p == T->NIL)
T->root = y;
else if (x == x->p->right)
x->p->right = y;
else x->p->left = y;
y->right = x;
x->p = y;
y->size = x->size;
x->size = x->left->size + x->right->size + 1;
}
void make_RB_tree(RB_tree &T)
{
T = (RB_tree)malloc(sizeof(RB_tree));
T->NIL = new Node_RB;
T->NIL->color = black;
T->NIL->left = NULL;
T->NIL->right = NULL;
T->NIL->p = NULL;
T->NIL->low = 0;
T->NIL->high = 0;
T->NIL->maxnum = 0;
T->NIL->size = 0;
T->root = T->NIL;
T->black_height = 0;
T->node_num = 0;
}
Node_RB* make_node(const RB_tree &T,int element1,int element2)
{
Node_RB* node;
node = new Node_RB;
node->low = element1;
node->high = element2;
node->maxnum = element2;
node->color = red;
node->left = T->NIL;
node->right = T->NIL;
node->p = T->NIL;
node->size = 1;
return node;
}
int biggest(int a,int b,int c){
int key=a;
if (b>key)
key=b;
if (c>key)
key=c;
return key;
}
void left_rotate(RB_tree &T,Node_RB* x)
{
Node_RB *y = x->right;
x->right = y->left;
if (y->left != T->NIL)
y->left->p = x;
y->p = x->p;
if (x->p == T->NIL)
T->root = y;
else if (x == x->p->left)
x->p->left = y;
else x->p->right = y;
y->left = x;
x->p = y;
y->size = x->size;
y->maxnum = x->maxnum;
x->size = x->left->size + x->right->size + 1;
x->maxnum=biggest(x->high,x->left->maxnum,x->right->maxnum);
}
void RB_insert_fixup(RB_tree &T,Node_RB* &z)
{
Node_RB* y,*temp;
while (z->p!=T->NIL && z->p->color == red)
{
if (z->p == z->p->p->left)
{
y = z->p->p->right;
if (y->color == red)
{//case 1
z->p->color = black;
y->color = black;
z->p->p->color = red;
z = z->p->p;
}
else
{
if (z == z->p->right)
{
z= z->p;
left_rotate(T, z);
}
z->p->color = black;
z->p->p->color = red;
right_rotate(T, z->p->p);
}
}
else
{
y = z->p->p->left;
if (y->color == red)
{//case 1
z->p->color = black;
y->color = black;
z->p->p->color = red;
z = z->p->p;
}
else
{
if (z == z->p->left)
{
z = z->p;
right_rotate(T, z);
}
z->p->color = black;
z->p->p->color = red;
left_rotate(T, z->p->p);
}
}
T->NIL->color = black;
}
T->root->color = black;
}
void insert_RB(RB_tree &T,int element1,int element2)
{
Node_RB* new_node;
Node_RB* x=T->root, *y=T->NIL;
T->node_num++;
new_node = make_node(T,element1,element2);
while (x != T->NIL)
{
y = x;
x->size += 1;
if (new_node->low < x->low)
x = x->left;
else x = x->right;
}
new_node->p = y;
if (y == T->NIL)
T->root = new_node;
else
if (new_node->low < y->low)
y->left = new_node;
else
y->right = new_node;
RB_insert_fixup(T, new_node);
}
void RB_transplant(RB_tree &T,Node_RB* u,Node_RB* v)
{
u->low = v->low;
}
Node_RB* tree_minimum(const RB_tree T,Node_RB* x)
{
Node_RB* temp = x;
while (temp->left != T->NIL)
temp = temp->left;
return temp;
}
void delete_RB_fixup(RB_tree &T,Node_RB* x)
{
Node_RB * w;
while (x!=T->root&&x->color==black)
{
if (x==x->p->left)
{
w = x->p->right;
if (w->color == red)
{
w->color = black;
x->p->color = red;
left_rotate(T, x->p);
w = x->p->right;
}
if (w->left->color == black && w->right->color == black)
{
w->color = red;
x = x->p;
}
else if (w->right->color == black)
{
w->left->color = black;
w->color = red;
right_rotate(T,w);
w = x->p->right;
}
w->color = x->p->color;
x->p->color = black;
w->right->color = black;
left_rotate(T,x->p);
x = T->root;
}
else
{
w = x->p->left;
if (w->color == red)
{
w->color = black;
x->p->color = red;
right_rotate(T, x->p);
w = x->p->left;
}
if (w->right->color == black && w->left->color == black)
{
w->color = red;
x = x->p;
}
else if (w->left->color == black)
{
w->right->color = black;
w->color = red;
left_rotate(T, w);
w = x->p->left;
}
w->color = x->p->color;
x->p->color = black;
w->left->color = black;
right_rotate(T, x->p);
x = T->root;
}
T->NIL->color = black;
}
x->color = black;
}
void delete_RB(RB_tree &T, Node_RB* z)
{
Node_RB *y,*x;
if (z->left == T->NIL)
{
y = z;
//RB_transplant(T, z, z->right);
}
else if (z->right ==T-> NIL)
{
y = z;
//RB_transplant(T,z,z->left);
}
else
y = tree_minimum(T,z->right);
if(y->left!=T->NIL)
x=y->left;
else
x=y->right;
x->p=y->p;
if(y->p==T->NIL)
T->root=x;
else{
if(y==y->p->left)
y->p->left=x;
else
y->p->right=x;
}
//x = y->right;
///*
//if (y->p == z)
// x ->p = y;
//else {
// RB_transplant(T,y,y->right);
// y->right = z->right;
// y->right->p = y;
//}
//RB_transplant(T,z,y);
//y->left = z->left;
//y->left->p = y;
//y->color = z->color;
//*/
if(y!=z){
z->low = y->low;
z->high= y->high;
z->maxnum=y->maxnum;
}
/*x->p = y->p;
if (y->p == z)
z->right = x;
else y->p->left = x;*/
//while (y != T->NIL)
//{
// y->size--;
// y = y->p;
//}
//tree2dot(T, "debug");
if (y->color == black)
delete_RB_fixup(T,x);
}
//void generate_num(string filename)
//{
// ofstream ost(filename.c_str());
// int a[max],temp;
// if (!ost)error("can't open this file", filename);
// srand((int)time(0));
// for (int i = 0; i < max; i++)
// a[i] = i ;
// for (int i = 0; i < 120; i++)
// {
// int j = rand() % (max-1 - i)+1;
// temp = a[i];
// a[i] = a[i + j];
// a[i + j] = a[i];
// }
// for (int i = 0; i < 120;i++)
// ost << a[i]<<endl;
//}
Node_RB* OS_select(Node_RB* x,int low,int high)
{
if(!(x->low)) return NULL;
int r = x->low;
int s = x->high;
if ((low<=s&&low>=r)||(high<=s&&high>=r))
return x;
else if (low < r)
return OS_select(x->left, low ,high);
else return OS_select(x->right, low ,high);
}
Node_RB* OS_findnum(Node_RB* x,int i,int j)
{
if(!(x->low)) return NULL;
int r = x->low;
int s = x->high;
if (i == r&&j ==s)
return x;
else if (i < r)
return OS_findnum(x->left, i ,j);
else return OS_findnum(x->right, i ,j);
}
//int OS_rank(RB_tree &T,int i,int j)
//{
// Node_RB* x=OS_findnum(T->root,i,j);
// if (!(x)) return -1;
// int r = x->left->size + 1;
// Node_RB* y=x;
// while(y != T->root){
//
// if (y==y->p->right)
// r=r+y->p->left->size+1;
// y=y->p;
// }
// return r;
//}
void delete_element(RB_tree &T,int n1,int n2)
{
Node_RB *node1 = OS_findnum(T->root, n1, n2);
delete_RB(T, node1);
//tree2dot(T, "RB_tree20_delete1");
//tree2dot(T, "RB_tree20_delete2");
}
void InOrder(RB_tree &T,Node* nod){
if (nod->left != T->NIL)
InOrder(T,nod->left);
printf("[%d %d] ",nod->low,nod->high);
i