笔试算法题（42）：线段树（区间树，Interval Tree）
议题：线段树（Interval Tree）
分析：
线段树是一种二叉搜索树，将一个大区间划分成单元区间，每个单元区间对应一个叶子节点；内部节点对应部分区间，如对于一个内部节点[a, b]而言，其左子节点表示的区间为[a, (a+b)/2]，其右子节点表示的区间为[1+(a+b)/2, b]；
对于区间长度为N的线段树，由于其单元节点都是[a, a]的叶子节点，所以其叶子节点数为N，并且整棵树为平衡二叉树，所以总节点数为2N-1，树的深度为log(N)+1；
插入操作：将一条线段[a, b]插入到区间长度为[l, r]的线段树root中，如果root不是单元节点，则求得mid=(l+r)/2；（删除和查找操作类似）
如果b<=mid，则将[a, b]插入到root->left子树中；
如果a=b=mid，则将[a, b]插入到root->left子树中，
如果a=mid<b，则将[a, a]插入到root->left子树中，[a+1, b]插入到root->right子树中；
如果a>mid，则将[a, b]插入到root->right子树中；
如果a<mid<b，则将[a, mid]插入到root->left子树，将[mid+1, b]插入到root->right子树中线段树最主要的应用是判定几个给定区间之间的关系，判定某一个区间A是否在若干个目标区间内出现，时间复杂度为O(MlogN)，M为A的区间长度，N为 构建线段树的整个区间长度；但原始的线段树需要表示每一个单元区间，所以空间复杂度较高为2N，优化方案是离散化（Discretization）压缩线 段树区间；但是由于线段树每个节点上需要维护一个int的计数变量（记录其子树被覆盖的次数），所以每次插入或者删除操作都需要O(N)的时间维护线段树 的正确性，可以为每一个节点增加一个延迟标记的delta值（Delay Mark），这个值记录当前节点所在的区间需要进行的修改（但是还没有对其左右子树的节点进行修改），当查询路径需要到其左右子树中时，将这个delta 值传递给其左右子树，而将本节点保存饿delta值去除；
一道利用线段树的题目：给定一个自然数集合，自然数的范围是[0,30000]，现在已知N条线段，每条线段以[a,b]的形式给出，现在有M个数字，要求判断每个数字分别在多少条线段上出现过；
一般解法是将M个数字分别于N条线段比较判断，时间复杂度为O(MN)；可以利用线段树记录N条线段在[0, 30000]范围内出现的次数和位置，然后利用二叉树的O(logN)查找时间判断每个数字最终出现的线段；
首先是按照给定的元素范围构建线段树的框架；如给定[0, 7]，则利用线段树为满二叉树的性质，其节点个数为2N-1=15；基本存储结构为数组，如果当前节点为array[i]，则array[2*i]和 array[2*i+1]分别为左右子节点；节点内拥有一个记录本节点代表的线段出现的次数，初始化为0；时间复杂度为O(logK)，K为给定的区间范 围；
- 然后将给定的N条线段插入到已经构建好的线段树框架中；如给定三条线段：[2,5],[4,6],[0,7]，依次插入则最终成为一棵可用的线段树；时间复杂度为O(NlogK)
- 最后是查询给定的M个点在N条线段出现的次数；如给定数字2，则递归到线段树中的节点[2,2]，并将经过的节点的count值累加起来，最终就是数字2在给定的线段集合内出现的次数；
样例：
/**
* count记录这条线段出现的次数
* */
struct Interval {
int left;
int right;
int count;
}; /**
* 此函数用于创建线段树的基本结构，InterTree是一个元素为Interval类型的指针数组
* 其大小为2*(max-min+1)，也就是满二叉树；
* */
void ConstructIT(int min, int max, Interval** InterTree, int index) {
/**
* 构建当前节点
* index用于索引InterTree中当前元素的位置
* 遵循父节点为i，则左右子节点分别为2*i, 2*i+1
* */
Interval *temp=new Interval();
temp->count=;
temp->left=min;
temp->right=max;
InterTree[index]=temp;
/**
* 如果min和max相等，则说明已经到叶子节点
* */
if(min==max)
return;
/**
* 分别递归创建左右子节点
* */
int middle=(min+max)/;
ConstructIT(min,middle,InterTree,index*);
ConstructIT(middle+,max,InterTree,index*+);
}
/**
* 此函数用于注入线段树的线段标记信息
* */
void InsertInfor(int min, int max, Interval** InterTree, int index) {
/**
* 构建线段树的时候，middle本身属于left子树
* */
int middle=(InterTree[index]->left + InterTree[index]->right)/; if(max<=middle) {
/**
* 插入线段完全在middle左边
* */
InsertInfor(min, max, InterTree, *index);
} else if(min>middle) {
/**
* 插入线段完全在middle右边
* */
InsertInfor(min, max, InterTree, *index+);
} else if(min==InterTree[index]->left &&
max==InterTree[index]->right) {
/**
* 插入线段恰好是节点本身的端点范围，有可能是叶子节点
* */
InterTree[index]->count+=;
return;
} else if(InterTree[index]->left==InterTree[index]->right) {
/**
* 已经到达叶子节点，但是min和max仍旧不等，错误返回
* */
return;
} else {
/**
* middle将待插入的线段分成两段
* */
InsertInfor(min, middle, InterTree, *index);
InsertInfor(middle+, max, InterTree, *index+);
}
}
/**
* 此函数用于检查覆盖区间，注意此时的min和max可能超出
* InterTree的范围
* */
int CheckInterval(int min, int max, Interval** InterTree, int index) {
int middle=(InterTree[index]->left + InterTree[index]->right)/;
if(max<middle) {
return CheckInterval(min, max, InterTree, *index);
} else if(min>middle) {
return CheckInterval(min, max, InterTree, *index+);
} else if(min==InterTree[index]->left &&
max==InterTree[index]->right) {
return InterTree[index]->count;
} else {
return CheckInterval(min, middle, InterTree, *index)+
CheckInterval(middle+, max, InterTree, *index+);
}
} void Crossover(int *first, int lfirst, int *second, int lsecond) {
/**
* 获取first和second数组中各自的最大值与最小值的差值
* 选取差值较小的一个范围作为线段树的构建区间
* 节省空间消耗
* */
int minf=, maxf=,mins=,maxs=;
for(int i=;i<lfirst;i+=) {
if(maxf<first[i])
maxf=first[i];
if(minf>first[i])
minf=first[i];
}
for(int i=;i<lsecond;i+=) {
if(maxs<second[i])
maxs=second[i];
if(mins>second[i])
mins=second[i];
}
int min=minf,max=maxf;
int isFirst=true;
if((max-min)>(maxs-mins)) {
min=mins;
max=maxs;
isFirst=false;
}
/**
* 构建一个数组，数组元素为Interval*类型，
* 数组大小为线段树节点个数，由于线段树是
* 完全二叉树，所以节点数肯定为2N-1，N为区间
* 大小，也为叶节点数
* */
Interval *InterTree[*(max-min+)-];
/**
* 首先构建线段树的基本结构
* */
ConstructIT(min, max, InterTree, );
/**
* 然后将线段树范围大小对应的区间数组元素
* 插入到线段树中，如果区间在线段树之外则
* 需要特殊处理
* */
int *temp=NULL, length=;
int overlapSize=;
if(isFirst) {
for(int i=;i<lfirst;i+=) {
if(first[i]<InterTree[]->left ||
first[i-]>InterTree[]->right)
continue;
else if(first[i]==InterTree[]->left ||
first[i-]==InterTree[]->right)
overlapSize++;
else
InsertInfor(first[i-],first[i], InterTree, );
}
temp=second;
length=lsecond;
} else {
for(int i=;i<lsecond;i+=) {
if(second[i]<InterTree[]->left ||
second[i-]>InterTree[]->right)
continue;
else if(second[i]==InterTree[]->left ||
second[i-]==InterTree[]->right)
overlapSize++;
else
InsertInfor(second[i-],second[i], InterTree, );
}
temp=first;
length=lfirst;
}
/**
* 顺序将temp中的区间元素插入到InterTree中
* */ for(int i=;i<length;i+=) {
length+=CheckInterval(temp[i-],temp[i],InterTree,);
}
}
参考连接：
http://hi.baidu.com/alpc62/blog/item/469edeca0043e382c8176875.html
最新文章
- [转]MyEclipse 里查看jar文件源码
- select2
- Spark读取HDFS文件，文件格式为GB2312，转换为UTF-8
- Visual C++ 设置适合自己的解决方案目录结构
- 使用Spring的Property文件存储测试数据 － 添加测试数据
- ExtJs布局之viewport
- VS2010性能监视工具
- Cassandra1.2文档学习（12）—— hint机制
- 351. Android Unlock Patterns
- Core Data & MagicalRecord
- DDL DML DCL TCL之不同
- Postman使用小技巧
- 目标文件去除header一行开头的#号
- Windows Server 2008 R2 免费使用900天的方法
- poj_3045 贪心
- Mcafee(麦咖啡) 无法升级的解决办法(威流验证)
- 2019.1.22 zigbee test
- tar、7z（7zip）压缩/解压缩指令的使用
- awk正则匹配nginx日志【原创】
- 从CPU/OS到虚拟机和云计算