Структуры данных для подготовки к собеседованиям по алгоритмам

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

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

Рекомендую также прочитать мою статью про алгоритмы и оценку сложности. Эти две статьи помогут вам подготовиться к алгоритмическим собеседованиям.

Я не преследую цель дать всю исчерпывающую информацию в одной статье – это лишь перечисление самых часто используемых структур данных с поверхностным пояснением.

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

Если вы нанимаете, и готовы рассмотреть хорошего Junior+/Middle Python Backend, напишите мне в Telegram. Я учу людей программировать, а не просто проходить собеседования. Даже если прямо сейчас у вас нет вакансии, в будущем у вас появится потребность в хорошем Junior+, который готов к самостоятельной работе и может быстро расти до уровня Middle. Посмотрите как я обучаю, если у вас есть сомнения.

Используйте содержание и кнопку НАВЕРХ для удобства навигации по статье.

Содержание

1. Массивы

   1. Статический массив

   2. Динамический массив

   3. Двумерные массивы (матрицы)

2. Связные списки

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

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

   3. Циклические списки

3. Стек (Stack)

4. Очереди (Queues)

   1. FIFO (First In, First Out)

   2. LIFO (Last In, First Out)

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

   4. Очередь с приоритетом (Priority Queue)

5. Бинарная куча (Binary heap)

   1. Как работает бинарная куча (Binary heap)

   2. Минимальная куча (Min-Heap)

   3. Максимальная куча (Max-Heap)

6. Хеш-таблица (Hash table)

   1. Основные характеристики

   2. Как работает хеш-функция

   3. Что такое бакет (bucket)

   4. Как выбирается бакет

   5. Как работает resize в Хеш-таблице

   6. Худший случай в хеш-таблице

   7. Оптимизация работы Хеш-таблицы

7. Деревья (Trees)

   1. Бинарное дерево (Binary tree)

      1. Общие сведения

      2. Виды бинарных деревьев

      3. Бинарные деревья поиска (BST)

   2. AVL деревья

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

   4. Б-дерево (Btree)

   5. Б+-дерево (B+tree)

   6. Префиксные деревья (Tries)

8. Графы

   1. Деревья (Tree)

   2. Ориентированные графы (Direct Graph)

   3. Неориентированные графы (Undirected Graph)

   4. Взвешенные графы (Weighted Graph)

   5. Двудольные графы (Bipartite Graph)

   6. Сильно связные графы (Strongly Connected Graph)

   7. Графы с циклами (Cyclic Graph)

   8. Графы без циклов (Acyclic Graph)

9. Заключение

Массивы

Статический массив

Статический массив или просто массив – это структура данных, в которой количество элементов заранее определено и не может быть изменено во время выполнения программы и все элементы имеют один тип данных, например только int. При этом массив не является неизеняемым и значения в массиве можно изменить, но нельзя добавить новый элемент, так как длина массива фиксированная.

В Python нет традиционных статических массивов (как в C или Java), но в Python есть массивы с фиксированным типом элементов это модуль array. Они работают более эффективно, чем списки, но поддерживают только один тип данных.

array.array в Python под капотом использует динамический массив.

Хотя он работает похоже на статический массив, он не является статическим, потому что:

1. Он может изменяться в размере с помощью .append(), .extend(), .pop(), и т. д.

2. При нехватке памяти он перевыделяется (realloc()) аналогично list.

3. Под капотом у array.array используется C-массив, но с динамическим управлением памятью.

Так же в python есть tuple, который похож на статический массив, но позволяет хранить элементы разного типа. Под капотом в CPython для его релизации используется статический массив, но хранит в себе не сами объекты, а ссылки на них.

Смотрите реализацию tuple в CPython тут и тут, чтобы лучше понять как он устроен. Обратите внимание на _PyTuple_Resize в некоторых ситуациях tuple все таки может изменяться, но это происхдит в особых случаях, и он на самом деле не изменяется, а пересоздается заново.

НАВЕРХ

Динамический массив

Динамическим называется массив, размер которого может изменяться во время выполнения програмы.

В python это любые последовательности кроме tuple, например list является динамическим массивом, потому что его размер можно изменить с помощью методов .append(), .extend(), .pop(), и т. д.

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

Давайте разберёмся на пальцах, как это работает под капотом большинства языков программирования (методы ниже из языка Си):

1. Выделем память с помощью calloc или malloc заданного размера

2. Добавляем в массив элементы

3. Когда выделенная память израсходована, вызывается метод realloc и выделяется дополнительная память, увеличив исходную в два(обычно) раза, чтобы массив вмещал не 4, а например 8 элементов.

4. Если realloc не может расширить непрерывный блок памяти, выделяется новый смежный участок увеличенного размера, и данные копируются туда.

5. Продолжаем добавлять элементы, если память снова закончилась повторяем шаг 3 и 4.

6. Когда массив нам больше не нужен, освобождаем память с помощью метода free

Выше всего лишь поверхотсное описание базового сценария добавления нового элемента в динамический массив.

НАВЕРХ

Двумерные массивы (матрицы)

Двумерный массив — это таблица данных, где:

• Строки идут горизонтально (слева направо).

• Столбцы идут вертикально (сверху вниз).

• Каждый элемент имеет два индекса: [номер строки][номер столбца].

Пример двумерного массива:

1  2  3
4  5  6
7  8  9

1 2 3 4 5 6 7 8 9 (не путайте с нумерацией строк 1, 2, 3 по вертикали)

1 — элемент с индексами [0][0]
5 — элемент с индексами [1][1]

Реализация двумерных массивов в Python

Python не имеет встроенного типа “двумерный массив”, но можно создать его разными способами.

Двумерный массив с list (список списков)

matrix = [
    [1, 2, 3],  
    [4, 5, 6],  
    [7, 8, 9]
]

# Доступ к элементу (например, 5)
print(matrix[1][1])  # 5

Плюсы: Простая реализация
Минусы: Медленный доступ к элементам в больших массивах

Двумерный массив с numpy (быстрые вычисления)

import numpy as np

matrix = np.array([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
])

# Доступ к элементу
print(matrix[1, 1])  # 5

Плюсы: Быстрее, чем list, удобные операции с числами
Минусы: Нужно устанавливать numpy

Двумерный массив с array.array (эффективно по памяти)

import array

matrix = [
    array.array('i', [1, 2, 3]),
    array.array('i', [4, 5, 6]),
    array.array('i', [7, 8, 9])
]

print(matrix[1][1])  # 5

Плюсы: Экономит память
Минусы: Только для чисел одного типа

Где используются двумерные массивы в реальных проектах?

Изображение — это двумерный массив пикселей. Например, чёрно-белая картинка — это матрица чисел (0 — чёрный, 255 — белый).

import cv2  # OpenCV

image = cv2.imread('image.jpg', cv2.IMREAD_GRAYSCALE)  # Загружаем картинку как 2D-массив
print(image.shape)  # (высота, ширина)

Матрицы используются в нейросетях, обработке текстов, анализе данных.

import numpy as np

weights = np.random.rand(3, 3)  # Матрица весов для нейросети
print(weights)

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

