Hi,

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)

2
Contributors
3
Replies
5
Views
8 Years
Discussion Span
Last Post by Saschakil

It's possible and basically straightforward.

Note that you can find the median of an ordered indexable set of k elements in O(log k) time and of course you can do insertions and removals in O(log k) time. And each Pi could be such a set.

It's possible and basically straightforward.

Note that you can find the median of an ordered indexable set of k elements in O(log k) time and of course you can do insertions and removals in O(log k) time. And each Pi could be such a set.