Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

fix(ds/leftist-tree.md): 修改左偏树任意节点删除操作 #5547

Merged
merged 12 commits into from May 15, 2024

Conversation

JiZiQian
Copy link
Contributor

  • 我已认真阅读贡献指南 (contributing guidelines) 和社区公约 (code of conduct),并遵循了如何参与页及格式手册页的相应规范。

源代码中实现方法的复杂度有误

Copy link

welcome bot commented Apr 22, 2024

感谢你对 OI Wiki 的关注!记得检查是否遵守了格式规范,听说和项目风格统一的 Pull Request 会更容易被 Merge~

@HeRaNO HeRaNO changed the title Update leftist-tree.md fix(ds/leftist-tree.md): 修改左偏树合并实现,并添加删除操作 Apr 23, 2024
@HeRaNO
Copy link
Collaborator

HeRaNO commented Apr 23, 2024

@JiZiQian

  1. 是不是和 [内容有误] 左偏树页面删除任意结点有误 #5256 有关
  2. preview 一下 netlify/oi-wiki/deploy-preview,格式全乱了

@HeRaNO
Copy link
Collaborator

HeRaNO commented Apr 29, 2024

@llleixx PTAL

@HeRaNO HeRaNO changed the title fix(ds/leftist-tree.md): 修改左偏树合并实现,并添加删除操作 fix(ds/leftist-tree.md): 修改左偏树任意节点删除操作 Apr 29, 2024
Copy link
Contributor

@llleixx llleixx left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

大体思路是对的。

但 erase 函数有个 corner case 没考虑到,如果删除节点是根节点,那没有正确维护根节点的父亲(0)。

然后 erase 函数不需要递归,所以不用特判 !x(96 行)。

erase 函数中的 pushup(y) 应为 pushup(t[y].fa)。

解决:

把 t[y].fa = t[x].fa 从两个 if 和 else if 块中拿出来(100 行和 104 行);删去 96 行;修改 pushup(y) 为 pushup(t[y].fa)。

还有原文档这块的复杂度证明也写得不是很清楚,可以考虑顺带细化一下。

复杂度分为两部分:一部分 merge 递归,前面已证
;另一部分 pushup 递归(也就是原文档的证明),但那块证明的前提是代替删除节点位置的新节点的 dist 最多减少
(尽管比较显然)。

@HeRaNO
Copy link
Collaborator

HeRaNO commented May 8, 2024

@JiZiQian WDYT

24OI-bot
24OI-bot previously approved these changes May 8, 2024
Copy link
Collaborator

@24OI-bot 24OI-bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Lint finished, ready for review :)

@JiZiQian
Copy link
Contributor Author

JiZiQian commented May 10, 2024

大体思路是对的。

但 erase 函数有个 corner case 没考虑到,如果删除节点是根节点,那没有正确维护根节点的父亲(0)。

然后 erase 函数不需要递归,所以不用特判 !x(96 行)。

erase 函数中的 pushup(y) 应为 pushup(t[y].fa)。

解决:

把 t[y].fa = t[x].fa 从两个 if 和 else if 块中拿出来(100 行和 104 行);删去 96 行;修改 pushup(y) 为 pushup(t[y].fa)。

还有原文档这块的复杂度证明也写得不是很清楚,可以考虑顺带细化一下。

复杂度分为两部分:一部分 merge 递归,前面已证 ;另一部分 pushup 递归(也就是原文档的证明),但那块证明的前提是代替删除节点位置的新节点的 dist 最多减少 (尽管比较显然)。

能否说一下怎么细化复杂度证明?是不是要考虑数学归纳?

我太菜了,不会证

24OI-bot
24OI-bot previously approved these changes May 10, 2024
Copy link
Collaborator

@24OI-bot 24OI-bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Lint finished, ready for review :)

24OI-bot
24OI-bot previously approved these changes May 10, 2024
Copy link
Collaborator

@24OI-bot 24OI-bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Lint finished, ready for review :)

24OI-bot
24OI-bot previously approved these changes May 10, 2024
Copy link
Collaborator

@24OI-bot 24OI-bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Lint finished, ready for review :)

@llleixx
Copy link
Contributor

llleixx commented May 10, 2024

@JiZiQian 你最后一次提交格式仍是错误的

image


复杂度证明:

复杂度分为两部分:一部分 merge 递归,前面已证;另一部分 pushup 递归(也就是原文档的证明),但那块证明的前提是代替删除节点位置的新节点的 dist 最多减少 $1$,如此才能保证只有文中提及的两种情况存在。

dist 至多减少 $1$:考虑 merge 过程,每次都会使 $x$$y$ 向下一层,也就是说最极端的情况,就是一直选择左偏树的右节点(dist 最小的结点)向下一层,此时 dist 减少 $1$

24OI-bot
24OI-bot previously approved these changes May 10, 2024
Copy link
Collaborator

@24OI-bot 24OI-bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Lint finished, ready for review :)

@JiZiQian
Copy link
Contributor Author

@JiZiQian 你最后一次提交格式仍是错误的

image

复杂度证明:

复杂度分为两部分:一部分 merge 递归,前面已证;另一部分 pushup 递归(也就是原文档的证明),但那块证明的前提是代替删除节点位置的新节点的 dist 最多减少 1,如此才能保证只有文中提及的两种情况存在。

dist 至多减少 1:考虑 merge 过程,每次都会使 x 或 y 向下一层,也就是说最极端的情况,就是一直选择左偏树的右节点(dist 最小的结点)向下一层,此时 dist 减少 1。

都怪24OI-bot(

我改完了

24OI-bot
24OI-bot previously approved these changes May 10, 2024
Copy link
Collaborator

@24OI-bot 24OI-bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Lint finished, ready for review :)

Copy link
Contributor

@llleixx llleixx left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

应该就没问题了 :)。

docs/ds/leftist-tree.md Outdated Show resolved Hide resolved
docs/ds/leftist-tree.md Outdated Show resolved Hide resolved
docs/ds/leftist-tree.md Outdated Show resolved Hide resolved
Copy link
Contributor

@llleixx llleixx left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@HeRaNO
Copy link
Collaborator

HeRaNO commented May 14, 2024

@JiZiQian 能否在作者处加上 @llleixx ?毕竟他也对这次更新做出了贡献

@JiZiQian
Copy link
Contributor Author

@JiZiQian 能否在作者处加上 @llleixx ?毕竟他也对这次更新做出了贡献

你说得很对,我加上了

@HeRaNO
Copy link
Collaborator

HeRaNO commented May 15, 2024

@24OI-bot lint please

@Tiphereth-A Tiphereth-A merged commit a0ceb96 into OI-wiki:master May 15, 2024
16 checks passed
Copy link

welcome bot commented May 15, 2024

恭喜!你的 Pull Request 首次被 Merge 了! 😄

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

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