Словари

Словари - это структуры данных, которые поддерживают операции поиска, вставки и удаления. Один из наиболее эффективных способов реализации словаря - хеш-таблицы. Как правило, к ключам применяется какая-нибудь простая функция, значения которой доставляют место ключа в словаре; хорошая функция рандомизирует значения ключей, рассеивая их по интервалу [1, N], где N - количество мест в словаре (объем хеш-таблицы). Мы рассмотрим также двоичные и красно-черные деревья. Методы работы с обоими типами деревьев включают приемы, с которыми мы познакомились при изучении бинарного поиска. Наконец, слоёные списки (skip lists) - еще одна иллюстрация пользы применения случайных чисел при построении словарей.

• Хеш-таблицы
• Поиск в бинарных деревьях
• Красно-черные деревья
• Слоёные списки
• Сравнение методов