C структура данных подходит для быстрого поиска и простого добавления / удаления

Question

Как указано в заголовке вопроса, мне нужна структура данных, подходящая для быстрого и эффективного поиска.Структура данных также должна иметь возможность добавлять / удалять элементы в любом месте внутри структуры данных.

В настоящее время я использую связанный список.Но проблема в том, что я должен пройтись по списку, чтобы найти нужный элемент.Общие алгоритмы поиска (бинарный поиск, переходный поиск и ...) не могут напрямую использоваться в связанных списках, так как нет случайного доступа к элементам списка.Сортировка элементов списка, необходимых в этих алгоритмах, также является проблемой.С другой стороны, я не могу использовать массивы, так как трудно добавлять / удалять элементы в / из любого желаемого индекса.

Я искал алгоритмы поиска в связанных списках и пришел к тому, чтобы пропустить списки».Теперь я здесь, чтобы спросить, существует ли лучшая структура данных для моего случая или есть лучший алгоритм поиска для связанных списков.

Answer 1

Я бы использовал дерево двоичного поиска AVL

В качестве примера дерева двоичного поиска вы можете взглянуть на https://www.geeksforgeeks.org/avl-tree-set-1-insertion/ и https://www.geeksforgeeks.org/avl-tree-set-2-deletion/

Это очень подробно, есть код на C и схема.

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