Cтруктуры данных. Хранение информации.

Рекурсивные структуры данных: общие сведения

Очень доступно объясняется, что такое список и как с ним работать, а также что такое очередь, стек и дек. Даны плюсы и минусы по сравнению с массивом.

Обходы деревьев

Алгоритмы обхода и обработки вершин различными способами (прямой, обратный порядки и т.п), в различном порядке.

Словари - структуры с быстрым поиском/вставкой/удалением.

Слоёные списки (скип-списки)

Просто в реализации и почти так же эффективно, как деревья. Гораздо более быстрое время вставки.

Поиск в бинарных деревьях

На практике не применяется, однако полезно с точки зрения общего образования.

Хеш-таблицы

Лучший выбор, если не нужна сортировка информации, а только быстрый доступ к ней.

Красно-черные деревья

Один из методов балансировки дерева. В результате получаем отсортированную информацию с быстрым хранением и доступом.

Сравнение методов

Подробнее о характеристиках вышеназванных способов организации словарей.

Б, Б+ и Б++ деревья

Предназначены для хранения больших объемов информации на диске. При этом минимизированы переходы по дереву, а значит, и задержки при обращениях к диску.

Перевод статьи 'HATs: Hashed Array Trees'^doc

Эффективный и удобный способ реализации массивов переменной длины. Для языка вроде С++ очень даже неплохо.

StringBTree^pdf

Комбинация Patricia и B-tree. Обладает рядом больших преимуществ и перед тем и перед другим. Подходит для хранения, поиска информации и индексации баз данных как на диске, так и в памяти.

VP-tree^pdf

Структура данных, позволяющая проводить быстрый поиск ближайшего соседа в любых пространствах, причем не обязательно Евклидовой метрики. Построение - O(nlogn), поиск O(logn).

Информацию об использовании различных структур данных в конкретных задачах можно найти также в разделе Олимпиадные задачи: структуры данных.

Архив статей.

AVL trees in C++

Определение, основные теоремы и описание операций. С исходником на С++.

[in English] Список, Очередь, Стек - описание и различные реализации

Описание, реализация в виде массива и с указателями, указано быстродействие операций. Их использование для обхода деревьев. Исходники на Си++.

Suffix Arrays: A New Method of on-line string searches

Структура данных, занимающая в 3-5 раз меньше места, чем suffix tree, однако обеспечивающая почти такую же эффективность точного поиска подстроки в строке.

Вверх по странице, к оглавлению и навигации