Member Avatar for nissan

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
  • 73 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Saschakil
Member Avatar for 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.

Your English is pretty good.

Member Avatar for nissan

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.

Member Avatar for Saschakil

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.