let n，合并的be树的大小为奇数，并假定树上的所有整数都是不同的。将这两个AVL树作为输入，并以O（log（n））的时间找到树的中值。
我已经尝试过，我能得到的最好的时间是O（log²（n））时间。这是通过使用模仿此问题的解决方案算法，而是使用两个排序的数组U-tube: Binary Search : Median of two sorted arrays of different sizes。
有人可以帮我在O（log（n））中找到一个解决方案，如果您提供代码，python将不胜感激！
编辑：每个节点都存储以该节点为根的子树的大小。
更正了我的答案，这可能不是最有效的。
您可以获得O（N + M）的时间复杂度，并且有可能达到O（logN + logM）的时间复杂度，原因很简单：如果要找到两个列表的中位数，则需要O（m + n） ，从O（n）中获得一个列表，然后需要查找avl树的中位数O（logN），然后有意义的是，需要O（logN + logM）来查找两棵AVL树的中位数。我假设您的教授实际上表示O（logN + logM），这将适当地考虑涉及两棵树的迭代的时间复杂性...
对于O（N）时限算法，我们可以执行以下操作1）对两棵树进行有序遍历2）合并O（N + M）中的两个有序列表3）在O（N + M）中重建新的avl树4）按照logN中的单个AVL树所述，计算logN中的中位数函数。
所以O（N + M）不错，但是如果我们可以在O（logN + M）中做到这一点，那就更好了。该解决方案肯定有一些优势，但是对于非常大的数据集，树将拥有数百万个节点，因此线性算法可能无法对其进行裁剪。我相信遵循离散数学和计算机科学的一般对称性是有可能的。
这里有一些关于如何在logN时间内合并两个AVL树的讨论：
Concatenating/Merging/Joining two AVL trees
如果理论上可以做到，那么我们可以根据要求将该算法的时间限制降低到logN。
关于两个列表：我们必须基于随机分区（索引范围从0到两个列表的总和（不包括最后一个数字），形成新的ksorted列表）-将由第一列表和第二列表中的元素组成。比较函数将是相同的，将左边的大小与右边的大小进行比较，如果相等，则分区等于奇数列表的中位数（在两个列表的情况下，两个列表的大小之和列表）。对于偶数情况，我将其保留为实现细节，其中涉及以下内容：1）检测列表具有偶数个元素（对于两个列表，两个列表的长度之和），以及2）查找中心索引处的两个元素使用k阶递归方法，并将它们取平均值以返回输出。 k阶方法看起来与我们为两个数的奇数情况编写的函数非常相似，但会为任何索引进行修改。
1）合并O（n + m）中的两个排序列表2）在O（n + m）中找到两个排序列表的中位数