数据结构：左偏树

Posted on 2024-02-25 Edited on 2024-09-07 In 数据结构 Views:

左偏树 与 配对堆 一样，是一种 可并堆，具有堆的性质，并且可以快速合并。

左偏树的定义和性质

对于一棵二叉树，我们定义 外节点 为子节点数小于两个的节点，定义一个节点的为其到子树中最近的外节点所经过的边的数量。空节点的为。

Note：有些资料中对的定义是本文中的减，这样定义是因为代码编写时可以省略一些判空流程，但需要注意应预先置空节点的为。本文中所有代码对的定义 均为后者，请注意与行文间定义的差别。

左偏树是一棵二叉树，它不仅具有堆的性质，并且是「左偏」的：每个节点左儿子的都大于等于右儿子的。

因此，左偏树每个节点的都等于其右儿子的加一。

需要注意的是，不是深度，左偏树的深度没有保证，一条向左的链也符合左偏树的定义。

核心操作：合并（merge）

合并两个堆时，由于要满足堆性质，先取值较小（为了方便，本文讨论小根堆）的那个根作为合并后堆的根节点，然后将这个根的左儿子作为合并后堆的左儿子，递归地合并其右儿子与另一个堆，作为合并后的堆的右儿子。为了满足左偏性质，合并后若左儿子的小于右儿子的，就交换两个儿子。

参考代码：

int merge(int x, int y) {
  if (!x || !y) return x | y;  // 若一个堆为空则返回另一个堆
  if (t[x].val > t[y].val) swap(x, y);  // 取值较小的作为根
  t[x].rs = merge(t[x].rs, y);          // 递归合并右儿子与另一个堆
  if (t[t[x].rs].d > t[t[x].ls].d)
    swap(t[x].ls, t[x].rs);   // 若不满足左偏性质则交换左右儿子
  t[x].d = t[t[x].rs].d + 1;  // 更新dist
  return x;
}

由于左偏性质，每递归一层，其中一个堆根节点的就会减小，而一棵有个节点的二叉树，根的不超过，所以合并两个大小分别为和的堆复杂度是。

关于性质的说明：

一棵根的为的二叉树至少有层是满二叉树，那么就至少有个节点。注意这个性质是所有二叉树都具有的，并不是左偏树所特有的。

左偏树还有一种无需交换左右儿子的写法：将较大的儿子视作左儿子，较小的儿子视作右儿子：

int& rs(int x) { return t[x].ch[t[t[x].ch[1]].d < t[t[x].ch[0]].d]; }

int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[x].val < t[y].val) swap(x, y);
  int& rs_ref = rs(x);
  rs_ref = merge(rs_ref, y);
  t[x].d = t[rs(x)].d + 1;
  return x;
}

左偏树的其它操作

插入节点

单个节点也可以视为一个堆，合并即可。

删除根

合并根的左右儿子即可。

删除任意节点

做法

先将左右儿子合并，然后自底向上更新、不满足左偏性质时交换左右儿子，当无需更新时结束递归：

int& rs(int x) { return t[x].ch[t[t[x].ch[1]].d < t[t[x].ch[0]].d]; }

// 有了 pushup，直接 merge 左右儿子就实现了删除节点并保持左偏性质
int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[x].val < t[y].val) swap(x, y);
  int& rs_ref = rs(x);
  rs_ref = merge(rs_ref, y);
  t[rs_ref].fa = x;
  t[x].d = t[rs(x)].d + 1;
  return x;
}

void pushup(int x) {
  if (!x) return;
  if (t[x].d != t[rs(x)].d + 1) {
    t[x].d = t[rs(x)].d + 1;
    pushup(t[x].fa);
  }
}

void erase(int x) {
  int y = merge(t[x].ch[0], t[x].ch[1]);
  t[y].fa = t[x].fa;
  if (t[t[x].fa].ch[0] == x)
    t[t[x].fa].ch[0] = y;
  else if (t[t[x].fa].ch[1] == x)
    t[t[x].fa].ch[1] = y;
  pushup(t[y].fa);
}

复杂度证明

先考虑 merge 的过程，每次都会使或向下一层，也就是说最极端的情况，就是一直选择左偏树的右节点（最小的节点）向下一层，此时减少了。

再考虑 pushup 的过程，我们令当前 pushup 的这个节点为，其父亲为，一个节点的「初始」为它在 pushup 前的。从被删除节点的父亲开始递归，有两种情况：

是的右儿子，此时的初始为的初始加一。
是的左儿子，由于节点的最多减一，因此只有的左右儿子初始相等时（此时左儿子减一会导致左右儿子互换）才会继续递归下去，因此的初始仍然是的初始加一。

所以，我们得到，每递归一层的初始就会加一，因此最多递归层。

整个堆加上/减去一个值、乘上一个正数

其实可以打标记且不改变相对大小的操作都可以。

在根打上标记，删除根/合并堆（访问儿子）时下传标记即可：

int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[x].val > t[y].val) swap(x, y);
  pushdown(x);
  t[x].rs = merge(t[x].rs, y);
  if (t[t[x].rs].d > t[t[x].ls].d) swap(t[x].ls, t[x].rs);
  t[x].d = t[t[x].rs].d + 1;
  return x;
}

int pop(int x) {
  pushdown(x);
  return merge(t[x].ls, t[x].rs);
}

其他可并堆

随机堆

int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[y].val < t[x].val) swap(x, y);
  if (rand() & 1)  // 随机选择是否交换左右子节点
    swap(t[x].ls, t[x].rs);
  t[x].ls = merge(t[x].ls, y);
  return x;
}