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

Question

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

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

Вот список для начала:

1. B + деревья: хорошая общая структура индексации по одному ключу
2. K-d дерево: пространственные данные
3. Красно-черное дерево: самобалансирующееся BST; также AVL или Splay Tree
4. Пропустить список: хорошая гибридная структура для произвольного или (псевдо) последовательного доступа
5. Trie: поиск строки по линейному времени

Answer 1

Фильтры Блума

Answer 2

А как же:

• Биноминальные кучи
• Кучи Фибоначчи
• Несвязанные структуры данных набора
• Деревья Splay

Answer 3

Пальцевые деревья

Answer 4

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

Answer 5

Цитировать Мартин Кей :

Суффикс деревья составляют колодец понял, очень элегантно, но к сожалению, плохо оцененные данные структура с потенциально многими приложения (...)

См. Также: Каковы менее известные, но крутые структуры данных?

Answer 6

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

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

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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