Структура данных для нахождения медианы

Это вопрос интервью. Разработайте класс, который хранит целые числа и предоставляет две операции :

void insert(int k)
int getMedian()

. Думаю, я могу использовать BST, чтобы insertзанимало O (logN ), а getMedianзанимало O (logN )(. для getMedianя должен добавить количество левых/правых дочерних элементов для каждого узла ).

Теперь мне интересно, является ли это наиболее эффективным решением и нет ли лучшего.