首页 > 代码库 > 7.18晚1.5hrs
7.18晚1.5hrs
可并堆
左偏树中
dist[x]=dist[rs[x]]+1
合并的时候,把权志较大的根作为根节点,把这棵树右子树和另一棵树合并。
说明白点:(上图描述有点问题)
设x表示根权值较大的左偏树,y表示根权值较小的左偏树,合并的时候把x的根节点当做新的树的根节点,把x左子树当做新的左子树,x的右子树和y合并的树作为新的右子树。最后比较dist,如果新的树的左子树的dist小于右子树的,交换。
int merge(int x,int y)//x y是要合并的左偏树的两个根 返回值是新树的根 { if(!x||!y)return x|y;//一个数|0还是那个数,判断空树 if(v[x]<v[y])swap(x,y);//x是权值大的 y小 rs[x]=merge(rs[x],y);//新的右子树是原来的右子树和y的合并树 if(dist[rs[x]]>dist[ls[x]])swap(rs[x],ls[x]);//根据dist调整 dist[x]=dist[rs[x]]+1;//更新x的dist的值 return x; }
还有...add del
int add(int x) { v[++cnt]=x;//先建一个只有一个节点的树 dist[cnt]=0; root=merge(cnt,root);//然后把这个数合并 } int del() { root=merge(ls[root],rs[root]); //合并一个节点的左儿子和右儿子,就是删除这个点啦... }
7.18晚1.5hrs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。