game_map = [
    [0, 1, 0],
    [1, 0, 1],
    [0, 1, 0]
]  # 0 — пустая клетка, 1 — стена

Когда мы загружаем таблицу из базы данных, она фактически является двумерным массивом.

import sqlite3

conn = sqlite3.connect('database.db')
cursor = conn.cursor()

cursor.execute("SELECT * FROM users")
data = cursor.fetchall()  # Получаем данные в виде списка кортежей (2D-матрица)

НАВЕРХ

Связные списки

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

Односвязный или однонаправленный список – это структура данных, состоящая из элементов, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на NULL.

Давайте рассмотрим пример на Python. Я использовал tuple, но можно использовать любую последовательность.

third = ('third', None)
second = ('second', third)
first = ('first', second)

В примере выше tuple содержит первым элементом значение, а вторым сслыку на объект, в котором хранится следующее значение. Последовательность заканчивается на third, так как второй элемент None и ни на что не ссылается.

НАВЕРХ

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

Двусвязный или двунаправленный список – это структура данных, состоящая из элементов, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на предыдущий и следующий элемент.

Давайте рассмотрим пример на Python.

third = (second, 'third', None)
second = (first, 'second', third)
first = (None, 'first', second)

В примере выше tuple содержит вторым элементом значение, а первым и третьим ссылки на предыдущий и следующий объект.

У first первый элемент None, потому что нет предыдущего объекта, а у third третий элемент None, потому что нет следующего объекта и на нем последовательность заканчивается.

В Python есть реализация двусвязного списка – это deque. Одно из преймуществ двусвязного списка – это возможность удалить или добавить элемент в начало списка за константное время O(1). К примеру в случае list эти операции выполняются за линейное время O(n). Еще одно преймущество – это динамическое выделение памяти, но без лишних копирований в отличие от динамического массива как с list.

Внешне deque выглядит как обычный двусвязный список и получение элемента по индексу происходит хотя и за линейное время O(n), но без полного прохода по всем элементам, потому что под капотом используются структура данных – связанный список блоков.

Как это реализованно:

[BLOCK_1] → [BLOCK_2] → [BLOCK_3] ...

• Каждый блок — это массив указателей (например, на 64 элемента).

• При переполнении создаётся новый блок, связанный с предыдущим.

• Внутри каждого блока элементы хранятся как кольцевой буфер (индексы left и right двигаются циклически).

• Когда один блок (64 элемента) заполняется, создаётся новый блок и связывается с предыдущим.

• Если один блок полностью пустеет, он может быть удалён.

• Доступ к элементу по индекс в deque не приводит к проходу по всем элементам, а идет по блокам, проверяя только вхождение индекса в блок (диапазон индексов в блоке например 64-127).

Допустим у нас deque с 256 элементами и блоками по 64 элемента:

Блок 0 → [0, 1, 2, ..., 63]   (индексы 0-63)
Блок 1 → [64, 65, ..., 127]   (индексы 64-127)
Блок 2 → [128, ..., 191]      (индексы 128-191)
Блок 3 → [192, ..., 255]      (индексы 192-255)

Чтобы найти deque[150]:

1. Проверяем Блок 0 (0-63) – не здесь.

2. Проверяем Блок 1 (64-127) – не здесь.

3. Проверяем Блок 2 (128-191) – индекс 150 внутри!

4. Берём deque[150] прямым доступом как в массиве за O(1). В итоге доступ по индексу O(k), но k – это число блоков, а не общее число элементов.

Не нужно проходить все 256 элементов!

НАВЕРХ

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

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

Обычный список:

A → B → C → D → None  (конец списка)

Циклический список:

A → B → C → D → A  (последний элемент ссылается на первый)

Такой список никогда не заканчивается, и если пройти по нему обычным способом, можно попасть в бесконечный цикл!

Давайте рассмотрим пример на Python.

third = ['third', None]
second = ['second', third]
first = ['first', second]

third[1] = first

В примере выше tuple содержит первым элементом значение, а вторым сслыку на объект, в котором хранится следующее значение. Цикл начинается на third, так как второй элемент ссылается на первый first.

Циклический список через collections.deque

Используется, если нужно легко делать “зацикленное” движение по списку.

from collections import deque

# Создаём двустороннюю очередь
cyclic_list = deque([1, 2, 3, 4])

# Циклический сдвиг (вращение)
cyclic_list.rotate(-1)  # Перемещает первый элемент в конец
print(cyclic_list)  # deque([2, 3, 4, 1])

cyclic_list.rotate(2)  # Сдвигаем два элемента назад
print(cyclic_list)  # deque([4, 1, 2, 3])

Где используется?

• В круговых очередях (например, обработка задач)

• В музыкальных плеерах (циклический плейлист)

• В игровых логиках (например, ходы по кругу)

Циклический список через itertools.cycle

Если нам нужно бесконечно проходить список по кругу:

import itertools

cyclic_list = [1, 2, 3, 4]

# Создаём бесконечный итератор
cycle_iter = itertools.cycle(cyclic_list)

for _ in range(10):  # Проходим 10 шагов (но можно бесконечно)
    print(next(cycle_iter), end=" ")  # 1 2 3 4 1 2 3 4 1 2

Где используется?

• В анимациях (повторяющиеся циклы кадров)

• В бесконечном переборе данных (например, изображения на веб-сайте)

• В ботах и автоматизации (например, перебор действий)

Реализация циклического связного списка вручную

Если нужен настоящий связанный список с циклом:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None  # Следующий элемент

class CircularLinkedList:
    def __init__(self):
        self.head = None  # Голова списка

    def append(self, data):
        new_node = Node(data)
        if not self.head:  # Если список пуст
            self.head = new_node
            self.head.next = self.head  # Указываем на себя (создаём цикл)
        else:
            temp = self.head
            while temp.next != self.head:  # Находим последний элемент
                temp = temp.next
            temp.next = new_node  # Добавляем новый узел
            new_node.next = self.head  # Замыкаем в кольцо

    def display(self, steps=10):
        """Выводим список, но не бесконечно"""
        temp = self.head
        for _ in range(steps):
            print(temp.data, end=" → ")
            temp = temp.next
        print("... (цикл)")

# Используем
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)
cll.append(4)

cll.display()  # 1 → 2 → 3 → 4 → 1 → 2 → 3 → 4 → 1 → 2 → ... (цикл)

Где используется?

• В операционных системах (планировщики задач)

• В графах (если граф цикличен)

• В сетевых алгоритмах (маршрутизация пакетов)

НАВЕРХ

Стек (Stack)

Стек — это структура данных, работающая по принципу LIFO (Last In, First Out), что означает: Последний добавленный элемент извлекается первым.

Пример на Python

stack = []  
stack.append(1)  # push(1)
stack.append(2)  # push(2)
stack.append(3)  # push(3)
print(stack)  # [1, 2, 3]

top = stack.pop()  # pop() -> 3
print(top)   # 3
print(stack)  # [1, 2]

Где используется стек?

• Обратный порядок выполнения (например, стек вызова функций в Python, JavaScript и т.д.).

• Алгоритмы обхода (DFS, обратная польская нотация).

