《算法导论》14.3 区间树

一、引入

1、我们可以把一个区间[t，tr]表示成一个对象i，其中属性i.low=t为低端点(lowendpoint)，属性i.high=t为高端点(high endpoint)。我们称区间i和i’重叠(overlap),如果i∩i’≠B，即如果i. low≤i’.high且i’.low≤i.high。如图14-3所示，任何两个区间i和i’满足区间三分律(interval trichotomy)，即下面三条性质之一成立:

2、区间树支持下面这些操作：
INTERVAL-INSERT(T, x):将包含区间属性int的元素x插人到区间树T中。
INTERVAL-DELETE(T, x):从区间树T中删除元素x。
INTERVAL- SEARCH(T, i): 返回-个指向区间树T中元素x的指针，使x.int与i重叠;
若此元素不存在，则返回T.nil。
3、四步法设计操作

步骤1:基础数据结构
我们选择这样一棵红黑树，其每个结点x包含一个区间属性x.int，且x的关键字为区间的低端点x. int.low。因此，该数据结构按中序遍历列出的就是按低端点的次序排列的各区间。
步骤2:附加信息
每个结点x中除了自身区间信息之外，还包含一个值x.max,它是以x为根的子树中所有区间的端点的最大值。
步骤3:对信息的维护
我们必须验证n个结点的区间树上的插人和删除操作能否在O(lgn)时间内完成。通过给定
区间x. int和结点x的子结点的max值，可以确定x. max值:
x.max = max(x.int.high, x.left.max, x.night.max)
这样，根据定理14.1可知，插入和删除操作的运行时间为O(lgn)。事实上，在一次旋转后，更新max属性只需O(1)的时间。
步骤4:设计新的操作
这里我们仅需要唯一的一个新操作INTERVAL SEARCH(T, i)， 它是用来找出树T中与区间i重叠的那个结点。若树中与i重叠的结点不存在，则下面过程返回指向哨兵T. nil的指针。

INTERVAL-SEARCH(T,i)
x = T.root
while x != T.nil and i does not overlap x.int
	if x.left != T.nil and x.left.max >= i.low
		x = x.left
	else x = x.right
return x
1
2
3
4
5
6
7

#include 
#include 
#include 
using namespace std;
#define SIZE 15 
struct Node
{
	int low;//低端点 
	int high;//高端点 
	int max;
	string color;//颜色 
	Node *pParent;//父结点 
	Node *pLeft;//左孩子 
	Node *pRight;//右孩子 
};
 
class RBT
{
public:
	RBT();
	~RBT();
	void LeftRotate(Node* px);//左旋
	void RightRotate(Node* px);//右旋
	void Insert(Node* pz);//插入
	void InsertFixUp(Node* pz);//插入调整
	void InorderTreeWalk( Node* px );//中序遍历
	Node* GetRoot(){ return this->pT_root; }
	Node* GetNil(){ return this->pT_nil; }
	Node* IntervalSearch( Node* i );//区间树查找 
private:
	Node* pT_nil;
	Node* pT_root;
};
 
RBT::RBT()
{//构造一棵区间树 
	pT_nil = new Node; 
	pT_nil->color = "Black";//颜色设为BLACK 
	pT_nil->max = 0;
	pT_root = pT_nil;
}
RBT::~RBT()
{
	if( pT_nil != NULL )
		delete pT_nil;
}
 
void RBT::LeftRotate(Node *px)
{//左旋 
	Node* py = px->pRight;//用py记录px的右孩子 
	px->pRight = py->pLeft;//px的右孩子是py的左孩子 
	if( py->pLeft != pT_nil )
		py->pLeft->pParent = px;
	py->pParent = px->pParent;//py的父结点为px的父结点 
	if(px->pParent == pT_nil )//下面判断py为父结点的哪个孩子 
		pT_root = py;//根 
	else if( px == px->pParent->pLeft )
		px->pParent->pLeft = py;//左 
	else px->pParent->pRight = py;//右 
	py->pLeft = px;
	px->pParent = py;
	py->max = px->max;
	px->max = max( px->max,max(px->pLeft->max,px->pRight->max) );
}
void RBT::RightRotate(Node *py)
{//右旋 
	Node* px = py->pLeft;
	py->pLeft = px->pRight;
	px->pRight->pParent = py;
	px->pParent = py->pParent;
	if(py->pParent == pT_nil )
		pT_root = px;
	else if( py == py->pParent->pLeft )
		py->pParent->pLeft = px;
	else py->pParent->pRight = px;
	px->pRight = py;
	py->pParent = px;
	px->max = py->max;
	py->max = max( py->max,max(py->pLeft->max,py->pRight->max) );
}
 
