AVL trees

[vak]

Состряпал реализацию map<string, int> на скорую руку на Си, не без помощи ИИ. Грок неленивый программист, если ему прямо говорить что делать.

• Интерфейс: string_map.h
• Реализация: avlmap.c
• Тесты: avlmap_test.cpp

Выбрано представление в виде AVL деревьев. Они компактнее по памяти и вроде эффективнее красно-чёрных деревьев на всех операциях. Хэш был бы неплох, но вычисление хэш функций на словном процессоре типа БЭСМ-6 неэффективно.

Заодно узнал, что AVL деревья представляют собой наследие советской науки. Изобретены в 1962 году Адельсон-Вельским и Ландисом, на десять лет раньше красно-чёрных деревьев.

Георгий Максимович Адельсон-Вельский стоял у истоков шахматной программы Каисса. В 1992 году эмигрировал в Израиль.

Евгений Михайлович Ландис родом из Харькова. В 1968 году подписал нашумевшее письмо в защиту А. С. Есенина-Вольпина.

Comments

[spamsink]

Хэш-функцию можно выбрать любую, в т. ч. быстро вычисляемую на БЭСМ-6. Она совершенно не обязана быть криптографически стойкой или достигать avalanche. Мучиться с деревьями не имеет смысла.