Основные структуры данных и их реализация

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Разработчику Архитектору Инженеру

Основные структуры данных и их реализация

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

Сначала пробежимся по всем:

Массивы — сплошной блок памяти, очень быстрый доступ по номеру ячейки, но вставка/удаление в середину — всё сдвигать.
Списки — цепочка элементов, где каждый знает следующего; быстрое добавление/удаление, но поиск — полный перебор.
Стек и очередь — это просто правила поведения (LIFO и FIFO), ими делают на массивах или списках.
Хеш-таблица — как картотека: хеш-функция превращает ключ в номер ящичка, почти мгновенный доступ, но при коллизиях (два ключа в один ящик) нужны запасные варианты.
Бинарная куча — дерево, где родитель всегда старше детей (записано компактно в массив), используется для очередей с приоритетом.
Деревья поиска — упорядоченные структуры, где слева меньшие, справа большие; двоичные деревяшки вырождаются в список, поэтому используют самобалансирующиеся (AVL, красно-чёрные) для гарантированного O(log n).
B-деревья — толстые, широкие, оптимизированы под диски и базы данных (один узел = один диск-блок).
Суффиксные массивы — все окончания строки отсортировали, чтобы быстро искать подстроки; экономят память по сравнению с суффиксными деревьями.
Графы хранят либо матрицей (все-со-всеми, O(n²) памяти), либо списками соседей (экономично, когда рёбер мало).
Вероятностные структуры (Bloom Filter, Count-Min Sketch) — жертвуем точностью ради колоссальной экономии памяти и скорости; отвечают «нет — 100%, да — возможно».

В программировании, как правило, вам будут постоянно попадаться именно массивы и списки. Но задачи бывают разные, столкнуться можете с каждым вариантом.

1. Массивы

Массив — это непрерывная последовательность элементов фиксированного типа, размещённая в смежных ячейках оперативной памяти. Эта структура является одной из самых ранних и фундаментальных в информатике, поскольку напрямую отражает особенности адресации памяти в архитектуре фон Неймана.

Буквально:

массив = [элемент1, элемент2, элемент3]

1.1 Статические массивы

Статический массив выделяется в памяти во время компиляции или при входе в область видимости (в зависимости от языка). Его размер фиксирован и не может быть изменён в ходе выполнения программы. Доступ к элементу по индексу осуществляется за константное время O(1), поскольку адрес элемента вычисляется по формуле:

адрес_элемента = базовый_адрес + индекс × размер_элемента

Это свойство делает статические массивы крайне эффективными для задач, требующих быстрого прямого доступа: численные методы, обработка сигналов, линейная алгебра и работа с буферами.

JavaScript:

// Объявление массива фиксированной длины
const colors = ["red", "green", "blue"];

Python:

# Массивы в Python — динамические по умолчанию
numbers = [1, 2, 3, 4, 5]

C#:

// Статический массив в C# с фиксированным размером
int[] values = new int[10];
values[0] = 1;
values[1] = 2;

