假设我有两个AVL树和，我知道他们各自的大小。然而，我不知道是否有重复的节点，或任何其他信息。什么是对他们在新的AVL树合并的最有效方法是什么？原来的树木可以被摧毁。

IIRC这一切的操作都是O（N），所以完全合并也将是O（N）。

如果你再$ P $的AVL树psentation可以有效地在它们之间迭代（例如，使用后指针，延续，懒惰的评价等），你应该能够做到这一点还没有中间的列表。

更新：作为编程语言似乎是C / C ++，你可以暂时滥用的AVL节点estructures是在一个链表节点，稍后再重新使用它们的输出树

更新2 ：@hwlau：这是O（N），我已经使用的Prolog自己的AVL实现可检查它的