Finding median weights in all paths of an AVL tree with weighted nodes I need some help with proving the complexity of the following problem
(I'm new here, so please excuse my "newbie-ness")

Given: an AVL tree with keys: $1,2,..,n$, such that each node $i$ in the tree has the parameter $w_i$ (which is an integer)

The task: To make an algorithm which returns an array of size $n$ such that  in the cell $i$ there is the median value of all the $w_i$ of all the nodes from the root of the AVL to the node $i$.

Running time: $O(n\log\log n)$

My solution:


For each node among the $n$ nodes in the AVL, I build a separate AVL containing the $O(\log n)$ nodes(because the depth of each node is $O(\log n)$) on the path to it from the root.
Each insertion to an AVL takes $O(\log n)$ ($n$ = number of nodes), but number of nodes here is $O(\log n)$, therefore, each insertion takes $O(\log\log n)$, and since there are $n$ nodes, then building the $n$ AVLs takes $O(n\log\log n)$
Finding the median for each AVL takes $O(\log n)$ (using Select) since there are $O(\log n)$ values in the tree. Then, we put in the output array at the cell $i$ the median value which we just found.


Thus, building each AVL and finding the median, is done in $O(\log(n) + \log\log n)  = O(\log n)$.

My Question:
I'm uncertain about step 2 in the described algorithm above: does building the $n$ AVL trees takes actually $O(n\log\log n)$ running time?
Your main AVL tree has $n$ nodes. On each you build a small AVL tree with a nomber of nodes bounded by $\log n$, so that the insertion of each node on the small AVL tree has a cost $\log\log n$ steps. Overall that makes $O(n\log n\log\log n)$ steps, not $O(n\log\log n)$ as stated in your step 2.