пусть n, размер объединенных be-деревьев нечетен, и предположим, что все целые числа в деревьях различны. Возьмите эти два дерева AVL в качестве входных данных и найдите медиану деревьев за время O(log(n)) .
Я пытался, и лучшее, что я могу получить, это время O(log²(n)) . Для этого используется алгоритм решения, который имитирует этот вопрос, но вместо этого использует два отсортированных массива U-tube: Binary Поиск: Медиана двух отсортированных массивов разного размера.
Может ли кто-нибудь помочь мне найти решение в O (log (n em>)), и если вы предоставите код, python будет очень признателен!
Редактировать: каждый узел хранит размер поддерева с корнем в этом узле.