Цикл статей: Алгоритмы, изучение, примеры на C и Python, нюансы использования

Списки, деревья, графы — в чём разница и где применяются

Список, дерево, граф — три кита, на которых стоит любая алгоритмическая логика.

Они встречаются везде: от браузеров и маршрутов до очередей, файлов и рекомендаций.

Разберём их с нуля: как устроены, где применяются и как реализуются.

Список (List)

Линейная структура: каждый элемент знает своего соседа.

Применяется:

Очереди задач
Буферы сообщений
История действий

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

| Операция | Сложность |
|----------------|-----------|
| Поиск по значению | O( n ) |
| Добавление в начало | O(1) |
| Добавление в конец (односвязный) | O( n ) |

---

Дерево (Tree)

Иерархическая структура: каждый узел может иметь несколько потомков.
Особый случай — двоичное дерево поиска (BST).

Пример BST:

Код:

      10
      /  \
     5    15
    / \     \
   2   7     20

Применяется:

Файловые системы
Словари и индексы
Сжатие данных (Huffman)
DOM-дерево

Сложности операций (BST):

| Операция | Среднее | Худшее (несбаланс) |
|------------|--------- |------------------------|
| Поиск | O(log n) | O ( n ) |
| Вставка | O(log n) | O ( n ) |
| Удаление | O(log n) | O ( n ) |
---

Граф (Graph)

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

Пример графа:

Граф — это множество вершин (nodes) и рёбер (edges), которые соединяют эти вершины.

Бывает:

Ориентированный (стрелки: A → B)
Неориентированный (двусторонние связи: A — B)

Применяется:

Навигация и маршруты
Социальные сети (связи)
Анализ зависимостей
Поиск путей (Dijkstra, A*)

Сравнение структур

Свойство	Список	Дерево	Граф
Форма	Линейная	Иерархия	Сеть
Связи	1 на 1	1 ко многим	Произвольные
Циклы	Нет	Нет	Да
Поиск	O ( n )	O(log n)	Зависит от алгоритма
Применение	Очереди, undo	ФС, индексы	Маршруты, связи

---

Вывод

Списки — простые и линейные, отлично подходят для очередей и стеков
Деревья — иерархии и быстрый поиск
Графы — универсальный инструмент для сетей и навигации

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

⚙ Операции: поиск, вставка и удаление в списках, деревьях и графах

Теперь добавим в практику: не просто структура, а как с ней работать.
Ниже — реализации трёх базовых операций для списка, дерева и графа на Python и C.
---

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

Python:

Python:

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def insert(head, value):
    new_node = Node(value)
    new_node.next = head
    return new_node  # новый head

def find(head, value):
    while head:
        if head.val == value:
            return True
        head = head.next
    return False

def delete(head, value):
    dummy = Node(0)
    dummy.next = head
    prev, curr = dummy, head
    while curr:
        if curr.val == value:
            prev.next = curr.next
            break
        prev, curr = curr, curr.next
    return dummy.next

typedef struct Node {
    int val;
    struct Node* next;
} Node;

Node* insert(Node* head, int value) {
    Node* n = malloc(sizeof(Node));
    n->val = value;
    n->next = head;
    return n;
}

int find(Node* head, int value) {
    while (head) {
        if (head->val == value) return 1;
        head = head->next;
    }
    return 0;
}

Node* delete(Node* head, int value) {
    Node dummy = {.next = head};
    Node* prev = &dummy;
    Node* curr = head;
    while (curr) {
        if (curr->val == value) {
            prev->next = curr->next;
            free(curr);
            break;
        }
        prev = curr;
        curr = curr->next;
    }
    return dummy.next;
}

---

Двоичное дерево поиска (BST)

Python:

Python:

class Node:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

def insert(root, key):
    if not root:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

def search(root, key):
    if not root or root.key == key:
        return root
    return search(root.left, key) if key < root.key else search(root.right, key)

def delete(root, key):
    if not root:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        temp = root.right
        while temp.left:
            temp = temp.left
        root.key = temp.key
        root.right = delete(root.right, temp.key)
    return root

typedef struct Node {
    int key;
    struct Node *left, *right;
} Node;

Node* new_node(int key) {
    Node* node = malloc(sizeof(Node));
    node->key = key;
    node->left = node->right = NULL;
    return node;
}

Node* insert(Node* root, int key) {
    if (!root) return new_node(key);
    if (key < root->key)
        root->left = insert(root->left, key);
    else
        root->right = insert(root->right, key);
    return root;
}

Node* search(Node* root, int key) {
    if (!root || root->key == key) return root;
    return (key < root->key) ? search(root->left, key) : search(root->right, key);
}

Node* min_value_node(Node* node) {
    while (node->left) node = node->left;
    return node;
}

Node* delete(Node* root, int key) {
    if (!root) return NULL;
    if (key < root->key)
        root->left = delete(root->left, key);
    else if (key > root->key)
        root->right = delete(root->right, key);
    else {
        if (!root->left) {
            Node* temp = root->right;
            free(root); return temp;
        } else if (!root->right) {
            Node* temp = root->left;
            free(root); return temp;
        }
        Node* temp = min_value_node(root->right);
        root->key = temp->key;
        root->right = delete(root->right, temp->key);
    }
    return root;
}

---

Граф (ориентированный, список смежности)

Python:

Python:

graph = {}

def add_vertex(v):
    if v not in graph:
        graph[v] = []

def add_edge(u, v):
    graph[u].append(v)