• Отмена действий (Ctrl+Z).

• Парсинг выражений (проверка скобок, HTML).

НАВЕРХ

Очереди (Queues)

FIFO (First In, First Out)

FIFO (First In, First Out) — это очередь, где первый добавленный элемент извлекается первым.

Пример из жизни: Очередь в магазине

• Первый человек, который встал в очередь, обслуживается первым.

• Последний пришедший ждёт своей очереди.

Это и есть FIFO: первый зашёл — первый вышел.

Пример реализации в Python

from collections import deque

queue = deque()
queue.append(1)  # enqueue(1)
queue.append(2)  # enqueue(2)
queue.append(3)  # enqueue(3)

print(queue.popleft())  # dequeue() -> 1
print(queue)  # deque([2, 3])

Важно, что для реализации FIFO, хорошо подходит связанный список deque, потому что с ним мы можем брать первый элемент из очереди за константное время O(1) методом popleft. В случае с list эта операция займет O(n).

НАВЕРХ

LIFO (Last In, First Out)

LIFO (Last In, First Out) переводится как «последним пришёл – первым вышел».

Это принцип работы стека (stack), где последний добавленный элемент удаляется первым.
Представьте стопку тарелок:

• Если положить тарелку №1, затем №2, затем №3,

• То первыми достанем в обратном порядке: №3 → №2 → №1.

Графическое представление стека (LIFO):

Добавляем:  1 → 2 → 3  (3 сверху)
Извлекаем:  3 → 2 → 1  (3 первым выходит)

Реализация LIFO в Python

Используем list (встроенный стек)

stack = []  # Создаём пустой стек

stack.append("A")  # Добавляем "A"
stack.append("B")  # Добавляем "B"
stack.append("C")  # Добавляем "C"

print(stack)  # ['A', 'B', 'C']

# Удаляем (всегда с конца)
print(stack.pop())  # C
print(stack.pop())  # B
print(stack.pop())  # A

append() – добавляет в конец (верх стека)
pop() – удаляет последний добавленный элемент

Используем queue.LifoQueue (потокобезопасный стек)

from queue import LifoQueue

stack = LifoQueue()

stack.put("A")
stack.put("B")
stack.put("C")

print(stack.get())  # C
print(stack.get())  # B
print(stack.get())  # A

Подходит для многопоточных программ (безопасен в многозадачных системах).

НАВЕРХ

Двусторонняя очередь (Deque)

Дек — это двусторонняя очередь (так же называют deque, double-ended queue), которая поддерживает добавление и удаление элементов с обоих концов за O(1).

Пример из жизни: Очередь в метро

• Люди могут заходить спереди и сзади.

• Могут выходить как с начала, так и с конца.

Это и есть дек — гибкая очередь с доступом к обоим концам.

Пример на Python

from collections import deque

d = deque()  
d.append(1)       # [1]
d.append(2)       # [1, 2]
d.appendleft(0)   # [0, 1, 2]

print(d.pop())    # 2 (удаляем с конца)
print(d.popleft()) # 0 (удаляем с начала)
print(d)          # deque([1])

НАВЕРХ

Очередь с приоритетом (Priority Queue)

Очередь с приоритетом – это очередь, где элементы извлекаются не в порядке добавления (FIFO), а по приоритету.

Пример из жизни: Больница

• Пациенты поступают в разном порядке.

• Сначала обслуживаются те, у кого высокий приоритет (например, срочные случаи).

• Обычные пациенты ждут своей очереди.

Пример реализации с использованием queue.PriorityQueue (потокобезопасная реализация)

from queue import PriorityQueue

pq = PriorityQueue()
pq.put((1, "Low priority"))
pq.put((3, "High priority"))
pq.put((2, "Medium priority"))

print(pq.get())  # (1, 'Low priority')
print(pq.get())  # (2, 'Medium priority')
print(pq.get())  # (3, 'High priority')

Так же можно использовать пакет heapq для реализации очереди с приоритетом.

НАВЕРХ

Бинарная куча (Binary heap)

Как работает бинарная куча (Binary heap)

Очередь с приоритетом и куча – тесно связаны, так как куча является эффективной внутренней структурой для реализации очереди с приоритетом. Т.е. куча – это структура данных, которая используется для реализации очереди с приоритетом, которая является абстрацией.

Куча – это деревовидная структура данных, которая может быть минимальной или максимальной.

Основные операции (вставка, удаление) выполняются за O(log n). Куча автоматически перестраивается после вставки и удаления.

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

Представление кучи в виде дерева

        1
       / 
      2   3
     / 
    4   5

Свойство кучи:

• 1 (корень) < 2, 3

• 2 < 4, 5

• 3 не имеет потомков

Соответствующий массив (list)

heap = [1, 2, 3, 4, 5]

Элементы идут сверху вниз, слева направо.

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

• Родитель узла: parent(i) = (i – 1) // 2

• Левый потомок: left(i) = 2 * i + 1

• Правый потомок: right(i) = 2 * i + 2

Как изменяется куча при вставке и удалении?

Вставка нового элемента (например, 0)

До вставки:

        1
       / 
      2   3
     / 
    4   5

Массив: [1, 2, 3, 4, 5]

Добавляем 0 в конец массива:

        1
       / 
      2   3
     / 
    4   5
   /
  0

Массив: [1, 2, 3, 4, 5, 0]

Но 0 < 4, значит, поднимаем его вверх (просеивание вверх).

После перестановок:

        0
       / 
      1   3
     / 
    2   5
   /
  4

Массив: [0, 1, 3, 2, 5, 4]

Удаление минимального элемента (1)

До удаления:

        1
       / 
      2   3
     / 
    4   5

Массив: [1, 2, 3, 4, 5]

Удаляем 1, перемещаем последний элемент (5) в корень:

        5
       / 
      2   3
     / 
    4

Массив: [5, 2, 3, 4]

Так как 5 > 2, меняем местами 5 и 2:

        2
       / 
      5   3
     / 
    4

Массив: [2, 5, 3, 4]

Теперь 5 > 4, меняем местами 5 и 4:

        2
       / 
      4   3
     / 
    5

Массив: [2, 4, 3, 5]

Свойство минимальной кучи восстановлено!

НАВЕРХ

Минимальная куча (Min-Heap)

Минимальная куча (Min-Heap): Родительский элемент всегда меньше своих дочерних элементов. Таким образом, минимальный элемент всегда находится в корне дерева.

Пример минимальной кучи:

          1
         / 
        2   3
       / 
      4   5

1 – минимальный элемент, так как все элементы в дереве больше или равны ему.

Минимальная куча (Min-Heap) — извлекаются элементы с минимальным приоритетом.

• Используется в основном для реализации очереди с приоритетом, где меньшие числа имеют более высокий приоритет.

• Реализуется с помощью heapq (по умолчанию).

Пример реализации Min-Heap в Python:

import heapq

# Инициализация пустой очереди с приоритетом
pq = []

# Добавление элементов (приоритет, значение)
heapq.heappush(pq, (1, "Low priority"))
heapq.heappush(pq, (3, "High priority"))
heapq.heappush(pq, (2, "Medium priority"))

