Сложность динамической хеш-таблицы с использованием дерева AVL
Какова сложность динамического хэширования в худшем случае, когда вместо хеширования цепей в каждом элементе массива таблицы будет дерево AVL?
Если хеш-таблица не была динамической, сложность WC была бы O (logn) для вставки, поиска и удаления. Но как динамическая хеш-таблица повлияет на эти сложности?
Решение
При линейном сцеплении наихудший случай случается, когда (1) все элементы хешируются в одном и том же сегменте, и (2) клиент ищет последний элемент в сегменте.
С деревом AVL часть № 1 остается прежней, но часть № 2 становится лучше, потому что вместо поиска в (несортированном) связанном списке мы теперь ищем в BST с балансировкой по высоте, который является улучшение от линейной сложности до логарифмической сложности.
Другие решения
Других решений пока нет …