Finding median weights in all paths of an AVL tree with weighted nodes
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.