算法基础习题—内存分配(区间树实现)

算法基础习题—内存分配(区间树实现)

C语言中需要申请一块连续的内存时需要使用malloc等函数。如果分配成功则返回指向被分配内存的指针(此存储区中的初始值不确定)，否则返回空指针NULL。现在小明决定实现一个类似malloc的内存分配系统，具体来说，他需要连续处理若干申请内存的请求，这个请求用一个闭区间$[a_i..b_i]$来表示。当这个区间和当前已被申请的内存产生重叠时，则返回内存分配失败的信息。否则返回内存分配成功，并将该区间标记为已被占用。假设初始状态下内存均未被占用，管理的内存地址范围为$0-1GB（0-2^{30}）$。

输入数据共$n+1$行。第一行一个整数$n$表示共需要处理$n$次内存分配。然后是$n$行数据，每行的格式为$a_i{b}_i$​表示申请区间为$[a_i,b_i]$
数据规模：$n\le 1,000,000;0<a_i\le b_i\le 2^{30}$

输出共n行。 对于每行内存分配的申请，若申请成功则输出一行0，若申请失败则输出一行-1

区间树查找，插入的时间复杂度都为$\lg n$,所以不会超时

#include
#define BLACK 0
#define RED 1
#define ll long long int
using namespace std;
const int N = 1e6;
int n;
typedef struct interval{
	ll low;
	ll high;
	}interval;
interval arr[N];//区间数组
typedef struct Node{
	ll key;
	bool color;
	Node *parent;
	Node *left;
	Node *right;
 
	interval inte;  //区间信息
	ll max;        //子树中端点最大值
 
	}Node;
 
typedef struct IntervalTree{
	Node *root;
	}IntervalTree;
 
//NIL结点
interval Nil_interval={-1,-1};
Node NILL={-1,BLACK,NULL,NULL,NULL,Nil_interval,-1};
Node *NIL=&NILL;          


Node *Search(IntervalTree *T,interval i)
{//查找结点
	Node *x=T->root;
	while(x!=NIL && (i.high<x->inte.low||i.low>x->inte.high))//a.high < b.low || a.low > b.high
	{ 
		if(x->left !=NIL && x->left->max>= i.low)
			x=x->left;
		else
			x=x->right;
		}
	return x;
}

 
void LeftRotate(IntervalTree *T,Node *x)
{//左旋操作
	Node *y=x->right;    //取x的右孩子
 
	x->right=y->left;       //y的左子树变成x的右子树
	if(y->left!=NIL)
		y->left->parent=x;
 
	y->parent=x->parent;     //连接x的父结点到y
	if(x->parent == NIL)
		T->root=y;
	else if(x==x->parent->left)
		x->parent->left=y;
	else
		x->parent->right=y;
 
	y->left=x;               //x放到y的左子树
	x->parent=y;
	
	//维护最大值信息
	y->max=x->max;
	x->max=max(x->inte.high,max(x->left->max,x->right->max));
	}
 
void RightRotate(IntervalTree *T,Node *x)
{//与左旋类似
	Node *y=x->left;      
	
	x->left=y->right;  
	if(y->right !=NIL)
		y->right->parent=x;
	
	y->parent=x->parent;    
	if(x->parent == NIL)
		T->root=y;
	else if(x == x->parent->left)
		x->parent->left=y;
	else
		x->parent->right=y;
	
	y->right=x;         
	x->parent=y;
 
	
	y->max=x->max;
	x->max=max(x->inte.high,max(x->left->max,x->right->max));
 
	}
void InsertFixup(IntervalTree *T,Node *z)
{
	while(z->parent->color==RED)
	{
		if(z->parent == z->parent->parent->left)    
		{
			Node *y=z->parent->parent->right;   
			if(y->color==RED)
			{  
	
				z->parent->color=BLACK;            
				y->color=BLACK;                    
				z->parent->parent->color=RED;     
				z=z->parent->parent;               
				}
			else
			{
			   	if(z==z->parent->right)
				{ 
				/*这里是第二种情况*/
					z=z->parent;                    
					LeftRotate(T,z);               
				 	}
						/*这里是第三种情况*/
				z->parent->color=BLACK;             
				z->parent->parent->color=RED;      
				RightRotate(T,z->parent->parent);  
		 		} 
		 	}
		else
		{	/*第四种种情况*/
			Node *y=z->parent->parent->left;
			if(y->color==RED)
			{
				z->parent->color==BLACK;
				y->color=BLACK;
				z->parent->parent->color=RED;
				z=z->parent->parent;
		 	 	}
			else
			{
				if(z==z->parent->left)
				{
					z=z->parent;
					RightRotate(T,z);
			 	 	}
				z->parent->color=BLACK;
				z->parent->parent->color=RED;
				LeftRotate(T,z->parent->parent);
			  	} 
			} 
		}   
	T->root->color=BLACK;      //根结点变成黑色
	}
void Insert(IntervalTree *T,interval inte)
{
	Node *z=new Node();
	z->key=inte.low;
	z->max=inte.high;
	z->inte=inte;
	z->color =RED;   
	z->parent=NIL;
	z->left=NIL;
	z->right=NIL;
 
	Node *y=NIL;        //y是x的父结点
	Node *x=T->root;
	while(x != NIL)
	{ 
		x->max=max(x->max,z->max);     //维护最大端点值
		y=x;
		if(z->key < x->key)
			x=x->left;
		else
			x=x->right;
		}   
	z->parent=y;   
	if(y==NIL)
		T->root=z;
	else if(z->key < y->key)
		y->left=z;
	else
		y->right =z;
	InsertFixup(T,z);
	}
 
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%lld %lld",&arr[i].low,&arr[i].high);
		
	IntervalTree *T=new IntervalTree();
	T->root=NIL;
	for(int i=0;i<n;i++)
	{
	    Node *temp=Search(T,arr[i]);
	    if(temp==NIL)
		{
			cout<<0<<endl;
			Insert(T,arr[i]);
		}
		else
    		cout<<-1<<endl;
	}
	return 0;
	}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204