左偏树

左偏树 会让人联想到平衡树 其实毫无关系= =
只不过一个很平衡 一个很不平衡而已~
左偏树其实是可并堆 主要操作是merge(int, int)
传入两个根 把这以这两个为根的子树合并 返回新根

这个数据结构的node类:

1
2
3
4
struct MHnode
{
  int l, r, dis, v;
}

l,r就是左右儿子的指针
v是这个节点的权值
dis就是左偏树的关键 表示从这个点 一直走右儿子 要走多少步能走到头
左偏树就是用这个保持左偏性质

以下是merge程序 这里是大根堆
[/cc lang = “cpp”]
int merge(int a, int b)
{
if (!a) return b;
if (!b) return a; //如果某个点为空 就返回另外一个点
if (t[a].v < t[b].v) swap(a, b); //以a为根 t[a].r = merge(t[a].r, b); //合并a.r和b if (t[t[a].l].dis < t[t[a].r].dis) swap(t[a].l, t[a].r); //如果左边的dis<右边的dis 那么就交换 这样可以保持左偏性质 t[a].dis = t[t[a].r].dis + 1; //更新dis return a; //返回根 } [/cc] 删除只能删除根 就是把根弄掉 然后合并左右子树 插入就是把一个只有一个点的树和原堆合并 合并就是合并了 一个性价比很高的数据结构 虽然他能做的 启发式合并平衡树都能做 但是代码复杂度不是一个级别。。

左偏树》上有2条评论

发表评论