BBYR Achieve
返回信息流
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #99176同步于 2020/8/5
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖

【算法】求一个高效合并两颗AVL的算法？

player1111
2020/8/5镜像同步14 回复
求一个高效合并两颗AVL的算法？
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
Wizmann机器人#1 · 2020/8/6
如果让用额外内存。可以O(n)。 （看懂的请点赞）
player1111机器人#2 · 2020/8/6
是不是把他按顺序读出来，然后在重新建立 【 在 Wizmann (Wizmann) 的大作中提到: 】 : 如果让用额外内存。可以O(n)。 : （看懂的请点赞）
Wizmann机器人#3 · 2020/8/6
【 在 player1111 的大作中提到: 】 : 是不是把他按顺序读出来，然后在重新建立 多么顺滑的思路。
wenxiao机器人#4 · 2020/8/6
如果这两颗AVL树互相没有特征的话，想不到比较好的优化方法[ema1]
player1111机器人#5 · 2020/8/7
那大佬说的是啥？ 【 在 Wizmann (Wizmann) 的大作中提到: 】 : 多么顺滑的思路。
player1111机器人#6 · 2020/8/7
维基百科英文版有求解方法，但我没看懂 【 在 wenxiao (wenxiao) 的大作中提到: 】 : 如果这两颗AVL树互相没有特征的话，想不到比较好的优化方法[ema1]
Wizmann机器人#7 · 2020/8/7
就是合并到一块新建的连续内存里啊。 然后这段内存就可以看做一棵平衡树（ 【 在 player1111 的大作中提到: 】 : 那大佬说的是啥？
nuanyangyang机器人#8 · 2020/8/9
不让用额外内存也行。O(n)归并成单向链表，然后，你懂的。 【 在 Wizmann 的大作中提到: 】 : 如果让用额外内存。可以O(n)。 : （看懂的请点赞）
SCSsong机器人#9 · 2020/8/10
链表再转换成 AVL 是不是得 O(nlgn)? 【 在 nuanyangyang 的大作中提到: 】 : 不让用额外内存也行。O(n)归并成单向链表，然后，你懂的。 :