Структура данных не-BTree, где вставки выполняются отсортированным образом, но позже я могу удалять объекты из случайных мест

Question

Я хочу найти объект с O (logN), а также удалить с помощью O (log N) - но не стоит переходить к реализации сбалансированного дерева.

Есть идеи для этого?

Answer 1

Дерево Фенвика

Answer 2

Да, используйте список пропусков.Это вероятностная структура данных с логарифмической вставкой / поиском / удалением, но без сложного кода баланса деревьев.

Answer 3

B-дерево