Однако статические массивы не поддерживают динамический рост. Попытка выйти за пределы выделенной памяти вызывает поведение, неопределённое на уровне языка (в C/C++), либо исключение (в Java, C#, Python). В языках с управляемой памятью (например, C#) такие массивы инкапсулируются в типы, предоставляющие дополнительную безопасность.

1.2 Динамические массивы

Динамические массивы (в C++ — std::vector, в C# — List<T>, в Python — list) имитируют поведение бесконечно расширяемой последовательности, скрывая от программиста механизм реаллокации. Внутренне такая структура поддерживает буфер фиксированного размера. При добавлении элемента, если буфер заполнен, выделяется новый блок памяти большего размера (обычно в 1.5–2 раза больше), и все существующие элементы копируются в него.

Python:

# Добавление элементов происходит автоматически
list_data = []
list_data.append(10)
list_data.append(20)
list_data.append(30)
print(list_data)  # [10, 20, 30]

Java:

// ArrayList в Java — динамическая структура
ArrayList<Integer> dynamicList = new ArrayList<>();
dynamicList.add(5);
dynamicList.add(15);
dynamicList.add(25);
System.out.println(dynamicList);  // [5, 15, 25]

Амортизированная сложность операции добавления в конец составляет O(1), несмотря на то, что отдельные операции могут быть O(n). Выбор коэффициента роста — компромисс между временем копирования и фрагментацией памяти. В C# List<T> использует удвоение ёмкости, в Python — более сложную стратегию, включающую деление с остатком от предыдущего размера, чтобы уменьшить избыточное выделение.

Динамические массивы обеспечивают быстрый прямой доступ и эффективный кэш-локальный обход, но неэффективны при вставке/удалении в середине: такие операции требуют сдвига всех последующих элементов, что даёт O(n).

1.3 Разрежённые массивы

Разрежённый массив — это оптимизация, применяемая тогда, когда большинство индексов не содержит значимых данных. Вместо выделения полного блока памяти хранятся только ненулевые (или непустые) элементы в структуре типа «ключ–значение», где ключ — это индекс. Такой подход широко применяется в линейной алгебре (разрежённые матрицы), моделировании физических систем и задачах с большими диапазонами индексов, где плотность данных мала.

Python:

# Хранение только ненулевых значений
sparse_array = {
    0: 10,
    100: 50,
    1000: 200
}
# Остальные элементы считаются нулями

C#:

// Dictionary как реализация разрежённого массива
Dictionary<int, int> sparseData = new Dictionary<int, int>();
sparseData.Add(0, 10);
sparseData.Add(100, 50);
sparseData.Add(1000, 200);

Реализуется разрежённый массив, как правило, на основе хеш-таблицы или сбалансированного дерева, обеспечивая компромисс между временем доступа и объёмом памяти.

1.4 Зигзагообразные (jagged) массивы

Зигзагообразные массивы — это массивы массивов, где каждый подмассив может иметь независимую длину. В отличие от прямоугольных (многомерных) массивов, выделенных как единый блок памяти, зигзагообразные структуры представляют собой дерево ссылок: корневой массив содержит указатели на другие массивы. Это даёт гибкость в хранении, например, строк разной длины (в обработке текста) или нерегулярных данных (в сетевых протоколах).

Python:

# Массив массивов разной длины
jagged = [
    [1, 2],
    [3, 4, 5],
    [6, 7, 8, 9]
]

C#:

// Целочисленный зигзагообразный массив
int[][] zigzagArray = new int[3][];
zigzagArray[0] = new int[] { 1, 2 };
zigzagArray[1] = new int[] { 3, 4, 5 };
zigzagArray[2] = new int[] { 6, 7, 8, 9 };

В языках вроде C# различие между int[,] (прямоугольный) и int[][] (зигзагообразный) проявляется и в производительности, и в семантике. Прямоугольные массивы имеют лучшее поведение кэширования и меньший оверхед памяти, но менее гибки.

2. Списки

Списки — это линейные структуры данных, где элементы связаны между собой посредством указателей (ссылок). Это позволяет эффективно вставлять и удалять элементы без необходимости перемещения больших объёмов данных.

2.1 Односвязный список

Каждый узел односвязного списка содержит полезные данные и указатель на следующий узел. Последний узел указывает на null. Основные операции:

Вставка в начало: O(1)
Удаление по ссылке на предыдущий: O(1)
Поиск по значению: O(n)
Доступ по индексу: O(n)

Python:

# Узлы связаны друг с другом через указатель next
node1 = {"value": 10, "next": None}
node2 = {"value": 20, "next": None}
node3 = {"value": 30, "next": None}

node1["next"] = node2
node2["next"] = node3

C#:

// Класс узла односвязного списка
class Node {
    public int Value;
    public Node Next;
    
    public Node(int val) {
        Value = val;
        Next = null;
    }
}

// Создание списка: 1 -> 2 -> 3
Node head = new Node(1);
head.Next = new Node(2);
head.Next.Next = new Node(3);

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

2.2 Двусвязный список

Двусвязный список содержит два указателя в каждом узле: на предыдущий и следующий элементы. Это позволяет обходить список в обоих направлениях и реализовывать операции удаления без знания предыдущего узла. Стандартные реализации (например, LinkedList<T> в .NET или std::list в C++) обычно используют двусвязный вариант.

Python:

# Два указателя — prev и next
node1 = {"value": 10, "prev": None, "next": None}
node2 = {"value": 20, "prev": None, "next": None}
node3 = {"value": 30, "prev": None, "next": None}

node1["next"] = node2
node2["prev"] = node1
node2["next"] = node3
node3["prev"] = node2

C#:

// Структура узла двусвязного списка на C++
struct DoublyNode {
    int value;
    DoublyNode* prev;
    DoublyNode* next;
};

Недостаток — увеличенный объём памяти на узел и снижение эффективности кэширования из-за несмежного размещения.

2.3 Циклические списки

Циклический список — это связный список, в котором последний узел указывает на первый (в односвязном случае) или на первый и последний соответственно (в двусвязном). Такая структура удобна при реализации кольцевых буферов, планировщиков задач или в сценариях, где требуется бесконечное вращение по набору элементов без явной проверки границ.

Python:

# Последний элемент указывает на первый
head = {"value": 10, "next": None}
node2 = {"value": 20, "next": None}
node3 = {"value": 30, "next": None}

head["next"] = node2
node2["next"] = node3
node3["next"] = head  # Цикл замыкается

C#:

// Циклический список
CircularNode first = new CircularNode(10);
CircularNode second = new CircularNode(20);
CircularNode third = new CircularNode(30);

first.Next = second;
second.Next = third;
third.Next = first;  // Замыкание цикла

Важно при работе с циклическими списками избегать бесконечных циклов обхода: условие завершения должно быть логическим, а не основанным на достижении null.

3. Стеки и очереди

Стек и очередь — это абстрактные типы данных (АТД), определяющие интерфейс и поведение. Их реализация может быть основана как на массивах, так и на связных списках. Выбор базовой структуры влияет на производительность, потребление памяти и поведение в граничных условиях.

3.1 Стек (LIFO — Last In, First Out)

Стек поддерживает две основные операции:

push(x) — добавление элемента на вершину стека;
pop() — извлечение и удаление верхнего элемента.

Дополнительно может присутствовать peek() или top() — просмотр верхнего элемента без удаления.

Python:

# Последовательность операций со стеком
stack = []
stack.append(10)   # push
stack.append(20)   # push
stack.append(30)   # push
last = stack.pop() # LIFO — последний элемент извлекается первым
print(last)  # 30

Java:

// Стек в Java
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
int top = stack.pop();  // Извлекает 3

Реализация на динамическом массиве.

Этот подход обеспечивает O(1) амортизированное время для push и pop, отличную кэш-локальность и компактное представление в памяти. Большинство стандартных библиотек (например, Stack<T> в .NET или ArrayDeque в Java как стек) предпочитают именно такую реализацию. Однако при интенсивном росте возможны паузы из-за реаллокации.

Реализация на односвязном списке.

Каждый push создаёт новый узел, указывающий на предыдущий; pop освобождает голову списка. Преимущества — отсутствие реаллокации, гарантированный O(1) без амортизации. Недостатки — фрагментация памяти, плохая кэш-локальность, накладные расходы на узлы.

Инженерные соображения.

Стек часто используется в системах с жёсткими требованиями к предсказуемости (real-time systems). В таких случаях предпочтение отдаётся статическому массиву фиксированного размера, чтобы избежать динамических аллокаций. Переполнение стека в этом случае обрабатывается как критическая ошибка. Пример — стек вызовов в embedded-системах или виртуальных машинах с ограниченной памятью.

3.2 Очередь (FIFO — First In, First Out)

Очередь поддерживает:

enqueue(x) — добавление в конец;
dequeue() — извлечение из начала.

Python:

# Очередь работает как FIFO
queue = []
queue.append(1)  # enqueue
queue.append(2)
queue.append(3)
first = queue.pop(0)  # dequeue — первый элемент
print(first)  # 1

Java:

// Очередь в Java
Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
queue.offer("C");
String first = queue.poll();  // Извлекает A

Реализация на связном списке.

Наиболее прямолинейна: поддерживается указатель на голову (для dequeue) и хвост (для enqueue). Обе операции — O(1). Однако, как и в случае со стеком на списке, страдает эффективность кэширования.

Реализация на массиве: кольцевой буфер (circular buffer).

Используется фиксированный массив и два индекса: head (начало) и tail (конец). При достижении конца массива индексы «зацикливаются» с помощью операции по модулю:

tail = (tail + 1) % capacity;

Такой подход устраняет необходимость перемещения данных при dequeue, обеспечивает O(1) для обеих операций и отличную кэш-локальность. Однако требует заранее известного максимального размера или механизма роста (что усложняет логику, так как при росте элементы нужно копировать в новую область с сохранением порядка).

Динамические очереди на основе двух стеков.

Теоретически возможна реализация очереди через два стека: один для входа, второй — для выхода. При dequeue, если выходной стек пуст, все элементы из входного переносятся в выходной (что инвертирует порядок). Амортизированная сложность остаётся O(1). На практике этот метод редко используется из-за высокой константы и неэффективного использования памяти, но он полезен в функциональных языках, где изменяемые структуры недоступны.

3.3. Дек (двусторонняя очередь)

Расширение очереди, допускающее вставку и удаление с обоих концов. В Java — ArrayDeque, в C++ — std::deque. Реализуется либо как кольцевой буфер с возможностью роста в обе стороны, либо как массив указателей на фиксированные блоки («буфер блоков»), что позволяет избегать частых реаллокаций и сохранять близость к O(1) для всех операций.

Python:

# Использование с обеих сторон
from collections import deque
dq = deque()
dq.append(1)      # справа
dq.appendleft(0)  # слева
rightEnd = dq.pop()       # извлекает 1
leftEnd = dq.popleft()    # извлекает 0

Java:

// Deque в Java
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(10);
Integer left = deque.removeFirst();
Integer right = deque.removeLast();

4. Хеш-таблицы

Хеш-таблица — одна из самых важных структур данных в инженерной практике, обеспечивающая среднее время доступа O(1) для операций вставки, поиска и удаления. Её эффективность зависит от качества хеш-функции, стратегии разрешения коллизий и политики роста.

4.1 Принцип работы

Хеш-таблица отображает ключи в индексы массива («корзины») с помощью хеш-функции h(key). Идеальная хеш-функция равномерно распределяет ключи, минимизируя коллизии — ситуации, когда разные ключи отображаются в одну и ту же ячейку.

4.2 Методы разрешения коллизий

4.2.1 Цепочки (chaining)

Каждая ячейка массива содержит список (или дерево) пар «ключ–значение». При коллизии новый элемент добавляется в список. Преимущества:

Простота реализации;
Устойчивость к плохому распределению хешей;
Поддержка неограниченного числа элементов (теоретически).

Недостатки:

Выделение дополнительных узлов для списка;
Потеря кэш-локальности при обходе цепочки.

В современных реализациях (например, в Java 8+) при превышении порога длины цепочки (обычно 8 элементов) она преобразуется в сбалансированное дерево (красно-чёрное), что снижает асимптотику поиска в худшей ситуации с O(n) до O(log n).

Python:

# Реализация через словарь со списком ключей
hash_table = {}
hash_table.setdefault("key1", []).append("value1")
hash_table.setdefault("key2", []).append("value2")
hash_table["key1"].append("value1_extra")

C#:

// Словарь с цепочками коллизий
Dictionary<string, List<string>> hashTable = new Dictionary<string, List<string>>();
if (!hashTable.ContainsKey("key1"))
    hashTable["key1"] = new List<string>();
hashTable["key1"].Add("value1");
hashTable["key1"].Add("value2");

4.2.2 Открытая адресация (open addressing)

Все элементы хранятся непосредственно в массиве. При коллизии применяется функция пробирования для поиска следующей свободной ячейки. Распространённые стратегии:

Линейное пробирование: h_i(key) = (h(key) + i) mod m;
Квадратичное пробирование: h_i(key) = (h(key) + c1·i + c2·i²) mod m;
Двойное хеширование: h_i(key) = (h1(key) + i·h2(key)) mod m.

Преимущества:

Высокая кэш-локальность (все данные в одном массиве);
Отсутствие дополнительных аллокаций.

Недостатки:

Чувствительность к загрузке (load factor). При α > 0.7 производительность резко падает;
Удаление требует пометки ячеек как «удалённых» (tombstone), чтобы не нарушить цепочку пробирования;
Сложность масштабирования: при росте таблицы требуется полная перестройка.

Python (словари), CPython и Lua используют открытую адресацию с линейным или смешанным пробированием.

Python:

# Таблица с прямым хранением в ячейках
size = 10
table = [None] * size
table[hash("key1")] = "value1"
table[hash("key2")] = "value2"

Java:

// Прямая таблица без связных структур
Object[] table = new Object[10];
table[key.hashCode() % 10] = "value";

4.3 Универсальное хеширование

Чтобы избежать целенаправленных атак, вызывающих коллизии (например, хеш-флуд в веб-серверах), применяется универсальное хеширование: хеш-функция выбирается случайно из семейства функций при инициализации таблицы. Это гарантирует, что даже злонамеренный противник не сможет предсказать распределение ключей без знания внутреннего состояния хешера.

В .NET хеш-коды для строк могут быть рандомизированы (опция DOTNET_SYSTEM_GLOBALIZATION_USE_RANDOMIZED_HASHING), что защищает от DoS-атак через хеш-коллизии.

4.4 Выбор хеш-функции

Хорошая хеш-функция должна быть:

Быстрой (несколько тактов процессора);
Равномерной (минимизация смещения и корреляции);
Нечувствительной к малым изменениям входа (лавинный эффект).

Для целых чисел часто используется тождественное отображение или умножение на большую нечётную константу. Для строк — алгоритмы вроде FNV-1a, MurmurHash, CityHash или SipHash (последний — криптографически устойчивый, применяется в Python и Rust).

5. Бинарные кучи и приоритетные очереди

Приоритетная очередь — это абстрактный тип данных, в котором каждый элемент ассоциирован с приоритетом, и извлечение всегда происходит по элементу с наивысшим (в max-куче) или наинизшим (в min-куче) приоритетом. Наиболее распространённая и эффективная реализация приоритетной очереди — бинарная куча, представленная в виде почти полного двоичного дерева, хранящегося в массиве.

5.1 Структура бинарной кучи

Бинарная куча обладает двумя ключевыми свойствами:

Форма: дерево является почти полным — все уровни, кроме, возможно, последнего, полностью заполнены, а последний уровень заполнен слева направо.
Порядок: в max-куче значение любого узла не меньше значений его потомков; в min-куче — наоборот.

Благодаря свойству почти полноты, куча может быть эффективно представлена в виде одномерного массива без явного хранения указателей. Если корень расположен по индексу 0, то для узла с индексом i:

Левый потомок: 2·i + 1
Правый потомок: 2·i + 2
Родитель: ⌊(i – 1)/2⌋

Это позволяет реализовать кучу с минимальными накладными расходами: один массив, O(1) дополнительной памяти, отличная кэш-локальность.

Python:

# heapify создаёт минимальную кучу
import heapq
heap = [5, 2, 8, 1, 9]
heapq.heapify(heap)
minValue = heapq.heappop(heap)  # извлекает 1

Java:

// PriorityQueue — реализация бинарной кучи
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(5);
minHeap.add(2);
minHeap.add(8);
Integer smallest = minHeap.poll();  // Извлекает 2

5.2 Основные операции

5.2.1 Вставка (`insert`)

Новый элемент добавляется в конец массива (сохраняя свойство формы), затем выполняется просеивание вверх (sift-up): элемент сравнивается с родителем и, если нарушено свойство порядка, меняется местами. Процесс продолжается до корня или до восстановления порядка.
Сложность: O(log n).

5.2.2 Извлечение максимума/минимума (`extract`)

Корневой элемент (экстремум) удаляется и возвращается. На его место перемещается последний элемент массива, после чего выполняется просеивание вниз (sift-down): узел сравнивается с потомками и меняется местами с наибольшим (в max-куче) или наименьшим (в min-куче) из них. Процесс продолжается до листа или до восстановления порядка.
Сложность: O(log n).

5.2.3 Построение кучи из массива (`heapify`)

Наивный подход — последовательная вставка всех элементов — даёт O(n log n). Однако существует линейный алгоритм: начиная с последнего внутреннего узла (индекс ⌊n/2⌋ – 1) и двигаясь к корню, выполняется sift-down.
Сложность: O(n). Это возможно благодаря тому, что большинство узлов находятся в нижних уровнях дерева, где высота мала.

5.3 Инженерные аспекты реализации

5.3.1 Выбор представления

Хотя теоретически куча может быть реализована и на связанных узлах, массивное представление доминирует в практике из-за:

отсутствия аллокаций при каждой операции;
предсказуемого поведения кэша (элементы дерева хранятся последовательно);
простоты вычисления индексов.

5.3.2 Кэш-эффективные варианты: d-арные кучи

Вместо двух потомков у каждого узла допускается d потомков (обычно d = 4 или 8). Это уменьшает высоту дерева, сокращая число операций sift-down при извлечении. Однако увеличивается число сравнений на каждом уровне.
Компромисс выгоден в сценариях, где вставка происходит значительно реже извлечения, например, в алгоритме Дейкстры с плотным графом.
В стандартной библиотеке C++ (std::priority_queue) используется бинарная куча, но библиотеки вроде Intel TBB предлагают d-арные кучи для высоконагруженных систем.

5.3.3 Потокобезопасность

Обычная куча не является потокобезопасной. Для многопоточной среды применяются:

внешняя синхронизация (блокировки);
lock-free реализации на основе CAS-операций (редки из-за сложности);
использование нескольких куч с последующим слиянием (подход в некоторых scheduler’ах ОС).

5.3.4 Применение в алгоритмах

Сортировка кучей (Heapsort): построение кучи + n извлечений → O(n log n), in-place, нестабильная.
Алгоритмы на графах: Дейкстра, Прим — требуют эффективного обновления приоритетов. Стандартная куча не поддерживает decrease-key напрямую; для этого используются бинарные кучи с обратными индексами или фибоначчиевы кучи (в теории).
Планировщики задач: выполнение задач по приоритету (например, в ОС или message queues).

5.4 Ограничения и альтернативы

Стандартная бинарная куча не поддерживает:

эффективный поиск произвольного элемента (O(n));
изменение приоритета существующего элемента без внешнего индекса.

В случаях, где такие операции критичны (например, в интерактивных симуляторах), применяются:

Индексированные кучи: хранят дополнительный массив, сопоставляющий элементы с их позициями в куче;
Балансированные деревья поиска (например, TreeSet в Java): поддерживают все операции за O(log n), включая удаление по ключу и итерацию в порядке сортировки, но с худшей кэш-локальностью и большим оверхедом.

6. Деревья поиска

6.1 Двоичные деревья поиска (BST — Binary Search Tree)

Двоичное дерево поиска — это упорядоченное двоичное дерево, в котором для любого узла выполняется:

все ключи в левом поддереве меньше ключа узла;
все ключи в правом поддереве больше или равны (в зависимости от соглашения).

Это свойство позволяет выполнять поиск, вставку и удаление за время, пропорциональное высоте дерева: O(h).

Python:

# Структура узла дерева
class TreeNode:
    def __init__(self, val):
        self.value = val
        self.left = None
        self.right = None

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)

Проблема несбалансированности

В худшем случае (при вставке отсортированной последовательности) дерево вырождается в связный список: h = n, и все операции становятся O(n). Это делает наивное BST непригодным для production-сценариев без дополнительных мер.

6.2 Самобалансирующиеся деревья

Чтобы гарантировать h = O(log n), применяются стратегии автоматического восстановления баланса после модификаций.

6.2.1 AVL-дерево

Самый ранний вариант сбалансированного дерева (1962). Инвариант: для любого узла разность высот левого и правого поддеревьев («баланс-фактор») не превышает 1 по модулю.

Поддержание баланса достигается через вращения (левые, правые, комбинированные);
После каждой вставки/удаления может потребоваться до O(log n) вращений;
Высота дерева строго ограничена: h < 1.44·log₂(n + 2) – 0.328.

AVL-деревья оптимальны для читающих систем, где поиск значительно чаще модификаций, так как обеспечивают минимально возможную высоту.

6.2.2 Красно-чёрные деревья (Red-Black Tree)

Более «ленивый» подход к балансировке, используемый в std::map (C++), TreeMap (Java), ядре Linux (для планировщика).

Свойства:

Каждый узел либо красный, либо чёрный.
Корень — чёрный.
Все листья (NIL) — чёрные.
Красный узел не может иметь красного родителя.
Любой путь от узла до его листьев содержит одинаковое число чёрных узлов.

Из этого следует: высота h ≤ 2·log₂(n + 1).
Преимущества перед AVL:

меньше вращений при вставке/удалении (в среднем O(1) против O(log n));
лучше подходит для часто изменяемых структур.

Недостаток — дерево может быть на ~30% выше, чем AVL, что немного замедляет поиск.

6.3 Инженерные аспекты

Узлы обычно содержат указатели на родителя, левого и правого потомков, а также служебные поля (цвет в RB-дереве).
Для уменьшения фрагментации памяти в высоконагруженных системах применяется пул аллокаторов.
В языках с GC (Java, C#) такие деревья безопасны, но создают давление на сборщик мусора при частых обновлениях.

7. B-деревья и их варианты

7.1 Мотивация: иерархия памяти

В то время как двоичные деревья оптимизированы под оперативную память, B-деревья разработаны для сред с высокой латентностью доступа, таких как диски (HDD/SSD) или сетевые хранилища. Основная идея: минимизировать количество обращений к медленному устройству, максимизируя полезную нагрузку в каждом блоке.

7.2 Структура B-дерева

B-дерево порядка m — это сбалансированное дерево, в котором:

каждый узел содержит до m – 1 ключей и до m потомков;
все листья находятся на одном уровне;
внутренние узлы хранят ключи-разделители для навигации;
листья содержат фактические данные (в классической версии) или указатели на них.

Пример (B-дерево порядка 4):

        [20|40]
       /   |    \
[5|10|15] [25|30|35] [45|50|55]

Каждый узел соответствует одному дисковому блоку (обычно 4 КБ). Чтение одного узла — одна I/O-операция.

Python:

# Упрощённое представление узлов B-дерева
btree_node_1 = {"keys": [20, 40], "children": [node_a, node_b, node_c]}
node_a = {"keys": [5, 10, 15]}
node_b = {"keys": [25, 30, 35]}
node_c = {"keys": [45, 50, 55]}

C#:

// Структура узла B-дерева
class BTreeNode {
    public int[] Keys;
    public BTreeNode[] Children;
    public int Degree;
    public bool IsLeaf;
}

7.3 B⁺-деревья

Наиболее распространённый вариант в СУБД (PostgreSQL, MySQL InnoDB, Oracle).

Отличия от классического B-дерева:

Все данные хранятся только в листьях;
Листья связаны в двусвязный список, что позволяет эффективно выполнять диапазонные запросы (range scans);
Внутренние узлы содержат только ключи-разделители.

Это даёт два ключевых преимущества:

Повышенная плотность внутренних узлов → меньшая высота → меньше I/O;
Последовательное чтение листьев при диапазонных запросах — критично для аналитических нагрузок.

7.4 Реализация и оптимизации

Размер узла обычно выравнивается по границе страницы ОС (4 КБ);
При вставке, если узел переполнен, он расщепляется на два;
При удалении, если узел становится менее чем наполовину заполнен, выполняется слияние или перераспределение с соседом;
Для уменьшения блокировок в СУБД применяются ленивые (latch-free) алгоритмы, copy-on-write или версионирование (MVCC).

8. Суффиксные структуры

Эти структуры предназначены для эффективной обработки подстрок в фиксированной строке. Применяются в:

биоинформатике (поиск паттернов в ДНК);
полнотекстовом поиске;
сжатии данных (алгоритмы вроде Burrows–Wheeler Transform);
обнаружении плагиата.

8.1 Суффиксный массив (Suffix Array)

Суффиксный массив — это отсортированный массив индексов всех суффиксов строки.

Для строки S = "banana$" (с терминатором $):

Суффиксы: "banana$", "anana$", "nana$", "ana$", "na$", "a$", "$"
Сортировка: "$", "a$", "ana$", "anana$", "banana$", "na$", "nana$"
Суффиксный массив: [6, 5, 3, 1, 0, 4, 2]

Python:

# Суффиксы строки banana$
string_with_terminator = "banana$"
suffixes = [
    "banana$", "anana$", "nana$", "ana$", "na$", "a$", "$"
]
suffixes.sort()
print(suffixes)  # ['$', 'a$', 'ana$', 'anana$', 'banana$', 'na$', 'nana$']

# Индексы отсортированных суффиксов
suffix_array = [6, 5, 3, 1, 0, 4, 2]

Преимущества:

Потребляет 4n–8n байт (в зависимости от типа индекса), что в 3–5 раз меньше, чем суффиксное дерево;
Поддерживает быстрый поиск подстроки за O(m·log n) с помощью бинарного поиска по суффиксам;
С дополнительными структурами (LCP-массивом) можно достичь O(m + log n).

Построение

Наивный метод — сортировка всех суффиксов — O(n² log n). Современные алгоритмы (SA-IS, DC3) строят массив за O(n) времени и O(n) памяти.

8.2 Суффиксное дерево (Suffix Tree)

Суффиксное дерево — это сжатое префиксное дерево (trie), содержащее все суффиксы строки как пути от корня к листьям.

Для той же строки "banana$" дерево будет содержать ветви для каждого уникального префикса суффиксов.

Python:

# Дерево представляется словарём
suffix_tree = {
    'root': {
        '$': {'leaf': '$'},
        'a': {
            'n': {
                'a': {'leaf': 'ana'}
            }
        },
        'n': {
            'a': {
                'n': {'leaf': 'nana'}
            }
        }
    }
}

Свойства:

Построение за O(n) (алгоритм Укконена);
Поиск подстроки за O(m) — оптимально;
Поддержка сложных запросов: самый длинный повторяющийся подстрок, наименьший общий предок (LCA) для LCP и др.

Недостатки:

Высокое потребление памяти: до 20n–40n байт из-за указателей и метаданных;
Сложность реализации.

Поэтому на практике суффиксные массивы почти всегда предпочтительнее, особенно в 64-битных системах, где указатели занимают 8 байт.

8.3 Современные гибриды

FM-индекс (на основе BWT и суффиксного массива) — используется в bwa, bowtie для выравнивания геномов; поддерживает сжатое представление с возможностью поиска.
Wavelet-деревья — позволяют выполнять ранг/селект-запросы, что полезно в сжатых структурах данных.

9. Графовые структуры данных

Граф — это абстракция, состоящая из множества вершин (узлов) и рёбер (связей между ними). В отличие от линейных или древовидных структур, граф допускает произвольную топологию: циклы, множественные рёбра, несвязные компоненты, направленность и взвешенность. Эффективность работы с графами напрямую зависит от выбора представления.

9.1 Матрица смежности (Adjacency Matrix)

Матрица смежности — это двумерный массив A размером n × n, где A[i][j] = 1 (или вес ребра), если существует ребро из вершины i в j, и 0 (или ∞) в противном случае.

Python:

# Матрица 4x4 для графа
adjacency_matrix = [
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0]
]
# adj_matrix[i][j] = 1 означает наличие ребра между вершинами i и j

C#:

// Целочисленная матрица смежности
int[,] matrix = new int[4, 4];
matrix[0, 1] = 1;
matrix[0, 3] = 1;
matrix[1, 0] = 1;
matrix[1, 2] = 1;

Свойства:

Прямой доступ: проверка существования ребра — O(1);
Простота реализации: особенно для плотных графов;
Поддержка взвешенных и мультиграфов через значения ячеек.

Недостатки:

Память: O(n²), что неприемлемо при больших n (например, для соцсети с 1 млрд пользователей — 10¹⁸ ячеек);
Итерация по соседям: O(n), даже если степень вершины мала;
Неэффективна для разреженных графов (где число рёбер m ≪ n²).

Применение:

Алгоритмы, требующие частой проверки рёбер (например, Floyd–Warshall для всех пар кратчайших путей);
Малые графы (до нескольких тысяч вершин);
Теоретические задачи, где важна математическая интерпретация (спектральный анализ).

9.2 Список смежности (Adjacency List)

Список смежности — это массив (или хеш-таблица) из n элементов, где каждый элемент содержит список соседей данной вершины.

Реализации:

vector<vector<int>> (C++);
List<List<Node>> или Map<Node, List<Node>> (Java/C#);
dict[int, list[int]] (Python).

Python:

# Каждая вершина содержит список соседей
adjacency_list = {
    0: [1, 3],
    1: [0, 2],
    2: [1, 3],
    3: [0, 2]
}

Java:

// Map с набором вершин
Map<Integer, Set<Integer>> graph = new HashMap<>();
graph.put(0, Set.of(1, 3));
graph.put(1, Set.of(0, 2));

Свойства:

Память: O(n + m) — оптимально для разреженных графов;
Итерация по соседям: O(deg(v)) — линейно от степени вершины;
Добавление ребра: O(1) (в конец списка).

Недостатки:

Проверка существования ребра: O(deg(v)) — нужно просканировать список;
Удаление ребра: O(deg(v)) без двусвязного списка;
Фрагментация памяти, если списки выделяются отдельно.

Применение:

Большинство алгоритмов обхода: BFS, DFS, Dijkstra, Tarjan;
Социальные графы, маршрутизация, семантические сети.

9.3 Compressed Sparse Row (CSR) — сжатое разреженное строковое представление

CSR — это компактное и кэш-эффективное представление разреженных графов, заимствованное из линейной алгебры. Используется в high-performance computing и графовых базах данных.

Python:

# Три массива для представления графа
values = [1, 2, 2, 0]                    # целевые вершины
col_indices = [1, 2, 2, 0]               # индексы конечных вершин
row_ptr = [0, 2, 3, 4]                   # смещения строк

# Вершина 0 имеет рёбра 1 и 2 (индексы row_ptr[0] до row_ptr[1])
# Вершина 1 имеет ребро 2 (индексы row_ptr[1] до row_ptr[2])
# Вершина 2 имеет ребро 0 (индексы row_ptr[2] до row_ptr[3])

Структура:

Три массива:

values — список всех рёбер (или весов), упорядоченных по исходной вершине;
col_indices — для каждого элемента в values — индекс конечной вершины;
row_ptr — длина n + 1, где row_ptr[i] — позиция в values, с которой начинаются рёбра из вершины i.

Пример для графа:

→ 1, 2  
→ 2  
→ 0

values      = [1, 2, 2, 0]
col_indices = [1, 2, 2, 0]
row_ptr     = [0, 2, 3, 4]

Преимущества:

Непрерывное хранение данных → отличная кэш-локальность;
Память: O(n + m), без указателей;
Параллелизм: строки (исходные вершины) независимы — идеально для GPU и SIMD;
Поддержка только чтения — оптимален для аналитических нагрузок.

Недостатки:

Невозможно эффективно модифицировать — вставка ребра требует перестройки массивов;
Сложность реализации.

Применение:

Графовые процессоры (GraphBLAS, cuGraph);
PageRank, связность, распространение влияния;
Библиотеки вроде SciPy (scipy.sparse.csr_matrix).

9.4 Property Graphs — графы со свойствами

Property Graph — это модель данных, используемая в графовых базах данных (Neo4j, Amazon Neptune, JanusGraph). Отличается от математического графа тем, что:

Вершины и рёбра могут иметь свойства в виде пар «ключ–значение»;
Рёбра имеют тип (label): например, KNOWS, WORKS_AT;
Рёбра всегда направленные, но могут быть запрошены как ненаправленные.

Пример:

(Алекс {age: 30}) -[KNOWS {since: 2020}]-> (Мария {age: 28})

Хранение в СУБД:

Вершины и рёбра хранятся как отдельные записи;
Индексы по:
- ID вершин;
- типу рёбер;
- свойствам (для фильтрации);
Для быстрого обхода используются adjacency lists на диске с кэшированием.

Neo4j, например, использует native graph storage: каждый узел содержит указатели на первое входящее и исходящее ребро, а рёбра образуют двусвязные списки по направлению. Это позволяет обходить соседей без полного сканирования.

Компромиссы:

Гибкость модели vs. сложность оптимизации запросов;
ACID-транзакции возможны, но дороже, чем в реляционных СУБД;
Масштабирование — горизонтальное (шардинг по вершинам) остаётся сложной задачей из-за связности.

10. Вероятностные и потоковые структуры данных

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

10.1 Фильтр Блума (Bloom Filter)

Фильтр Блума — это компактная структура данных для проверки принадлежности элемента множеству с возможностью ложноположительных срабатываний, но без ложноотрицательных.

Python:

# Битовый массив и функция хеширования
bit_array = [0, 0, 0, 0, 0, 0]  # 6 бит
def hash_function(item):
    return sum(ord(c) for c in item) % len(bit_array)

# Добавление элемента
for char in "example":
    idx = hash_function(char)
    bit_array[idx] = 1

# Проверка наличия
all_set = True
for char in "example":
    if bit_array[hash_function(char)] == 0:
        all_set = False

C#:

// Фильтр Блума на C#
BitArray bloomFilter = new BitArray(1000);
foreach (var key in keys) {
    int index = GetHash(key) % 1000;
    bloomFilter.Set(index, true);
}

Принцип работы

Инициализируется битовый массив длиной m, заполненный нулями.
Используется k независимых хеш-функций h₁, ..., hₖ.
При добавлении элемента x: устанавливаются биты h₁(x), ..., hₖ(x) в 1.
При проверке: если все соответствующие биты равны 1 — элемент возможно в множестве; если хотя бы один бит 0 — элемент точно отсутствует.

Свойства

Память: O(m), независимо от числа элементов.
Операции: O(k) — константное время.
Ложноположительная вероятность

Инженерные аспекты

Невозможность удаления в классическом варианте (биты могут быть общими для разных элементов).
Counting Bloom Filter: заменяет биты на счётчики (обычно 4 бита), что позволяет удалять элементы, но увеличивает память в 4–8 раз.
Scalable Bloom Filters: динамически расширяются при превышении порога ошибки.
Применение:
- Проверка существования ключа в распределённой БД (Bigtable, Cassandra) — избегает дорогих дисковых I/O;
- Спам-фильтрация (быстрая проверка на чёрный список);
- Кэш-валидация (например, в CDN — есть ли ресурс в origin?).

10.2 Count-Min Sketch

Count-Min Sketch (CMS) — структура для оценки частоты встречаемости элементов в потоке данных. Позволяет отвечать на запросы вида «сколько раз встречался ключ x?» с гарантированной верхней границей погрешности.

Python:

# Таблица счётов для оценки частоты
width = 100
depth = 4
table = [[0] * width for _ in range(depth)]

def count_item(item):
    counts = [table[d][hash(item) % width] for d in range(depth)]
    return min(counts)  # Возвращает минимальное значение среди всех строк

Java:

// Count-Min Sketch в Java
int[][] cmSketch = new int[5][256];
for (int d = 0; d < 5; d++) {
    cmSketch[d][hash(key) % 256]++;
}

Принцип работы

Матрица из d строк и w столбцов, все ячейки = 0.
d независимых хеш-функций, каждая отображает ключ в [0, w).
При обновлении счётчика для x: инкрементировать table[i][hᵢ(x)] для всех i.
При запросе частоты: вернуть минимум по всем table[i][hᵢ(x)].

Почему минимум? Потому что коллизии только увеличивают значения (отсюда «min» даёт наименее завышенную оценку).

Свойства

Память: O(ε⁻¹ log δ⁻¹)
Операции: O(log δ⁻¹)
Оценка завышена, но никогда не занижена.

Применение

Обнаружение «тяжёлых» ключей (heavy hitters) — например, самых запрашиваемых URL;
Анализ сетевого трафика (NetFlow, DDoS-детекция);
Приближённые JOIN’ы в потоковых СУБД (Apache Flink, Kafka Streams);
Системы рекомендаций (оценка популярности).

Варианты

Conservative Update: уменьшает погрешность для редких элементов;
Hierarchical CMS: для распределённых систем с агрегацией.

10.3 Другие вероятностные структуры

HyperLogLog

Оценивает количество уникальных элементов (кардинальность) с погрешностью ~1.5%, используя всего 1.5 КБ памяти независимо от объёма данных.

Python:

# Оценка уникальных элементов с высокой точностью
# Визуализация регистров
registers = [0, 0, 0, 0, 1, 0, 2, 0, 1, 0]

# Количество уникальных элементов вычисляется на основе максимальных позиций установки бита
estimated_count = compute_hyperloglog(registers)

Применяется в Redis (PFADD, PFCOUNT), Google Analytics, рекламных системах.

Cuckoo Filter

Альтернатива Bloom Filter с поддержкой удаления и лучшей локальностью данных за счёт хранения «отпечатков» (fingerprints) в хеш-таблице с двумя возможными позициями.

Python:

# Таблица с двумя возможными позициями для каждого элемента
bucket_size = 4
cuckoo_table = [
    [None] * bucket_size for _ in range(size)
]

def add_item(item, fingerprint):
    pos1 = hash(item) % size
    pos2 = (hash(item) + hash(fingerprint)) % size
    
    if can_insert(pos1, fingerprint):
        insert_at(pos1, fingerprint)
    elif can_insert(pos2, fingerprint):
        insert_at(pos2, fingerprint)
    else:
        kick_and_redistribute(pos1, fingerprint)

Quotient Filter

Ещё одна замена Bloom Filter, поддерживающая слияние и удаление, с меньшим оверхедом памяти.

Инженерный контекст: где и зачем используются

Структура	Тип ошибки	Память	Используется в
Bloom Filter	Ложноположительная	Очень низкая	Cassandra, Bitcoin (SPV), Squid
Count-Min Sketch	Завышенная оценка	Низкая	Akamai, Flink, мониторинг
HyperLogLog	Относительная погрешность	1–2 КБ	Redis, Druid, Google BigQuery
Cuckoo Filter	Ложноположительная	Ниже Bloom	Новые СУБД, secure routing

Ключевой принцип: пожертвовать точностью ради масштабируемости. В потоковых системах, где данные не сохраняются, такие структуры — единственный способ извлекать сигнал из шума.

11. Реализация структур данных в системном ПО

11.1 Операционные системы

11.1.1 Планировщик задач (scheduler)

Структура: красно-чёрное дерево (Linux, начиная с ядра 2.6.23, в Completely Fair Scheduler — CFS).
Ключ: vruntime (виртуальное время исполнения процесса).
Почему не куча? Планировщик должен:
- быстро находить задачу с минимальным vruntime (как в куче),
- но также поддерживать балансировку по группам (cgroups), удаление произвольных задач (при завершении), изменение приоритета.
Итог: RB-дерево даёт O(log n) для всех операций с поддержкой итерации и модификации — куча этого не обеспечивает.

11.1.2 Управление виртуальной памятью

Структура: radix-дерево (Linux) или сбалансированное B-дерево (Windows) для хранения VMA (Virtual Memory Areas).
Задача: быстро находить регион памяти по адресу, объединять/разделять регионы при mmap/munmap.
Radix-дерево эффективно для диапазонных запросов и обладает хорошей кэш-локальностью.

11.1.3 Кэши ядра (slab allocator)

Структура: связные списки и битовые карты.
Цель: выделение объектов фиксированного размера (например, task_struct) без фрагментации.
Аналог в пользовательском пространстве — memory pool.

11.2 Системы управления базами данных (СУБД)

11.2.1 Индексы

B⁺-деревья — стандарт де-факто для дисковых СУБД (PostgreSQL, MySQL InnoDB, Oracle, SQL Server).
- Хранятся в страницах, выровненных по границе блока ОС (обычно 4–16 КБ).
- Поддерживают многоверсионность (MVCC) через временные метки или undo-логи.
- В InnoDB: листья B⁺-дерева содержат кластеризованные данные (clustered index), что ускоряет диапазонные запросы.
LSM-деревья (Log-Structured Merge Trees) — в NoSQL и аналитических СУБД (Cassandra, RocksDB, ScyllaDB).
- Данные сначала пишутся в memtable (skip-list или AVL-дерево в памяти),
- При переполнении сбрасываются в неизменяемый SSTable на диск,
- Фоновые процессы сливают SSTable’ы.
- Преимущество: высокая write-throughput, особенно на SSD.
- Недостаток: read amplification (нужно проверить несколько уровней).

11.2.2 Хэш-индексы

Используются в in-memory СУБД (Redis, Memcached, VoltDB).
Реализация: открытая адресация или цепочки.
Ограничение: не поддерживают диапазонные запросы.

11.2.3 Векторные индексы (AI/ML)

Современные СУБД (PostgreSQL + pgvector, Milvus, Pinecone) используют приближённые структуры:
- HNSW (Hierarchical Navigable Small World) — граф, оптимизированный для поиска ближайших соседей в высоких размерностях;
- IVF (Inverted File Index) — разбиение пространства на кластеры, поиск только в ближайших.
Эти структуры — гибриды графов, хэшей и деревьев.

11.3 Runtime-окружения (CLR, JVM, V8)

11.3.1 Сборка мусора

Remembered sets (в generational GC) — реализуются как битовые карты или хэш-таблицы для отслеживания ссылок из старого поколения в новое.
Card tables — массив байтов, где каждый байт «покрывает» 512 байт кучи; модификация помечает «карту» как «грязную».

11.3.2 Коллекции

.NET (List<T>, Dictionary<TKey, TValue>, SortedSet<T>):
- List<T> — динамический массив;
- Dictionary<,> — хэш-таблица с открытой адресацией и двойным хешированием;
- SortedSet<T> — красно-чёрное дерево.
Java (ArrayList, HashMap, TreeMap):
- HashMap — массив + цепочки → дерево при длине > 8;
- ConcurrentHashMap — сегментированная блокировка (раньше) или CAS + bins (с Java 8).
V8 (JavaScript):
- Массивы хранятся как fast elements (непрерывный массив) или dictionary mode (хэш-таблица) при разреженности;
- Объекты — hidden classes + shape trees, что позволяет оптимизировать доступ к полям.

См. также

Другие статьи этого же раздела в боковом меню (как на странице «О разделе»).