def remove_edge(u, v):
    if v in graph[u]:
        graph[u].remove(v)

def has_edge(u, v):
    return v in graph.get(u, [])

#define MAX 100
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* adj[MAX];

void add_edge(int u, int v) {
    Node* n = malloc(sizeof(Node));
    n->vertex = v;
    n->next = adj[u];
    adj[u] = n;
}

int has_edge(int u, int v) {
    Node* cur = adj[u];
    while (cur) {
        if (cur->vertex == v) return 1;
        cur = cur->next;
    }
    return 0;
}

void remove_edge(int u, int v) {
    Node** cur = &adj[u];
    while (*cur) {
        if ((*cur)->vertex == v) {
            Node* tmp = *cur;
            *cur = (*cur)->next;
            free(tmp);
            return;
        }
        cur = &((*cur)->next);
    }
}

Пример работы с графом:

#include <stdio.h>
#include <stdlib.h>

#define N 4 // кол-во вершин: A, B, C, D

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* graph[N]; // массив смежности

void add_edge(int from, int to) {
    Node* n = malloc(sizeof(Node));
    n->vertex = to;
    n->next = graph[from];
    graph[from] = n;
}

void print_graph() {
    char labels[] = {'A', 'B', 'C', 'D'};
    for (int i = 0; i < N; i++) {
        printf("%c -> ", labels[i]);
       Node* temp = graph[i];
       while (temp) {
           printf("%c ", labels[temp->vertex]);
           temp = temp->next;
      }
      printf("\n");
   }
}

int main() {
    add_edge(0, 1); // A → B
    add_edge(0, 2); // A → C
    add_edge(1, 3); // B → D
    add_edge(2, 3); // C → D

    print_graph();
    return 0;

}

---

Вывод

Знать структуру — мало. Нужно уметь с ней работать:
добавлять, искать, удалять.

Список — простейшая динамика
Дерево — база для логарифмичного поиска
⚙ Граф — мощный инструмент моделирования отношений

А ты с какой из этих структур работал чаще всего? Умеешь реализовать их сам или всегда используешь стандартные библиотеки? Делись опытом!

: Следующая страница цикла: Алгоритмы Дейкстры и A*: поиск кратчайшего пути

: Предыдущая статья цикла: Стек и очередь: фундаментальные структуры данных

⚖ Quick Sort vs Merge Sort: что выбрать?

Два самых популярных алгоритма сортировки — Quick Sort и Merge Sort.
Они оба работают за O(n log n) в среднем, но отличаются подходом, памятью и поведением в худших случаях.

---

Сравнительная таблица

Критерий	Quick Sort	Merge Sort
Средняя сложность	O(n log n)	O(n log n)
Худший случай	O(n²)	O(n log n)
Доп. память	O(log n) (стек вызовов)	O( n )
Стабильность	Нет	Да
Тип алгоритма	Разделение (Partitioning)	Слияние (Divide & Merge)
Подходит для	Большие массивы, если важна скорость	Сортировка связанных структур, гарантии времени
Сортирует на месте	Да	Нет (в классической реализации)

Что выбрать?

Quick Sort хорош, если:

Не нужна стабильность
Важна скорость и минимальная память
Массив — случайный или не отсортированный

Merge Sort лучше, если:

Нужна стабильность (например, сортировка по нескольким критериям)
Работаешь с связанными списками
Требуется предсказуемое поведение даже в худшем случае

А ты чаще используешь быструю сортировку или слиянием? Почему? Делись кейсами!

📡 Наши контакты

Выберите страницу

Списки, деревья, графы — в чём разница и где применяются

Список, дерево, граф — три кита, на которых стоит любая алгоритмическая логика.

Список (List)

Дерево (Tree)

Граф (Graph)

Сравнение структур

Вывод

⚙ Операции: поиск, вставка и удаление в списках, деревьях и графах

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

Двоичное дерево поиска (BST)

Граф (ориентированный, список смежности)

Вывод

Комментарии

0x42

⚖ Quick Sort vs Merge Sort: что выбрать?

Сравнительная таблица

Что выбрать?

ОГЛАВЛЕНИЕ

Информация о статье

Больше от 0x42

Поделиться этой страницей статьи

📡 Наши контакты

Цикл статей: Алгоритмы, изучение, примеры на C и Python, нюансы использования

Списки, деревья, графы — в чём разница и где применяются

Список, дерево, граф — три кита, на которых стоит любая алгоритмическая логика.​

Список (List)​

Дерево (Tree)​

Граф (Graph)​

Сравнение структур​

Вывод​

⚙ Операции: поиск, вставка и удаление в списках, деревьях и графах​

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

Двоичное дерево поиска (BST)​

Граф (ориентированный, список смежности)​

Вывод​

Комментарии

⚖ Quick Sort vs Merge Sort: что выбрать?​

Сравнительная таблица​

Что выбрать?​

ОГЛАВЛЕНИЕ

Информация о статье

Больше от 0x42

Поделиться этой страницей статьи

Список, дерево, граф — три кита, на которых стоит любая алгоритмическая логика.

Список (List)

Дерево (Tree)

Граф (Graph)

Сравнение структур

Вывод

⚙ Операции: поиск, вставка и удаление в списках, деревьях и графах

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

Двоичное дерево поиска (BST)

Граф (ориентированный, список смежности)

Вывод

⚖ Quick Sort vs Merge Sort: что выбрать?

Сравнительная таблица

Что выбрать?