a data structures advice

[littlerunaway]

I'm working on a homework assignment and looking for some advice.
my data is workers ID and salary. (different ID can have the same salary).
I'm planning on using AVL trees. I need to be able to do the following:
-search for an ID with log(n) comlexity
-find the max salary, which is still not higher than a number I get as input (if
there are several ID's for that salary I need the highest of the ID's). also with
log(n) complexity.
-find the highest salary with O(1) complexity.

now the issue is that some of the times I need to search for an ID, and on other times I'm searching for a salary (and once I found it I need to search for the highest ID with that salary).

the only way I came up with is 2 AVL trees:
1. with ID as the key and salary as data
2. salary as the key, and the data will be an AVL tree of ID.

but it seems too complex and makes me think there's a simpler option. any thoughts?

[requiem31]

Just use a linked list maintained in order for the salaries. Would be a constant search rate for the highest salary but linear for anything after. Each salary node can correspond to the location of the ids in your avl tree. Sort of like an upside down b star tree in a way