Ответ 1
Это действительно зависит от вашего определения "недавно". CLRS содержит большое количество структур данных, но опускает многие из структур, которые были разработаны в это время. Например, к этому времени было разработано дерево Ван Эмде Боас, которое обеспечивает чрезвычайно быстрое хранение и поиск целых чисел, но нигде не упоминалось.
Многие современные исследования были посвящены структурам, не учитывающим кэширование, которые представляют собой структуры, которые оптимально используют иерархию памяти при определенных разумных предположениях. Бродал - один из исследователей в этой области, который создал много превосходных структур такого рода.
Чисто функциональные структуры данных, которые могут использоваться в функциональных языках (или на императивных языках для гарантии настойчивости), также являются активной темой исследований. Например, работа Криса Окасаки в этой области привела к разработке новых деревьев и очередей приоритетов, например.
Распределенные структуры данных имеют большой импорт в эти дни. Google BigTable - отличный пример. Аналогично, параллельные или блокированные структуры данных нашли свой путь во многих языках программирования (см., Например, Java ConcurrentHashMap или CopyOnWriteArrayList).
Структуры данных, основанные на амортизации, упоминаются тангенциально в CLRS, которая фокусируется на куче Фибоначчи. Тем не менее, структуры дерева переходов и косых куч, также разработанные примерно в одно и то же время, не упоминаются, хотя сегодня они имеют большой импорт.
Вероятностные структуры, такие как treap и skip list, обладали большой исследовательской деятельностью и являются прекрасным местом для изучения. В связанном вене мощные хеш-таблицы, такие как хеш-таблица кукушки или динамические идеальные хеш-таблицы, безусловно, заслуживают внимания.
Структуры данных для вычислительной геометрии в последние годы были в центре внимания, хотя, к сожалению, я не знаю о них, достаточно хорошо, чтобы предлагать какие-либо конкретные структуры.
Структуры данных для обработки строк, а именно дерева суффиксов, чрезвычайно важны для биокомпьютинга и веб-поиска. Я не думаю, что CLRS даже упоминает их существование. Вы должны обязательно изучить их, хотя, поскольку они несут ответственность за большую часть новой работы в геномике.
Многие исследователи приложили усилия к созданию структур данных, которые используют тот факт, что современные машины могут работать на нескольких битах параллельно. Некоторые структуры, такие как дерево слияния, экспоненциальное дерево или y-fast tree, используют эти свойства для сортировки и поиска в массивах целых чисел быстрее, чем барьеры O (n lg n), введенные в наивной модели сравнения.
Также выполняется большая работа над структурами сводных данных, эскизов и синопсисов, которые пытаются дать ответы на вопросы о наборе данных, не сохраняя явно весь набор. Экран Count-Min является отличным примером одной из этих структур данных.
Это всего лишь небольшая выборка новых и классных структур. Надеюсь, это хорошая отправная точка!