Как организовать структуру данных для хранения списка пользователей?

Question

[mjr27]

Пытаюсь найти эффективную структуру для работы с данными.

Условия
В структуре хранятся данные следующего формата:

• id: int
• ts: date/int

Для структуры определены следующие операции:

* update(id, new_ts) - изменить ts у записи с id = id.
* delete(ts_max) - удалить записи с ts < ts_min
* latest(ts_min) - получить список записей (либо id) с ts > ts_min

В более частном случае можно ограничить задачу до следующих условий:
* update - new_ts строго возрастает и гарантированно больше любого значения ts в структуре:
* delete - отсутствует

Количество операций update и latest имеет будет иметь примерно один порядок, так что пренебречь ни одной не получается.

А теперь Вопрос:
Не могу придумать, как бы по всем операциям одновременно уложиться в разумное время. Разумным считается < O(N).

Не исключаю, что просто туплю - и поэтому буду рад не только совету, но и критике.

Язык - если вдруг это важно, питон.

Answer 1

[Виталий]

Для ts делаете бинарное дерево, для id - словарь. В дереве листья могут быть ссылками на объекты в словаре или наоборот, неважно.

В таком случае по id - операция будет линейной, по дереву - log(n)

Answer 2

[mjr27]

В частном случае вроде как получилось свести к варианту "двусвязный список + словарь".
В общем случае вопрос остается открытым.

UPD: Немного опоздал. @xytop , спасибо.