# Извлечение элемента с наивысшим приоритетом
print(heapq.heappop(pq))  # (1, 'Low priority')
print(heapq.heappop(pq))  # (2, 'Medium priority')
print(heapq.heappop(pq))  # (3, 'High priority')

В heapq приоритет задается первым значением в кортеже (кортеж вида (приоритет, значение)). Функция heappush добавляет элемент в кучу, а heappop извлекает элемент с минимальным приоритетом.

НАВЕРХ

Максимальная куча (Max-Heap)

Максимальная куча (Max-Heap): Родительский элемент всегда больше своих дочерних элементов. Максимальный элемент находится в корне дерева.

Пример максимальной кучи:

          5
         / 
        4   3
       / 
      2   1

5 — максимальный элемент, так как все элементы в дереве меньше или равны ему.

Максимальная куча (Max-Heap) – извлекаются элементы с максимальным приоритетом.

Пример реализации с помощью отрицания приоритетов в heapq:

import heapq

heap = []
heapq.heappush(heap, -3)  # Добавляем отрицательные числа
heapq.heappush(heap, -1)
heapq.heappush(heap, -5)

print(-heapq.heappop(heap))  # 5 (максимальный элемент)

НАВЕРХ

Хеш-таблица (Hash table)

Основные характеристики

Хеш-таблица – это структура данных, которая позволяет хранить пары «ключ-значение» и обеспечивать быстрый доступ к значениям по ключу.

Основные характеристики:

• Хеш-функция – применяется к ключу и возвращает целочисленное хеш-значение (обычно большое число).

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

  • Метод цепочек (Chaining) – каждый элемент массива хранит список (или другой контейнер) с элементами, имеющими одинаковый хеш.

  • Открытая адресация (Open Addressing) – при коллизии ищется следующая свободная ячейка (например, линейное пробирование).

Сложность операций

В Python хеш-таблицы реализованы в виде словарей (dict) и множеств (set).

Пример с dict:

# Создание хеш-таблицы (словаря)
hash_table = {
    "apple": 10,
    "banana": 20,
    "orange": 30
}

# Доступ к значению
print(hash_table["banana"])  # 20

# Добавление нового элемента
hash_table["grape"] = 40

# Удаление элемента
del hash_table["apple"]

# Проверка существования ключа
if "orange" in hash_table:
    print("Есть в таблице")

НАВЕРХ

Как работает хеш-функция

Когда мы добавляем ключ в словарь (dict), Python выполняет следующие шаги:

1. Вычисляет хеш-значение ключа с помощью встроенной функции hash().

2. Преобразует хеш в индекс бакета в хеш-таблице.

3. Если бакет занят (возникла коллизия), Python ищет другой бакет (используется открытая адресация).

Пример:

key = "hello"
hash_value = hash(key)  # Получаем хеш-значение
N = 8  # Размер хеш-таблицы (для простоты)
index = hash_value % N  # Вычисляем индекс бакета
print(f"Хеш: {hash_value}, Бакет: {index}")

НАВЕРХ

Что такое бакет (bucket)

• В Python хеш-таблица — это массив фиксированного размера, состоящий из бакетов.

• Бакет содержит ключ, значение и хеш ключа.

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

Размер массива всегда степень двойки (8, 16, 32, 64 и т.д.). Это ускоряет вычисление индекса с помощью & (N – 1), что быстрее, чем mod.

НАВЕРХ

Как выбирается бакет

Этап 1: Преобразование хеша в индекс

Python берет результат hash(key), а затем использует битовую операцию для вычисления индекса:

index = hash(key) & (N - 1)  # Быстрое вычисление индекса

Это эквивалентно hash(key) % N, но выполняется быстрее, так как N – степень двойки.

Этап 2: Проверка бакета

• Если бакет пуст, туда записывается (key, value, hash).

• Если бакет занят (коллизия). Python использует линейное пробирование и ищет следующую свободную ячейку.

Этап 3: Разрешение коллизий

Если два ключа попадают в один бакет (редкость, но возможно), Python:

1. Проверяет, совпадают ли ключи (не только хеши).

2. Если да — заменяет значение.

3. Если нет — использует линейное пробирование и проверяет следующий бакет.

НАВЕРХ

Как работает resize в Хеш-таблице

Когда происходит resize

Resize запускается, если используется более 2/3 бакетов.

• Начальный размер словаря = 8 бакетов

• При заполнении 6 бакетов (8 * 2/3 ≈ 5.3), словарь увеличивается до 16.

• При заполнении 10 бакетов (16 * 2/3 ≈ 10.6), увеличивается до 32.

• Этот процесс продолжается каждый раз при достижении 2/3 заполнения.

Как происходит resize

Когда Python увеличивает размер хеш-таблицы:

1. Создается новый массив в 2 раза больше старого.

2. Перехеширование всех элементов – каждый ключ получает новый индекс в новой таблице.

3. Запись элементов в новый массив по их новым индексам.

Почему нужно перехеширование (rehashing)

Когда увеличивается размер таблицы:

• Изменяется количество бакетов (N).

• Индекс каждого ключа вычисляется заново (hash(key) % new_size).

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

НАВЕРХ

Влияние resize и rehashing на производительность

resize – дорогая операция (O(n)). При увеличении размера все элементы копируются и перехешируются. Вставка в dict обычно O(1), но при resize становится O(n). Поэтому Python увеличивает размер в 2 раза, чтобы уменьшить частоту resize.

Худший случай в хеш-таблице

Python применяет открытую адресацию с линейным пробированием (linear probing). При коллизиях (hash(key1) % N == hash(key2) % N) новый ключ записывается в следующий свободный бакет.

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

Сравним скорость поиска в обычном словаре и словаре с плохими ключами:

import time

class BadHash:
    def __init__(self, value):
        self.value = value

    def __hash__(self):
        return 42  # Все объекты имеют одинаковый хеш

    def __eq__(self, other):
        return self.value == other.value  # Обычное сравнение

# Измеряем время для обычного словаря
start = time.time()
normal_dict = {i: f"Value {i}" for i in range(10000)}
print("Время создания обычного словаря:", time.time() - start)

# Измеряем время для словаря с плохими хешами
start = time.time()
bad_dict = {}
for i in range(10000):
    bad_dict[BadHash(i)] = f"Value {i}"
print("Время создания словаря с плохими хешами:", time.time() - start)

# Поиск элемента в словаре с обычными хешами
start = time.time()
for i in range(10000):
    _ = normal_dict[5000]  # Ожидаемая O(1)
print("Время поиска в словаре обычными хешами:", time.time() - start)

# Поиск элемента в словаре с плохими хешами
start = time.time()
for i in range(10000):
    _ = bad_dict[BadHash(5000)]  # Ожидаемая O(n)
print("Время поиска в словаре с плохими хешами:", time.time() - start)

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

Что происходит в этом примере?

• Мы создаем плохую хеш-функцию, которая всегда возвращает один и тот же хеш (42), что приводит к коллизиям для всех элементов.

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

• Так как мы используем линейное пробирование, при добавлении каждого нового элемента Python будет искать свободные ячейки по очереди, пока не найдет подходящую.

