algorithm - Search AVL tree in log(n)?

Question

This question was taken from a bigger one preparing for a job interview (Solved the rest of it successfully)

Question: Suggest DataStructure to handle boxes where a box has: special ID, weight and size.

I want to save those boxes in an AVL tree, and being able to solve the following problem:

From all boxes which has a maximum size of v (In other words: size<=v) I want to find the heaviest one.

How can I do this in log(n) where n is the number of total saved boxes?

I know that the solution would be saving some extra data in each node but I'm not sure which data would be helpful (no need to explain how to fix the data in rotation etc)

Example of extra data saved in each node: Id of heaviest box in right sub-tree.

Answer 1

It sounds like you're already on the right track: each node stores its heaviest descendant. The only missing piece is coming up with a set of log(n) nodes such that the target node is the descendant of one of them.

In other words, you need to identify all the subtrees of the AVL tree which consist entirely of nodes whose size is less than (i.e. are to the left of) your size=v node.

Which ones are those? Well, for one thing, the left child of your size=v node, of course. Then, go from that node up to the root. Every ancestor of the size=v node which is a right child, consider its left sibling (and the node itself). The set of subtrees whose roots you examine along the way will be all nodes to the left of the size=v node.

As a simplification, you can combine the upper-bound size search with the search for the target node. Basically, you traverse to the child with the highest maximum-weight descendant, but don't allow traversing to children which would violate the size constraint.

max = null
x = root
while x is not null:
  if x.size <= v:
    if x.weight > max.weight:
      max = x
    x = x.left or x.right, depending on which has a larger maxWeightDescendant
  else:
    x = x.left