Finding median weights in all paths of an AVL tree with weighted nodes

Question

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?

Answer 1

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.

Answer 2

Maintaining one AVL tree for the whole process is enough, and more efficient.

• Setup another AVL tree T, initially empty.
• Perform DFS on original AVL tree
  • Insert node to T on entering the node,
  • Delete node from T on leaving the node.
  • Find and record the median after inserting each node.

In the DFS process, T actively maintains all nodes along the path from root to current node, similar to the stack (explicitly or implicitly) maintained in DFS.

The size of T is $O(\log n)$ during the whole process, so each insertion/deletion/query cost $O(\log \log n)$. And each node in original AVL is inserted/deleted/queried exactly once. So the overall complexity is $O(n \log \log n)$.

The maintained AVL tree T can be replaced by other running median data structures. A common data structure min heap + max heap, maintaining the 2 halves partitioned by current median, which can report current median in $O(1)$. (insertion/deletion is still $O(\log n)$)