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? 
Finding median weights in all paths of an AVL tree with weighted nodes
algorithm analysis;data structures;binary trees;balanced search trees