Оценки снизу на стандартные алгоритмы

1. Сортировка NlogN
2. Дерево Add + Min + Del >= NlogN, N*Add + ViewAll >= NlogN
3. Куча Add + Del >= NlogN, Build + N*ExtractMin >= NlogN
4. Выпуклая оболочка >= NlogN

Операция удаления в любой структуре за ~O(1)

1. Add + Find = Delete
2. Деревья без удаления
3. Куча без удаления, Дейкстра с кучей
4. Граф и удаление ребер. Запросы = AddEdge, DelEdge, Connected?

Splay-Дерево

1. Update
2. Find
3. Add = Find + Update
4. Delete - не нужен (см. выше).
5. Реализация = 3 случая: zig-zig, zig-zag, root
6. Как избавиться от оставшихся трех? getLeft, getRight, isInverse

Язык C++

1. int & operator [] ( int i )
2. Реализация struct Array
3. Битовое сжатие: struct { char a:3; char b:5; }
4. Указатели: int a, b; int *p = &b; p--; *p = 2;
5. Для особых случаев: *(x > 0 ? &a : &b) = 3;

Практика

1. Splay-Tree (с "удалением")
2. Дейкстра с кучей без удаления (сравнить по времени с обычной)