Create a database for init,insert,delete,median

Question

I need to create a data base that works in this time complexity:

1. Init O(1)

2. Insert O(logn)

3. Delete O(logn)

4. Find Median O(1)

I'm struggling with finding the median in O(1).

I create an empty AVL Tree, and 1., 2. ,3. works like a charm with the needed time complexity. I thought about holding a pointer to the median everytime I input to the tree, but when I delete a node, how can I find the median in logn in the tree? because I believe I can't. It'll take about O(n) time complexity. Which means 3. won't work with O(logn) complexity after updating the pointer to find the new median.

Any ideas?

Answer 1

There are multiple solutions for this problem, based on what you already have:

1. Order Statistics tree, which is a variant of a binary search tree that allows you fast (logarithmic time) access to an element by its order statistic. In your case, you are looking for the ceil(n/2)'th element.
   While this mean you will find median in O(logn), you can easily cache it after each insertion/deletion, and it won't change the complexity of the original operation - which will remain O(logn).

2. Another (probably simpler) approach is to use the following observation:
   After each insertion/deletion of non empty set, the median can do one of the three options:
   a. Stay the same element. Example: 1,2,3 -> 1,2,3,4 - median is still 2,
   b. Move one element to the right. Example: 1,2,3,4 -> 1,2,3,4,5 - median changed from 2 to 3
   c. Move one element to the left. Example: 1,2,3,4,5 -> 1,2,3,4 (same as before, in reverse).

Assuming you can find in logarithimic time the "previous" and "next" elements, it is easy to maintain a pointer to the median with very little extra work required.