Как сохранить минимальное и максимальное время O (1) в сбалансированном бинарном дереве поиска без использования указателей?

Question

Акциз 3-7 в книге «Руководство по разработке алгоритмов» гласит:

Предположим, у вас есть доступ к сбалансированной структуре данных словаря, которая поддерживает каждую из операций поиска, вставки, удаления, минимума, максимум, преемник и предшественник за время O (log n).Объясните, как изменить операции вставки и удаления, чтобы они по-прежнему занимали O (log n), но теперь минимальное и максимальное время O (1).(Подсказка: мыслите в терминах использования абстрактных словарных операций, вместо того, чтобы копаться с указателями и т. П. .)

Без подсказок я думаю, что этот вопрос довольно прост,

Вот мое решение:

для дерева, я просто поддерживаю указатель min, всегда указывающий на минимум, и другой указатель max, всегда указывающий на максимум.

При вставке x я просто сравниваю min.key с x.key, if min.key > x.key, then min = x;, а также делаю это для max, если это необходимо.

При удалении x, if min==x, then min = successor(x); if max==x, then max = predecessor(x);

Но подсказка говорит, что я не могу гадить по указателям и тому подобное.Мое решение портится с указателями?

Если мы не можем использовать дополнительные очки, как я могу получить O (1) для минимума и максимума?

Спасибо

Answer 1

Вы можете получить время журнала (N) для обновления / удаления и постоянное время для получения минимального / максимального значения, используя Min-Max Heaps

Answer 2

Ваш ответ тот же, что я бы дал - вы не балуетесь с указателями, вы просто сохраняете минимальные / максимальные значения.

Так что просто будьте увереннее:)

Answer 3

Сохраните два значения, максимальное и минимальное.Они должны быть проверены и потенциально обновлены при каждом удалении.Если минимум удаляется, вызовите преемника, обновите минимум и удалите старый элемент.При вставке сравните новый элемент с min / max, если он заменяет одно из обновлений min / max соответственно

Answer 4

Я бы использовал две двоичные кучи: минимальная и максимальная куча. В каждом из них вы храните половину элементов, и таким образом вы можете получить доступ к max и min за O (1) времени. Минимальная куча будет содержать половину с наименьшими элементами, а максимальная куча - половину с большими элементами. Все операции вставки / удаления все равно будут O (log n). При вставке нового элемента просто проверьте, в какую кучу он должен попасть.

Answer 5

Не думаю, что вы можете получить O (1) как для максимума, так и для минимума.

В любом случае, книга хочет, чтобы вы открыли двоичные кучи самостоятельно. Не смотрите на ссылку, если вы хотите сделать это самостоятельно. Учитывайте только эту подсказку: «Корень дерева всегда содержит значение min» (или значение max, если вы хотите, чтобы «максимум» был O (1)).