• В поиске Python будет использовать линейное пробирование для поиска нужной ячейки.

Результаты:

Время создания обычного словаря: 0.008013248443603516
Время создания словаря с плохими хешами: 4.327789306640625
Время поиска в словаре обычными хешами: 0.0017261505126953125
Время поиска в словаре с плохими хешами: 3.948306083679199

• В случае с плохим хешом, словарь будет работать неэффективно: при каждом поиске или вставке Python будет затрачивать больше времени на проверку ячеек.

• В худшем случае, если большая часть словаря занята, поиск и вставка могут быть выполнены за время O(n) вместо O(1).

НАВЕРХ

Оптимизация работы Хеш-таблицы

Способ 1: dict.fromkeys() (создает сразу N ключей)

Можно избежать resize задав нужный размер заранее, если это возможно.

d = dict.fromkeys(range(1000000), 0)  # Создаст сразу 1 млн ключей

Способ 2: defaultdict (лучше для больших словарей)

from collections import defaultdict
d = defaultdict(int)  # Значения по умолчанию будут 0
print(d[42])  # Вернет 0, даже если ключа 42 нет

defaultdict все равно использует те же правила resize, что и обычный dict, просто избегает лишних проверок наличия ключа, но количество элементов в нем растет так же, и еще он упрощает код, делая его более читаемым.

НАВЕРХ

Деревья (Trees)

Бинарное дерево (Binary tree)

Общие сведения

Бинарное дерево – это структура данных, где каждый узел (node) может иметь не более двух потомков (детей). Эти потомки называются левым и правым узлом.

Часто Binary tree путают с Btree, который используется в базах данных. Запомните, в базах данных используется Б+-деревья.

Основные термины:

• Корень (Root) — первый узел дерева. У него нет родителя.

• Лист (Leaf) — узел, у которого нет потомков.

• Родитель (Parent) — узел, имеющий потомков.

• Потомки (Children) — узлы, являющиеся дочерними по отношению к другому узлу.

• Глубина узла (Depth) — расстояние от корня до узла.

• Высота узла (Height) — расстояние от узла до самого дальнего листа.

• Поддерево (Subtree) — любое дерево, корнем которого является один из узлов исходного дерева.

• Размер дерева (Size) — общее количество узлов в дереве.

НАВЕРХ

Виды бинарных деревьев

• Полное (Full Binary Tree) — дерево, в котором у каждого узла либо два потомка, либо ни одного.

• Совершенное (Perfect Binary Tree) — бинарное дерево, у которого все внутренние узлы имеют ровно два потомка, а все листья находятся на одном уровне.

• Сбалансированное (Balanced Binary Tree) — бинарное дерево, в котором разница высот левого и правого поддерева любого узла не превышает 1.

• Двоичное или Бинарное дерево поиска (Binary Search Tree, BST) – рассмотрим подробно ниже.

НАВЕРХ

Бинарные деревья поиска (BST)

Бинарное дерево поиска (BST) — это бинарное дерево, в котором для каждого узла выполняется следующее свойство:

1. Все ключи в левом поддереве меньше, чем ключ текущего узла.

2. Все ключи в правом поддереве больше, чем ключ текущего узла.

3. Каждое поддерево также является бинарным деревом поиска.

Это свойство позволяет эффективно выполнять поиск, вставку и удаление элементов за O(log n) в среднем.

Структура BST

Допустим, у нас есть последовательность вставляемых элементов:
[10, 5, 15, 2, 7, 12, 20]

После вставки элементов дерево будет выглядеть так:

       10
      /  
     5    15
    /    /  
   2   7 12  20

Код для построения этого дерева:

class Node:
    def __init__(self, value):
        self.value = value  # Значение узла
        self.left = None  # Ссылка на левое поддерево
        self.right = None  # Ссылка на правое поддерево


root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(2)
root.left.right = Node(7)
root.right.left = Node(12)
root.right.right = Node(20)

Проблемы BST

1. Несбалансированность

   • Если вставлять элементы в возрастающем порядке, дерево превращается в список (линейное дерево), и сложность поиска становится O(n).

   • Решение: самобалансирующиеся деревья

2. Дублирующиеся значения

   • Чаще всего BST не допускает дубликаты.

   • Можно разрешить их, например, используя счетчик частоты.

Поиск элемента в BST

Алгоритм:

1. Если дерево пустое, возвращаем None.

2. Если key == node.value, нашли элемент.

3. Если key < node.value, идем в левое поддерево.

4. Если key > node.value, идем в правое поддерево.

Пример поиска в BST. Код построения дерева описан выше.

def search(node, key):
    if not node or node.value == key:
        return node  # Найден или отсутствует в дереве
    if key < node.value:
        return search(node.left, key)
    return search(node.right, key)

found = search(root, 7)
print(found.value if found else "Не найдено")  # Вывод: 7

Сложность:

• В сбалансированном дереве: O(log n)

• В несбалансированном (спискообразном): O(n)

НАВЕРХ

AVL деревья

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

Основные свойства AVL дерева:

1. Бинарное дерево поиска (BST): Все элементы слева от узла меньше его значения, а все элементы справа — больше.

2. Балансировка: Для каждого узла разница в высоте между левым и правым поддеревом не может быть больше 1. Это называется фактором баланса.

3. Фактор баланса: Для каждого узла дерево должно быть сбалансировано:

   • Если разница высот поддеревьев для узла больше 1, выполняются повороты (правый или левый).

4. Повороты:

   • Левый поворот (если правое поддерево слишком высокое).

   • Правый поворот (если левое поддерево слишком высокое).

   • Иногда выполняются двойные повороты (сначала правый, потом левый, или наоборот).

Пример AVL дерева:

               [30]
             /    
          [20]    [40]
         /       /    
      [10]   [25] [35]  [50]
                      /
                    [32]

Объяснение структуры:

1. Корень дерева — 30.

2. В левом поддереве:

   • 20 — левая вершина с поддеревом 10 и 25.

3. В правом поддереве:

   • 40 — правая вершина с поддеревом 35 и 50.

   • 35 имеет левое поддерево 32.

Балансировка дерева:

• Узел 30: высота левого поддерева (20) = 2, высота правого поддерева (40) = 2 → фактор баланса = 0, всё сбалансировано.

• Узел 20: высота левого поддерева (10) = 1, высота правого поддерева (25) = 1 → фактор баланса = 0.

• Узел 40: высота левого поддерева (35) = 2, высота правого поддерева (50) = 1 → фактор баланса = 1.

• Узел 35: высота левого поддерева (32) = 1, правого поддерева нет → фактор баланса = 1.

Повороты в AVL деревьях:

• Если бы, например, добавление нового элемента привело бы к тому, что разница в высотах для узла 30 или 40 стала бы больше 1, то потребовались бы повороты для балансировки дерева.

Минусы AVL деревьев:

1. Сложность реализации:

   • Реализация AVL дерева требует дополнительного кода для поддержания балансировки (повороты и вычисление факторов баланса). Это делает такие деревья более сложными для реализации, чем обычные бинарные деревья поиска.

2. Более высокая стоимость вставки и удаления:

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

