О каких сложных структурах данных вы должны были слышать?

Это производный вопрос, но я задаю вопрос структурам данных, которые вам, по крайней мере, нужно знать для их полезности. Однако эти структуры слишком сложно реализовать без какой-либо экспертизы.

Я бы сказал, что хорошая граница между ними - куча - вы должны иметь возможность кодировать кучу, но вам понадобится день. Для этого не подходит BST и т.д. Редактирование: я вижу, что это зависит от того, что вы делаете. Я думаю, было бы здорово иметь список с фразой, суммирующей, почему вы ее используете!

Здесь начинается список:

  • B + деревья: хорошая общая структура индексирования на одном ключе
  • Дерево K-d: пространственные данные
  • Красно-черное дерево: самобалансирующееся BST; также AVL или splay tree
  • Список пропусков: хорошая гибридная структура для случайного или (псевдо) последовательного доступа
  • Trie: поиск по линейной временной строке

Ответы

Ответ 4

Это хорошее начало; существует полный список структур данных на wikipedia, некоторые из них должны быть рассмотрены. Но о том, какие из них вам нужны, это зависит от области, которую вы намереваетесь... делать все, что вы делаете.

Ребята из встроенных систем будут иметь очень разные идеи от веб-парней, которые сильно не согласятся с ребятами из бизнес-логики. Выясните, что вы хотите сделать; языки и платформа также будут влиять на список, который вам нужен.

Ответ 6

деревья Ван Эмде Боас. Я не думаю, что вы "должны" услышать о них, но я считаю, что они интересный пример того, какую сложность вы можете достичь с помощью "бит-трюков", а именно O (log log n), экспоненциально лучше, чем бинарные деревья!

Ответ 8

Близко связанный с деревом B +, о котором вы упомянули: B*-tree. Наряду с балансирующим подходом, известным как подход "танцевального дерева", они составляют основу Reiser4.

Ответ 9

Двоичные схемы принятия решений, в частности схемы двоичного принятия решений с сокращенным порядком (ROBDD). Они многократно заново изобретаются (плохо), когда кто-то решает создать свою собственную систему фильтрации.

Ответ 10

хэширование кукушки - простой и элегантный способ разрешения столкновений хеш-таблиц в ожидаемое постоянное время.

Ответ 11

Детерминированные конечные автоматы (DFA) или конечные автоматы, полезно для выражения многих вещей, таких как базовые лексеры, регулярные выражения, переходы состояний, и т.д.. См. Также связанные направленные ациклические графики слов, которые могут быть полезны для компактного хранения словарей.

Ответ 12

Я бы добавил Hash Tables в список. Они довольно просты в концепции, но могут быть сложными, если вы посмотрите, как реализовать хорошую функцию хеширования и эффективные методы зондирования.

Ответ 13

R-Tree и его варианты, такие как R * -Tree, X-Tree, Pyramid-Tree. Различные варианты M-Tree, такие как Slim-Tree.

Как часто, запрос к дереву очень прост. Там может быть и простая загрузка большого объема (для R-Trees STR часто делает хорошую работу). Трудная часть обычно заключается в поддержании хорошего дерева через обновления.

Ответ 14

Вы можете попробовать:

  • y-fast деревья
  • Приблизительные упорядоченные множества
  • выберите кучу
  • компактные массивы
  • Монолитные списки
  • Краткие списки