Структуры данных

[Олександр12]

Доброго дня.

Как написать программу на С #?

Допустим, имеется сбалансированный словарь, который поддерживает операции search, insert, delete, minimum, maximum, successor и predecessor, время исполнения каждой из которых равно О(logn). Как можно модифицировать операции вставки и удаления, чтобы их время исполнения оставалось равным О(logn), но время исполнения операций определения максимума и минимума было О(l). ( Подсказка: думайте в терминах абстрактных словарных операций и не теряйте время на указатели и т. п.).

[Alex11223]

Причем тут программа? Судя по "допустим, имеется" это просто теоретический вопрос.

Ну а если уж вам таки надо навелосипедить свой словарь, то делайте, кто ж мешает. С нуля за вас тут никто не напишет бесплатно.

[Selestis]

Можно кешировать минимум/максимум в поле объекта при операции вставки. Тогда чтение из кэша будет О(1).
При удалении:
если удаляемый ключ является максимумом (прочитали из поля за О(1)), то кладем в кэш его predecessor (вычислили за О(logn)), если является минимумом - то соответственно successor.
Операций на удаление получается в 2 раза больше, потому что само удаление тоже O(logn), но штука в том, что сложность от этого не увеличится.