Что такое структура данных, которая поддерживает быстрый следующий-более высокий элемент и следующий-более низкий элемент?

Question

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

Answer 1

Любое резьбовое дерево подойдет.

Пальцевые деревья также могут быть адаптированы для удобной обработки итерации.

Answer 2

Я думаю, что почти все древовидные структуры могут быть изменены таким образом, чтобы это работало.

Вы "просто" должны добавить двусвязный список "под" деревом, в котором хранятся фактические элементы. Элементы в дереве тогда только для навигационных вопросов. Обратите внимание, что добавление этого двусвязного списка увеличивает объем работы, выполняемой при вставке и удалении элементов. Асимптотическое время выполнения не изменится (по крайней мере, в большинстве случаев).

Answer 3

Структура

A B + Tree позволяет выполнить O (1) следующую / предыдущую операцию, поскольку все элементы находятся в связанном списке конечных страниц.

Answer 4

Красно-черное дерево позволит вам вставить и удалить за O (log n), но следующий-более высокий / более низкий может занять O (log n).

Вы можете исправить это, еслиразмещение узлов дерева в двусвязном списке.При вставке или удалении вы можете найти следующие верхние / нижние узлы и исправить указатели ссылок.

Существует длинное обсуждение поддержки деревьев с эффективной итерацией в Искусство компьютерного программирования Кнут.