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

Question

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

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

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

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

Answer 1

R-Tree

Answer 2

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

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

Answer 3

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

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

Answer 4

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