Редкие, экзотические структуры данных и их применение? [закрыт]

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

Ответы

Ответ 1

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

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

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

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


Ответ 2

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


Ответ 3

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


Ответ 4

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