19

Все знают про массивы, связные списки, стэки, очереди, хэш таблицы, простые двоичные деревья. Как насчет того чтобы привести хороший, годный пример чего-нибудь более продвинутого вроде фильтра Блума или B-дерева?

4
  • 3
    Фильтры блума повсеместно используются в спеллчекерах, идеи, заложенные в B и B+ деревьях хорошо распространяются на структуры данных для spatial decomposition типа R-trees, R*-trees, PR-trees, .... А насколько годный пример вы хотите услышать? 9 окт 2012 в 10:13
  • @Котик_хочет_кушать Чем больше разных структур тем лучше. Заниматься подробным описанием каждой в треде очень долго. Можно еще дать небольшое указание где применяется, как вы сделали с предыдущим двумя. Еще можно вставить картинку/пруфлинк, чтобы было понятнее.
    – igumnov
    9 окт 2012 в 10:31
  • А вам зачем это?
    – user6550
    9 окт 2012 в 11:01
  • 4
    @klopp Дабы не упустить возможности создать полезный тред, которого здесь еще нет.
    – igumnov
    9 окт 2012 в 11:07

4 ответа 4

7

Динамический массив размером до 2^32 элементов с временем вставки O(1).

По сути структура MMU с динамическим выделением сегментов данных и блоков оглавления нижнего уровня. Оглавление всегда 2 уровня.

Года полтора назад здесь был вопрос Как реализовать динамический массив? в ходе ответа (скорее спора о возможности операций с такой структурой за время O(1)) появилась такая структура данных. Там и программка есть.

Применение неизвестно.

2
  • Собственно, если я правильно понял, то dyna_xyz - это более низкоуровневая вариация на тему std::deque. 9 окт 2012 в 15:19
  • Вполне может быть. Никогда не смотрел код std::...
    – avp
    9 окт 2012 в 15:20
4

Красно-черное дерево, применяется в Java-коллекциях (TreeMap, TreeSet)

1
  • 3
    Есть у меня смутное подозрение, что автор, не знакомый с RB-Tree, не стал бы спрашивать про фильтры Блума :) 9 окт 2012 в 12:27
4

самое экзотическое, что я видел - Дерево ван Эмде Боаса

1
  • На первый взгляд это - всего лишь двухуровневый массив, аналогичный ответу в Как реализовать динамический массив? Причём в ответе - трёхуровневый 12 авг 2013 в 7:56
1

Коллега самостоятельно делал buddy allocator - вот это было прикольно, хотя это - и не совсем структура данных. Насколько я помню, чтобы сэкономить память, он на незанятых кусках памяти хранил информацию о соседних занятых. И линковал их в списки. А для фрагментов по 4 и 8 байт он делал ещё как-то по-особенному. Потому что первым способом на них потребовалось бы слишком много накладных расходов :)

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.