Цепочка хеш-таблиц с деревом avl

я хеширую строки... а затем мне приходится сортировать вторые строки в алфавитном порядке. Я должен иметь возможность удалять, вставлять или получать номер позиции в моем отсортированном дереве вторых строк. Итак, например, у меня есть хэш-таблица на основе типа животных (кошка, собака...), и каждое ведро имеет дерево AVL с именами, отсортированными по апфабетическому принципу.

insert("кот","Гарфилд"); вставить("кот","Зоро");

гарфилд и зоро будут иметь одинаковый хеш-ключ, потому что они оба кошки, но гарфилд будет корневым и правым потомком зоро.. поэтому, когда я захочу удалить гарфилда, мне придется снова отсортировать дерево..

Мой вопрос в том, является ли хеш-таблица + дерево avl самым быстрым вариантом? также, как я уже сказал, мне нужно иметь возможность получить имя животного на основе типа (хэш-ключ) плюс индекс.

изменить: это всего лишь пример, все является переменным и вставляется через функцию, поэтому количество видов может быть 1 миллион и имена тоже


algorithm hash data-structures avl-tree
person Dabux    schedule 04.11.2017    source источник
comment
Это полностью зависит от вашего режима использования. Какова относительная частота добавления, удаления и чтения?   -  person Martin Broadhurst    schedule 05.11.2017
comment
Фиксированы ли виды заранее (вы знаете, что это будут кошки, собаки и т. д.) или они изменчивы?   -  person Martin Broadhurst    schedule 05.11.2017
comment
все переменно   -  person Dabux    schedule 05.11.2017
comment
С точки зрения асимптотической сложности времени выполнения вы можете просто удалить часть хеш-таблицы и просто использовать AVL-Tree (в худшем случае в обоих случаях O (n * log n)). Однако, если сравнивать с общими шаблонами использования, первый шаг может сэкономить вам несколько циклов...   -  person Ctx    schedule 05.11.2017
comment
Есть ли особая причина, по которой вам нужно сортировать вторые строки в алфавитном порядке? Это потому, что вы должны вернуть список в алфавитном порядке при запросе?   -  person Jim Mischel    schedule 06.11.2017
comment
так должно быть, потому что так сказал наш профессор :D   -  person Dabux    schedule 11.11.2017

Ответы (1)


arrow_upward
1
arrow_downward

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

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

person Karthik Balaguru    schedule 12.11.2017