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
  • 99 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Saschakil

Dani AI

Generated

Short answer: yes — under the usual word-RAM assumptions and because weights are integers, an O(n log log n) solution is achievable. was on the right track about keeping an ordered multiset while walking the tree, and correctly reminds that the ordering must be by weight, not by AVL keys.

Concept sketch: run one depth-first traversal and keep the multiset of current ancestors. At each node record the median of that multiset, then recurse into children; when backing up remove the node just visited. The total number of insert/remove/select operations is Theta(n), so the overall time is n times the per-operation cost of the dynamic order-statistics structure used.

Practical options and tradeoffs:

  • Simple and robust: compress weights to ranks [1..n] and use a Fenwick (BIT) or an order-statistics balanced BST. This yields O(n log n) total time and is easy to implement.
  • To reach O(n log log n): use integer-oriented structures (van Emde Boas tree, y-fast trie, fusion/exponential-search trees) that support insert/delete and k-th selection in O(log log U) (expected or worst-case depending on the structure), where U is the weight universe; compressing to U = O(n) gives O(log log n) per operation. These are more complex and may have significant memory or implementation overhead and rely on word-RAM assumptions.

Implementation notes: confirm whether Pi includes the node itself or not and adjust insert/select order accordingly. If portability and simplicity matter, prefer the Fenwick/BST approach; only use vEB/y-fast/fusion techniques when the asymptotic improvement is required and the integer/universe assumptions hold.

Recommended Answers

All 3 Replies

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.