3. Дополнительные вычисления:

   • Для каждого узла нужно хранить дополнительную информацию — фактор баланса. Хотя это не является большим по объему, это увеличивает потребление памяти.

4. Частые повороты:

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

5. Меньшая эффективность при работе с большими объемами данных:

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

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

НАВЕРХ

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

Красно-черное дерево — это самобалансирующееся бинарное дерево поиска (BST), в котором каждый узел имеет цвет (красный или черный) и соблюдаются специальные правила, которые помогают поддерживать баланс.

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

Свойства красно-черного дерева:

1. Каждый узел окрашен либо в красный, либо в черный цвет.

2. Корень дерева всегда черный.

3. Каждый путь от корня до листа содержит одинаковое количество черных узлов.

4. У красного узла не может быть красного родителя (двойная краснота запрещена).

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

Если при добавлении или удалении узла нарушаются правила, выполняются повороты и перекрашивания, чтобы восстановить баланс.

Пример красно-черного дерева:

       [40B]
      /      
   [20R]     [60B]
   /        /    
[10B]  [30B] [50R] [70R]

🔴 Красные узлы: 20, 50, 70

⚫ Черные узлы: 10, 30, 40, 60

• Корень (40) черный.

• У каждого красного узла родитель черный.

• Все пути от корня к листьям (10, 30, 50, 70) содержат одинаковое количество черных узлов.

Плюсы красно-черных деревьев:

1. O(log n) для поиска, вставки и удаления.

2. Балансировка менее агрессивна, чем в AVL-деревьях, что делает вставку и удаление быстрее.

3. Частые вставки и удаления происходят быстрее, чем в AVL.

4. Используются в ассоциативных массивах (например, std::map и std::set в C++).

Минусы красно-черных деревьев:

1. Чуть хуже поиск, чем в AVL-деревьях.

   • AVL-дерево всегда сильнее сбалансировано, поэтому его высота меньше, чем у красно-черного дерева. Это даёт чуть более быстрый поиск.

2. Частые перекрашивания узлов.

   • Хотя количество поворотов меньше, перекрашивания могут занимать дополнительное время.

3. Сложнее в реализации, чем обычные BST.

4. Красно-черные деревья работают хорошо в оперативной памяти, но плохо подходят для работы с диском, так как хранят очень мало данных в одной вершине.

НАВЕРХ

Б-дерево (Btree)

Б-дерево (Btree) — это самобалансирующееся дерево, используемое для хранения и поиска данных. Оно похоже на бинарное дерево, но отличается тем, что каждый узел может содержать несколько ключей и иметь больше двух потомков.

Главные особенности B-дерева:

• Балансировка – дерево всегда остается сбалансированным.

• Минимизация высоты – благодаря многим ключам в узле дерево становится “низким”.

• Эффективность поиска, вставки, удаления – все операции выполняются за O(log n).

• Идеально для работы с большими объемами данных на диске.

Правила B-дерева:

1. Один узел может содержать от t-1 до 2t-1 ключей, где t — минимальная степень дерева.

2. Корневой узел содержит от 1 до 2t-1 ключей (если он не единственный в дереве).

3. Каждый узел, кроме корня, должен содержать не менее t-1 ключей.

4. Все листья находятся на одном уровне (дерево сбалансировано).

5. Ключи внутри узла упорядочены по возрастанию.

Пример структуры B-дерева

Допустим, у нас есть B-дерево с минимальной степенью t=2, значит:

• Каждый узел может содержать от 1 до 3 ключей.

• Максимальное число дочерних узлов у одного узла — 4.

Пример B-дерева с t=2 после вставки 10, 20, 30, 40, 50, 60, 70:

        [30]
       /    
  [10,20]  [40,50,60,70]

Объяснение:

• Корень содержит 1 ключ [30].

• Левый потомок содержит [10,20] (все ключи < 30).

• Правый потомок содержит [40,50,60,70] (все ключи > 30).

Проблемы B-дерева:

• Сложная реализация – код вставки и удаления сложнее, чем у бинарного дерева.

• Неэффективно для поиска отдельных элементов в оперативной памяти – быстрее работают хеш-таблицы.

• Не идеально для последовательного поиска – Б+-дерево решает этот недостаток.

НАВЕРХ

Б+-дерево (B+tree)

Б+-дерево – это улучшенная версия B-дерева, которая используется в базах данных и файловых системах.

Главные отличия от B-дерева:

• Все данные хранятся только в листьях (внутренние узлы содержат только ключи-указатели).

• Листья связаны между собой – это позволяет эффективно искать диапазоны значений.

• Более компактные внутренние узлы, поэтому меньше занимаемой памяти, быстрее работа.

PostgreSQL использует Б+-дерево! Так что, давайте рассмотрим его структуру на примере работы btree индекса в PostgreSQL.

Б+-дерево балансируется автоматически и идеально подходит для БД, где важна работа с диапазонами и дисковыми операциями. Рекомендую также познакомиться с другими самобалансирующимися деревьями (AVL, Red-Black) и механизмами балансировки деревьев.

Почему PostgreSQL использует Б+-дерево?

В PostgreSQL индексы типа Б+-дерево (btree) используются для ускорения поиска, особенно в условиях WHERE и сортировках ORDER BY.

1. Быстрый поиск диапазонов (WHERE age BETWEEN 20 AND 40) – листья связаны в список.

2. Экономия памяти – внутренние узлы содержат только индексы, а не сами данные.

3. Быстрая индексация – обновление индексов не затрагивает сами данные.

Разница между B-деревом и Б+-деревом

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

Что такое ctid?

• ctid — это указатель на строку в таблице.

• Он содержит (номер страницы, номер строки в странице).

• Позволяет PostgreSQL быстро находить нужные строки по индексу.

• Это IO операция чтения с диска данных конкретной строки в таблице

PostgreSQL не всегда при поиске использует ctid для чтения строк. Например, если мы хотим получить все колонки из таблицы, а в индексе есть только age, то нам необходимо получить все остальные колонки этой строки прочитав их с диска в том месте на которое указывает ctid.

Поэтому в некоторых ситуациях уместно добавлять нужные колонки в индекс, например с помощью INCLUDE

CREATE INDEX idx_users_age ON users(age) INCLUDE (name);

# Полезно для такого запроса
SELECT age, name
FROM users
WHERE age = 25

# Не имеет смысла в таком запросе
# так как age есть в индексе а другие колонки не нужны
# и у нас в любом случае не будет IO операции с ctid
SELECT age
FROM users
WHERE age = 25

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

Пример 1: Индекс по одному полю

Допустим, у нас есть таблица пользователей с индексом на поле age (возраст):

CREATE TABLE users (
    id SERIAL PRIMARY KEY,
    name TEXT,
    age INT
);

CREATE INDEX idx_users_age ON users(age);

Добавляем данные:

INSERT INTO users (name, age) VALUES
('Alice', 25),
('Bob', 30),
('Charlie', 22),
('Dave', 35),
('Eve', 28);

После вставки у каждой строки есть свой ctid (страница, строка).

НАВЕРХ

