# 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