Проект:Математика/Списки/Список структур данных

Это — список структур данных, сгруппированный по категориям.

Линейные структуры данных (Linear data structures)

• Список (List)
  • Массив (Array)
    • Битовая карта (Bitmap)
      • Изображения (Images)
      • Поля высот (Heightfields)
      • Фильтр Блума (Bloom filter)
    • Параллельный массив (Parallel array)
    • Дерево Фенвика
    • Разреженная матрица
  • Связный список (Linked list)
    • Список с пропусками (Skip list)
    • Развёрнутый связный список (Unrolled linked list)
    • XOR-связный список (Xor linked list)
  • V-список (VList)
  • Кольцевой буфер (Circular buffer)
• Ассоциативный массив (Associative array a.k.a. dictionary or map) — также известен как словарь или карта
• Хеш-таблица (Hash table)
  • Двоичное дерево Меркла (дерево хешей) [1]
  • Префиксное дерево, то же что и нагруженное дерево (Trie) [2][3]
    • Суффиксное дерево (Suffix tree)
    • Базисное дерево, тоже, что и основное дерево или дерево остатков (radix tree)
    • Патриция (Patricia trie) [4]
    • Префиксное дерево Меркла (Merkle Patricia tree)[5]
    • Сжатое нагруженное дерево[6]
• Стек (Stack a.k.a. LIFO Last in, first out) — также известен как ЛИФО
• Очередь (Queue a.k.a. FIFO First in, first out) — также известен как ФИФО
  • Очередь с приоритетом (Priority queue), одна из реализаций -- Двоичная куча, см. ниже
• Дек (Deque) — двусвязная очередь
• Буферное окно (Buffer gap)

Граф (Graph)

• Список рёбер (Adjacency list)
• Система непересекающихся множеств (Disjoint-set data structure)
• Представление графа в виде стеков (Graph-structured stack)
• граф сцены (Scene graph)
• Деревья, Дерево
  • BSP-дерево
  • Абстрактное синтаксическое дерево
  • Двоичное дерево
    • Двоичное дерево поиска (Binary search tree)
      • Декартово дерево или дерамида (Treap)
      • Сбалансированное дерево (Self-balancing binary search tree)
        • UB-дерево
        • АВЛ-дерево, (AVL tree)
          • Дерево Фибоначчи
        • B-дерево
          • 2-3-дерево [7]
          • 2-3-4-дерево [8]
          • B+-дерево
          • B*-дерево
        • Красно-чёрное дерево (Red-black tree)
        • Дерево со штрафами (Scapegoat tree)
        • Расширяющееся дерево (Splay tree)
      • Прошитое двоичное дерево (Threaded binary tree)
    • Дерево ван Емде Боаса англ. Van Emde Boas tree (vEB tree) [9]
    • Ориентированный граф
    • Направленный ациклический граф
      • Бинарная диаграмма решений
  • Дерево отрезков
    • Интервальное дерево (Interval tree)
  • Куча (Heap)
    • Двоичная куча (Binary heap)
    • Биномиальная куча (Binomial heap)
    • Фибоначчиева куча (Fibonacci heap)
    • Сливаемая куча (Mergable heap)
    • 2-3-куча англ. 2–3 heap
    • Мягкая куча англ. Soft heap
  • Дерево разбора англ. Parse tree
  • Квадродерево (Quadtree) и Октодерево (Octree)
  • Связка англ. Rope (computer science)
  • Сильноветвящееся дерево, многопутевое дерево (M-Way Tree)

Другие структуры данных

• Помеченное объединение (Tagged union)
• Объединение (Union)
• Таблица (Table)

См. также

• Список алгоритмов
• Список классов сложности, Класс сложности
• Проект:Математика/Списки/Список основных разделов теории алгоритмов
• Проект:Математика/Списки/Список терминов, относящихся к алгоритмам и структурам данных