Структура Б+-дерева для idx_users_age

        [25, 30]
       /       
 [22, (6,1)] → [25, (5,1)] → [28, (7,1)] → [30, (5,2)] → [35, (6,2)]

Как это работает?

1. Внутренние узлы содержат только ключи для навигации ([25, 30]).

2. Листовые узлы хранят сами данные (указатели на id записей).

3. Листья связаны между собой, что ускоряет поиск диапазонов (BETWEEN 25 AND 30).

Как отсортированы данные?

• Все ключи отсортированы по возрастанию.

• Если выполняется запрос SELECT * FROM users WHERE age > 25 ORDER BY age;, PostgreSQL просто сканирует листья справа налево.

• Поиск точного значения (WHERE age = 28) выполняется за O(log n) + O(1).

Как PostgreSQL использует ctid?

1. При запросе WHERE age = 28, PostgreSQL использует Б+-дерево, чтобы найти ключ 28.

2. Он получает ctid = (7,1).

3. PostgreSQL быстро читает строку (7,1) в таблице.

Без ctid поиск потребовал бы дополнительного хеширования или перебора!

Пример 2: Индекс по двум полям

Все описанное в примере 1, также справедливо и для индекса по 2 полям. Я лишь добавлю не много деталей для ясности.

Допустим, у нас есть индекс:

CREATE INDEX idx_users_age_name ON users(age, name);

Теперь Б+-дерево будет отсортировано по age, затем по name, но хранить в листьях ctid для быстрого доступа.

Б+-дерево для idx_users_age_name будет таким:

        [25, 30]
       /       
 [22, Charlie, (6,1)] → [25, Alice, (5,1)] → [25, Eve, (7,1)]
 → [30, Bob, (5,2)] → [30, Dave, (6,2)]

Как работает поиск?

Запрос: SELECT * FROM users WHERE age = 25 AND name = 'Eve';

1. PostgreSQL находит листовой узел с age = 25.

2. Внутри листа ищет Eve.

3. Берет ctid = (7,1).

4. Ищет строку (7,1) в таблице.

Такой поиск занимает O(log n) + O(1), потому что поиск в Б+-дереве логарифмический, а доступ по ctid моментальный.

Вывод

• Б+-дерево в PostgreSQL отсортировано по ключу индекса.

• Если один ключ, сортировка простая (по age).

• Если два ключа, сортировка идет сначала по age, потом по name.

• Поиск по диапазону (BETWEEN) выполняется очень быстро, потому что листья связаны.

• ctid – это указатель на физическую строку (страница, строка).

• В Б+-дереве PostgreSQL листья содержат ключи + ctid, а не id.

НАВЕРХ

Префиксные деревья (Tries)

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

Ключевые особенности Trie:

• Каждый узел хранит часть строки (символ).

• Все пути от корня к листьям образуют слова.

• Данные отсортированы лексикографически.

• Поиск, вставка и удаление — O(m), где m — длина слова (гораздо быстрее, чем O(log n) у B-деревьев).

Пример структуры Trie

Допустим, у нас есть список слов: “cat”, “car”, “cart”, “dog”, “dot”

Trie-структура для этих слов:

        (root)
       /     
      c       d
     /        
    a   o       o
   /|           
  t r     g       t
  | |      |
  # t      #

Расшифровка:

• c → a → t (конец слова: “cat”)

• c → a → r (часть “car”) → t (конец “cart”)

• d → o → g (конец “dog”)

• d → o → t (конец “dot”)

Trie группирует слова по общим префиксам, а не по алфавиту.

1. Все слова с одним префиксом хранятся в одном поддереве.

2. Поиск происходит сверху вниз, по символам строки.

3. Добавление и удаление слов не нарушает структуру дерева.

Где используется Trie?

• Автодополнение и поиск по словарю (Google Suggest, клавиатуры смартфонов)

• IP-адресные таблицы (маршрутизация в сетях)

• Поиск по подстрокам (например, grep)

• Сжатие данных (базовый алгоритм для сжатия Лемпеля-Зива, LZ78)

• Обнаружение спама (анализ доменных имен)

НАВЕРХ

Графы

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

Представьте карту авиаперелётов:

• Города — это узлы.

• Перелёты между городами — это связи.

• Можно лететь разными маршрутами, иногда с пересадками.

• Между некоторыми городами есть несколько маршрутов, а некоторые города связаны напрямую.

Пример графа (авиаперелёты):

        ✈ Москва ────✈ Лондон ────✈ Нью-Йорк
          │         /  |            /
          │        /   |           /
        ✈ Берлин ✈ Париж ✈ Мадрид ─✈ Чикаго
          │   /        │        /   
          │  /         │       /     
        ✈ Рим ───────✈ Барселона ─✈ Майами

• Между Москвой и Лондоном есть прямой рейс, но можно добраться через Берлин или Париж.

• Можно долететь до Нью-Йорка разными путями (через Лондон или Мадрид).

• Есть циклы — можно облететь маршрут и вернуться в исходный город.

Граф позволяет путешествовать разными маршрутами, соединяя города в сложную сеть.

НАВЕРХ

Деревья (Tree)

Дерево – это частный случай графа. Тогда как граф может быть запутанной сетью, дерево – это упорядоченная структура, где каждый элемент имеет только одного родителя.

Свойства дерева:

• Одна начальная папка (корень) – всё начинается с одной главной папки.

• Каждая папка может содержать только одну родительскую папку, но может иметь много вложенных папок и файлов.

• Никаких циклов – нельзя, чтобы папка содержала саму себя или ссылалась на вышестоящую папку.

Пример дерева (файловая система Ubuntu):

/
├── bin
├── etc
│   ├── apache2
│   ├── ssh
│   └── hosts
├── home
│   ├── user1
│   │   ├── Documents
│   │   ├── Downloads
│   │   └── Pictures
│   ├── user2
│   │   ├── Projects
│   │   └── Music
│   └── shared
├── var
│   ├── log
│   ├── www
│   └── syslog
├── tmp
└── usr
    ├── bin
    ├── lib
    └── share

• Корневой каталог (/) — это корень дерева.

• Каждая папка имеет только одного “родителя” (вложена в другую папку).

• Нет циклов — папка Documents не может ссылаться обратно на /.

НАВЕРХ

Ориентированные графы (Direct Graph)

Ориентированный граф (или директированный граф) — это граф, где рёбра имеют направление. То есть, связь между двумя узлами имеет направление от одного узла к другому. Например, это может быть направление движения по дорогам, где одна дорога ведет из города A в город B, но не наоборот (одностороннее движение).

Пример ориентированного графа (система маршрутов автобусов):

Представьте себе сеть автобусных маршрутов в городе, где каждый автобус (узел) имеет маршрут (ребро) с направлением.

        (Автобус 1) → (Автобус 2) → (Автобус 3)
           ↑               ↓              ↓
           └── (Автобус 4) ← (Автобус 5) → (Автобус 6)
                       ↑              ↘
                   (Автобус 7) → (Автобус 8)

Описание:

• Автобус 1 ссылается на Автобус 2 (направление).

• Автобус 2 ссылается на Автобус 3 (направление).

