I got the following question:
We have an AVL tree with n nodes (numbered from 1 to n).
Each node i contains a weight - wi which is an integer.
Pi is the set of the ancestors of the node i, and w(Pi) is the set of weights of all the nodes in Pi.
I need to find an algorithm which runs in O(nloglogn) time.
The algorithm gets an AVL tree like the one mentioned above and returns an array of size n, where each cell i in the array contains the median of the set W(Pi).
Is it even possible?
(sorry for my lousy English)