company’s salaraies tree

A company wishes to construct a data structure to store the salaries of its employees. The data structure should support the operations which are described below. An employee is described by a name and a salary. You may assume no two salaries are the same. You may wish to use more than a single tree.

Insert(e) – Insert employee $ e$ into the data structure. Should run in time $ \mathrm{O}(\log (n))$

Delete(e) – Delete employee $ e$ from the data structure. Should run in time $ \mathrm{O}(\log (n))$

Find(s) – Returns an employee with salary s, which exist in the data structure. If there is no such employee return null. Should run in time $ \mathrm{O}(\log (n))$

LargerSalaries() – Returns a tree, which contains the ceil func $ \left[\frac{n}{2}\right]$ employees who earn the most in the company. Should run in time $ \mathrm{O}(1)$

Smallersalaries() – Returns a tree, which contains the floor func $ \left[\frac{n}{2}\right]$ employees who earn the least in the company. Should run in time $ \mathrm{O}(1)$

For example, if the salaries in the company are 1,10,24,30,87 Largersalaries() should return a tree which contains 30 and $ 87,$ while SmallerSalaries() should return a tree which contains 1,10,24

I should suggest a data structure which fullfil these functions in the desire running time . I thought about using an AVL tree which each node in it has a size field, meaning the number of nodes in his subtrees +1 ; using that I can find the median of the tree and then construct an avl tree of the higher slaries and an avl tree for the lower salaries but when I construct a new higher slaries tree I realised that I need to find the succesor of the median every time and then insert it to the higher salaries tree which each function takes O(log n ) but since we do it for n/2 elements in the tree for the higher salaries and we do it for n/2 elements in the tree for the lower salaries (finding the predesccor and insert it) it will be running time of O(n*logn) and not O(logn) .

hope someone can lead me to a better solution or help me fix my problem