当前位置:编程学习 > C/C++ >>

划分树详解 结合例题hdu4251

用划分树来解决选定区间内的第K大值,其实也就两步!一步是建树,另一步则是查询。

     先说我对建树的理解吧!

    建树的过程很简单:两步就OK了!

   第一步:找到序列的中位数,把大于中位数的扔到中位数的左边,小于中位数的扔到数的右边。这样整个序列就被分成了两个区间。

   第二步:对每个子区间,也分别执行第一步操作,直到序列中只有一个元素为止。

   可以看出,建树是一个递归的过程,与线段树的建树有相似之处。

   划分树的建树需要注意以下几点:

     第一:建树是分层的,所以代码中用的是二维数组tree[20][M]。一般10W级别的数据,20层已经够了。

     第二:建树划分的标准是中位数,所以需要排序。而且只排一次序就OK了,为什么只排一次就OK了,我很久都没明白这一点。其实是这样的:对于任意序列: 划分后,左边的数据永远不会大于右边的数据。那么对左边数据单独排序与整体排序的结果是一样的,所以排一次序就OK了!

     第三:划分树划分好的数据永远在存放在下一层。比如数据:

tree[0][M]=1 5 2 6 3 7 4

排序后为:1 2 3 4 5 6 7

中位数为:4

划分后的结果为:tree[1][M]=1 2 3 4 5 6 7(这组数据有点特殊,划分后来就已经是排好序的了)红黑色字体都仍按原未排顺序排列

(红色表示划分到中位数的左边,黑色表示划分到中位数的右边)

接着划分:tree[2][M]=1 2 3 4 5 6 7

再接着分:tree[3][M]=1 2 3 4 5 6 0

到这里已经分完了,为什么最后是0呢?在第2层(tree[2][M]),7已经分完了,所以不用再分

 第四:划分到最后,实际上已经对序列进行排序了。

     划分的时候还有一点需要处理:如果有多个数据相同怎么办呢?通过一种特殊的处理:尽量使左右两边平均分配相同的数。这个特殊处理是这样的:

    在没分之前,先假设中位数左边的数据suppose都已经分到左边了,所以suppose=mid-left+1;然后如果真的分在左边,即if(tree[level][i]<sorted[mid])

suppose--;suppose就减一!到最后,如果suppos=1,则说明中位数左边的数都小于中位数,如果有等于中位数的,则suppose大于1。

    最后分配的时候,把suppose个数,分到左边就可以了,剩下的分到右边!因为suppose的初值是mid-left+1,这样就能保证中位数左边和右边的数平衡了!

   第五:划分的过程,需要把每层的数据记录:toLeft[20][M]。toLeft[i][j]定义为:第i层[1,j]之间有多

模板:
[cpp] 
#include<stdio.h>  
 
#include<algorithm>  
 
using namespace std;  
 
#define M 100005  
 
int tree[20][M],sorted[M];  
 
int toLeft[20][M];  
 
void build(int level,int left,int right){  
 
if(left==right)return ;  
 
int mid=(left+right)>>1;  
 
int i;  
 
int suppose;//假设在中位数sorted[mid]左边的数都全部小于sorted[mid]  
 
suppose=mid-left+1;  
 
for(i=left;i<=right;i++){  
 
if(tree[level][i]<sorted[mid]){  
 
suppose--;  
 
}  
 
}  
 
//如果suppose==1,则说明数组中值为sorted[mid]只有一个数。比如序列:1 3 4 5 6,sorted[mid]=4  
 
/*如果suppose>1,则说明数组中左半边值为sorted[mid]的不止一个数,为mid-suppose。比如序列:1 4 4 4 6,sorted[mid]=4 
 
*/  
 
int lpos=left,rpos=mid+1;  
 
for(i=left;i<=right;i++){  
 
if(i==left){//这里是预处理,相当与初始化  
 
toLeft[level][i]=0;  
 
}else{  
 
toLeft[level][i]=toLeft[level][i-1];  
 
}  
 
if(tree[level][i]<sorted[mid]){//划分到中位数左边  
 
toLeft[level][i]++;  
 
tree[level+1][lpos++]=tree[level][i];  
 
}else if(tree[level][i]>sorted[mid]){//划分到中位数右边  
 
tree[level+1][rpos++]=tree[level][i];  
 
}else{//这里,suppose大于0的数划分到中位数的左边  
 
if(suppose!=0){//这里的处理太巧妙了!帅气!  
 
suppose--;  
 
toLeft[level][i]++;  
 
tree[level+1][lpos++]=tree[level][i];  
 
}else{//表示  
 
tree[level+1][rpos++]=tree[level][i];  
 
}  
 
}  
 
}  
 
build(level+1,left,mid);  
 
build(level+1,mid+1,right);  
 
}  
 
//在[left,right]数据中查询[qleft,qright]中第k大的数据  
 
int query(int level,int left,int right,int qleft,int qright,int k){  
 
if( qleft==qright)  
 
return tree[level][qleft];  
 
int s;//代表[left,qleft)之间有多个个元素被分到左边  
 
int ss;//[qleft, qright]内将被划分到左子树的元素数目  
 
int mid=(left+right)>>1;  
 
if(left==qleft){  
 
s=0;  
 
ss=toLeft[level][qright];  
 
}else{  
 
s=toLeft[level][qleft-1];  
 
ss=toLeft[level][qright]-s;  
 
}  
 
int newl,newr;  
 
if(k<=ss){//查询左边  
 
newl=left+s;  
 
newr=left+s+ss-1;  
 
return query(level+1,left,mid,newl,newr,k);  
 
}else{//查询右边  
 
newl=mid-left+1+qleft-s;  
 
newr=mid-left+1+qright-s-ss;  
 
return query(level+1,mid+1,right,newl, newr,k - ss);  
 
}  
 
}  
 
int main(){  
 
int n,m;  
 
while(scanf("%d %d",&n,&m)!=EOF) 
 
{  
 
        int i;  
 
        for(i=1;i<=n;i++){  
 
            scanf("%d",&tree[0][i]);  
 
            sorted[i]=tree[0][i];  
 
        }  
 
        sort(sorted+1,sorted+n+1);  
 
        build(0,1,n);  
 
        for(i=0;i<n;i++){  
 
            for(int j=1;j<=n;j++){  
 
                printf("%d ",toLeft[i][j]);  
 
            }  
 
            printf("\n");  
 
        }  
 
     

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,