关于平衡树学习的一点问题

回复帖子

@SDNetFriend  2021-09-15 10:29 回复

求问,推荐学什么平衡树好

Splay 感觉如果带删除操作的我是不想再碰了……调到心态爆炸

也写过替罪羊,但感觉 Splay 会用到 LCT 上,然后开始纠结

各位一般平衡树都写什么,有什么建议吗

@bigmurmur 2021-09-15 10:49 回复 举报

普通平衡树的话就直接上 FHQ,特别好写

LCT 的话一般直接用splay辅助维护

当然如果会ETT啥的当我没说

@Dreamweaver Wisdom 2021-09-15 11:02 回复 举报

LCT的话用Splay,其他情况下用Treap好点吧

部分平衡树功能用set或vector代替也可以,好写。

@Chen_怡  2021-09-15 11:30 回复 举报

@SDNetFriend FHQ最好理解并且最易上手,$splay$ 可以延伸到 $\text{LCT}$,而且 $\text{FHQ}$ 平衡树的基本都可以做qwq。

@zimujunqwq  2021-09-15 11:42 回复 举报

如果你会除了 treap 之外的任何 self-balancing tree,您就走上了一条错误的道路。

——Um_nik

@Tony2  2021-09-15 12:01 回复 举报

我 treap 就写了一个板子(,其它基础题全部 splay

@jerry3128  2021-09-15 12:21 回复 举报

会 ett 也得去搞 lct ,ett在维护链上的信息太弱了,甚至需要lct辅助。

@ftiasch 2021-09-15 12:33 回复 举报

Splay 带删除有什么难的?难道不是所有平衡树中删除最简单直接的吗?

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。