[内容有误] 左偏树页面删除任意结点有误

[llleixx]

请选择：

• 我正在着手修复这个问题

我正在访问这个页面

https://oi.wiki/ds/leftist-tree/

我发现页面有这样的问题

其中删除任意结点文章给的代码如下：

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);
  t[rs(x) = merge(rs(x), y)].fa = x;
  pushup(x);
  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);
  }
}

但从底层自上而下地 pushup 时，之前地 fa 都没有改变，也就意味着每次从下而上都会经过不同的路径，复杂度会卡成 $O(log^{2}n)$，而且可能还会错误地更新不该更新的结点。

建议改成用 _merge , merge 和 correct 函数实现。其中原来 merge 函数改为 _merge 函数，并删除 pushup 的调用，现在的 merge 调用 _merge 得到根节点，再调用 correct 函数更新 d。

[welcome]

感谢你对 OI Wiki 的关注！记得在 Issue 中表达清楚自己的意思哦～

[llleixx]

而且删除任意结点应该专门写一个函数 del ，在里面维护一下 merge 后的“根”结点的父亲。

[HeRaNO]

ref: https://en.wikipedia.org/wiki/Leftist_tree#Deletion_of_an_arbitrary_element_from_a_Min_HBLT

Leftist tree - Wikipedia

[llleixx]

ref: https://en.wikipedia.org/wiki/Leftist_tree#Deletion_of_an_arbitrary_element_from_a_Min_HBLT

Leftist tree - Wikipedia

咦，学长。

这样写 pushup 不会有问题吗，递归到最底层，最底层又开始向上递归 pushup，但此时 rs(x) = merge(rs(x), y) 还没有执行，也就是说，上面的结点的右儿子还没有更新，当当层的 pushup 结束完后，才会正确更新上层的右儿子。也就是说会出现错误更新的情况，复杂度也不能保证。

应该写个 del 函数，在 del 函数中调用可以维护子孙结点的 merge 函数，然后再调用 pushup 函数。

[HeRaNO]

ref: https://en.wikipedia.org/wiki/Leftist_tree#Deletion_of_an_arbitrary_element_from_a_Min_HBLT

Leftist tree - Wikipedia

咦，学长。

这样写 pushup 不会有问题吗，递归到最底层，最底层又开始向上递归 pushup，但此时 rs(x) = merge(rs(x), y) 还没有执行，也就是说，上面的结点的右儿子还没有更新，当当层的 pushup 结束完后，才会正确更新上层的右儿子。也就是说会出现错误更新的情况，复杂度也不能保证。

应该写个 del 函数，在 del 函数中调用可以维护子孙结点的 merge 函数，然后再调用 pushup 函数。

我只是补一个 reference，左偏树页面下的评论貌似也有这个问题，可以看一下

Leftist tree - Wikipedia