• Автобус 5 ссылается на Автобус 6 и Автобус 7 (направление).

• Автобус 4 ссылается обратно на Автобус 1, создавая цикл.

• Автобус 8 ссылается на Автобус 6, но нет обратной связи.

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

Важные свойства ориентированных графов:

1. Направление рёбер: Каждое ребро имеет направление, которое указывает от одного узла к другому.

2. Необязательная симметрия: Например, автобусы могут следовать в одном направлении, но не обязательно вернуться обратно.

Ориентированные графы используются для представления зависимостей, маршрутов или потока данных (например, маршруты в навигации, маршруты в сети и т.д.).

НАВЕРХ

Неориентированные графы (Undirected Graph)

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

Простые примеры неориентированных графов:

• Дружеские связи в соцсетях (если два человека друзья, то связь между ними двусторонняя).

• Железнодорожные пути между городами (поезда могут двигаться в обе стороны).

• Электрическая сеть (ток может течь в обе стороны в зависимости от нагрузки).

Пример: Железнодорожная сеть между городами

        Москва ─── Казань ─── Самара
          │        │       /  │  
          │        │      /   │   
    Санкт-Петербург ─ Нижний ─ Екатеринбург ─ Челябинск
          │        │         │   /
          │        │         │  /
        Мурманск ─ Псков ─── Воронеж ── Ростов

• Любой город соединён с другими городами без строгого направления — можно ехать в любом направлении.

• Некоторые города имеют несколько путей (например, Самара связана с Казанью, Нижним Новгородом и Екатеринбургом).

• Нет ограничений по движению, можно попасть из одного города в другой разными маршрутами.

НАВЕРХ

Взвешенные графы (Weighted Graph)

Взвешенный граф — это граф, в котором каждое ребро (связь) имеет вес. Вес может означать:

• Расстояние (например, километры между городами).

• Время (например, время перелета между аэропортами).

• Стоимость (например, цена доставки между складами).

Такой граф помогает находить оптимальные пути — самый короткий, самый дешевый или самый быстрый маршрут.

Пример: Авиаперелеты между городами (вес = время полета в часах)

        [Москва]
        /   |   
   3ч /    |5ч   2ч
    /     2ч     
[Париж]──4ч──[Берлин]──1ч──[Амстердам]
         |       |      /
   7ч    | 3ч    | 2ч  /6ч
         |       |    /
      [Рим]──────[Лондон]
          5ч

• Рёбра (линии) между городами имеют вес (время перелета в часах).

• Например, из Москвы в Париж можно добраться за 3 часа, а в Берлин — за 5 часов.

• Можно найти самый быстрый маршрут из Москвы в Амстердам (например, через Берлин за 6 часов).

• Если добавим цены билетов, можно искать не только самый быстрый, но и самый дешевый вариант.

НАВЕРХ

Двудольные графы (Bipartite Graph)

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

Свойства двудольного графа:

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

2. Нет связей внутри одной группы: Например, студенты не связаны друг с другом, и курсы не связаны между собой.

Простые примеры:

• Работодатели и соискатели (компании нанимают кандидатов).

• Студенты и курсы (каждый студент записан на несколько курсов).

• Футбольные команды и игроки (игроки принадлежат разным командам).

Пример: Студенты и курсы

      [Студент 1] ─── [Математика]
      [Студент 2] ─── [Физика]
      [Студент 3] ─── [Математика]
                  
                      [Программирование]
                  /
      [Студент 4] ─── [Физика]

• Студенты принадлежат к одной группе, а курсы — к другой.

• Связи (рёбра) существуют только между студентами и курсами, но не между студентами или курсами внутри своей группы.

• Например, “Студент 1” записан на “Математику”, но не на “Физику”.

• “Программирование” выбрали “Студент 3” и “Студент 2”.

НАВЕРХ

Сильно связные графы (Strongly Connected Graph)

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

Свойства сильно связных графов:

1. Из каждой вершины можно добраться до любой другой (соблюдая направления рёбер).

2. Нет “тупиковых” вершин, из которых невозможно выбраться.

Простые примеры:

• Метро с кольцевой линией (можно добраться на любую станцию, двигаясь по направлениям пересадок).

• Сеть городов с дорогами в обоих направлениях (из любого города можно доехать в любой другой).

• Интернет-сеть между серверами (если между серверами установлены соединения в обоих направлениях).

Пример: Система метрополитена с пересадками

        [Станция A] → [Станция B]
             ↑           ↓
        [Станция D] ← [Станция C] → [Станция E]
              ↑           ↓         ↘
        [Станция F] ←─────→ [Станция G]

• Из любой станции можно попасть на любую другую, следуя направлению рёбер.

• Например, из “Станции A” можно дойти до “Станции G” через “B”, “C” и “E”.

• Обратные маршруты тоже существуют (например, от “G” к “A” можно дойти через “F” и “D”).

• Граф сильно связный, так как нет изолированных узлов и в любом направлении есть путь.

Чтобы проверить, сильно ли связен ориентированный граф, лучше всего использовать:

• DFS дважды (быстро и просто).

• Алгоритм Косарайю или Тарьяна (если нужно разбиение на SCC).

• Флойд-Уоршелл (если граф маленький и удобно работать с матрицей).

Если в графе хотя бы одна вершина не достижима из другой — он не сильно связный.

НАВЕРХ

Графы с циклами (Cyclic Graph)

Граф с циклами — это граф, в котором можно вернуться в ту же вершину, двигаясь по рёбрам.

Простые примеры:

• Дорожные развязки (можно проехать по кругу и вернуться в исходную точку).

• Производственные процессы (замкнутые цепочки операций).

• Компьютерные сети (пакеты данных могут идти по кругу).

Пример: Граф с циклом:

  
         A ───→ B                             
         ↑      │                               
         │      ↓           
         D ←─── C → E                               
                ↑                                
                │
                F

В графе есть цикл:

• A → B → C → D → A

• C → E → F → C

НАВЕРХ

Графы без циклов (Acyclic Graph)

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

Простые примеры:

• Родословные деревья (от предков к потомкам, но нельзя вернуться к предкам).

• Зависимости задач (например, одна задача должна быть выполнена до другой).

• Планирование проекта (задачи должны выполняться в определённом порядке).

Пример: Зависимости задач в проекте (DAG)

       A → B → D → F
       ↓    ↓    ↓
       C → E → G

Граф без циклов: Задачи A, B, C, D, E, F и G должны выполняться в определённом порядке, но нет путей, которые приводят обратно в исходные задачи.

Задачи:

• Задача A должна быть выполнена первой.

• Задачи B и C начинаются после A.

• Задачи D и E зависят от B и C.

• Задачи F и G зависят от D и E.

Такой граф называется Directed Acyclic Graph (DAG), так как рёбра направлены, но нет циклов.

НАВЕРХ

Заключение

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

Рекомендую к изучению книгу – Грокаем алгоритмы (Адитья Бхаргава)

Если вам понравилась статья не зыбывайте голосовать. Это лучшая мотивация для меня продолжать писать статьи ;)

Сохраняйте статью в закладки. Я планирую и дальше ее дополнять примерами и редактировать описание сложных моментов.