0

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
0

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.

Your English is pretty good.

0

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.

Your English is pretty good.

But Pi isn't an ordered set...
If node V is the left son of node U, it doesn't mean that the weight of U is greater then the weight of V...It only means that U has greater number (key) then V.

0

But Pi isn't an ordered set...

You can write your algorithm however you want. You get to decide whether it's an ordered set or not.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.