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