Лабораторная работа по курсу "Алгоритмы и анализ сложности"

Целью данной работы является сравнение следующих структур данных:

1. AVL Tree (АВЛ дерево)
2. Treap (Декартово дерево)
3. Splay Tree (Косое дерево)
4. RB Tree (Красно-чёрное дерево, не нужно реализовывать, будем использовать std::map)
5. Sorted Array (Отсортированный массив, только для бинарного поиска)

Что измеряется?

1. Время вставки
2. Время удаления
3. Время поиска

Данные:

1. Случайные целые числа
2. Случайные строки/векторы

Вывод должен содержать:

1. График зависимости скорости вставки от количества элементов в дереве
2. График зависимости скорости удаления от количества элементов в дереве
3. График зависимости скорости поиска от количества элементов в дереве

По АВЛ деревьям:

1. wikipedia
2. wikibooks
3. habr
4. neerc.ifmo

По декартовым деревьям:

1. habr 1/3
2. habr 2/3
3. habr 3/3
4. e-maxx
5. wikipedia
6. neerc.ifmo

По сплей деревьям:

1. wikipedia
2. habr
3. neerc.ifmo

Еще немного полезной информации:

1. Конспект лекций по алгоритмам