algorithm - 找到两棵 AVL 树的中位数？

Question

设n，组合 be 树的大小为奇数，并假设树中的所有整数都是不同的。将这两个 AVL 树作为输入，并在 O(log( n )) 时间内找到树的中位数。

我试过了，我能得到的最好的结果是 O(log²( n )) 时间。这是通过使用一个模拟这个问题的解决方案算法，而是使用两个排序数组U 型管：二分搜索：两个不同大小的排序数组的中值。

有人可以帮我在 O(log( n )) 中找到解决方案，如果您提供代码，python 将不胜感激！

编辑：每个节点存储以该节点为根的子树的大小。

标签： algorithmmedianavl-tree