void RBT::Insert( Node* pz)
{//插入 
	pz->max = pz->high;
	Node* py = pT_nil;
	Node *px  = pT_root;
	while( px != pT_nil )
	{
		px->max = max( pz->high,px->max );
		py = px;//用py记录px 
		if( pz->low < px->low )
			px = px->pLeft;
		else
			px = px->pRight;
	}
	pz->pParent = py;
	if( py == pT_nil )
		pT_root = pz;
	else if( pz->low < py->low )
		py->pLeft = pz;
	else
		py->pRight = pz;
	pz->pLeft = pT_nil;
	pz->pRight = pT_nil;
	pz->color = "Red";
	InsertFixUp( pz );
}
 
void RBT::InsertFixUp(Node* pz)
{//插入修正 
	Node* py = NULL;
	while( "Red" == pz->pParent->color )
	{
		if(pz->pParent == pz->pParent->pParent->pLeft )
		{
			py = pz->pParent->pParent->pRight;
			if( py->color == "Red" )
			{
				pz->pParent->color = "Black";
				py->color = "Black";
				pz->pParent->pParent->color = "Red";
				pz = pz->pParent->pParent;
			}
			else
			{
				if( pz == pz->pParent->pRight )
				{
					pz = pz->pParent;
					LeftRotate( pz );
				}
				pz->pParent->color = "Black";
				pz->pParent->pParent->color = "Red";
				RightRotate( pz->pParent->pParent );
			}
		}
		else if(pz->pParent == pz->pParent->pParent->pRight )
		{
			py = pz->pParent->pParent->pLeft;
			if( py->color == "Red" )
			{
				pz->pParent->color = "Black";
				py->color = "Black";
				pz->pParent->pParent->color = "Red";
				pz = pz->pParent->pParent;
			}
			else
			{
				if( pz == pz->pParent->pLeft )
				{
					pz = pz->pParent;
					RightRotate( pz );
				}
				pz->pParent->color = "Black";
				pz->pParent->pParent->color = "Red";
				LeftRotate( pz->pParent->pParent );
			}
		}
	}
	pT_root->color = "Black";
}
void RBT::InorderTreeWalk( Node* px )
{//中序遍历 
	if( px != pT_nil )
	{
		InorderTreeWalk( px->pLeft );
		cout << px->low << "-" << px->color << '-' << px->max <<endl;
		InorderTreeWalk( px->pRight );
	}
}
Node* RBT::IntervalSearch( Node* i)
{//区间树查找 
	Node* x = pT_root;查找与i重叠的区间x的过程从以x为根的树根开始  
	while( x != pT_nil && ( x->high < i->low || i->high < x->low ) )
	{//当x指向pT.nil或找到重叠区间时过程结束 
		if( x->pLeft != pT_nil && x->pLeft->max >= i->low )
			x = x->pLeft;//去左区间查找 
		else
			x = x->pRight;//去右区间查找 
	}
	return x;
}
int main()
{
	RBT rbt;
	int a[10][2] = {{6,20},{5,9},{25,36},{3,8},{15,23},{17,30},{26,28},{0,5},{6,12},{19,25}};
	Node* ptemp = new Node[ SIZE ];
	for(int i=0;i<10;i++)
	{
		ptemp[i].low = a[i][0];
		ptemp[i].high = a[i][1];
		rbt.Insert( &ptemp[i] );
	}
 
	rbt.InorderTreeWalk( rbt.GetRoot() );
	cout << endl;
 
	bool bquit = true;
	Node temp;
	while(bquit)
	{
		cout << "输入低端点和高端点: ";
		cin >> temp.low >> temp.high;
		Node* p = rbt.IntervalSearch(&temp);
		if(p != rbt.GetNil() )
			cout << p->low << "-" << p->color << '-' << p->max <<',' << endl;
		else
			cout << "无重叠区间" << endl;
		cout << "1-继续/0-结束): ";
		cin >> bquit;
	}
	delete []ptemp;
	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
205
206
207
208
209
210
211
212
213