Списки, деревья, графы — в чём разница и где применяются
Список, дерево, граф — три кита, на которых стоит любая алгоритмическая логика.
Они встречаются везде: от браузеров и маршрутов до очередей, файлов и рекомендаций.Разберём их с нуля: как устроены, где применяются и как реализуются.
Список (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*)
Сложности операций (список смежности):| Операция | Сложность |
|------------------ |---------------- |
| Добавление вершины | O(1) |
| Добавление ребра | O(1) |
| Поиск соседей | O(k) (где k — степень вершины) |
Сравнение структур
| Свойство | Список | Дерево | Граф |
|---|---|---|---|
| Форма | Линейная | Иерархия | Сеть |
| Связи | 1 на 1 | 1 ко многим | Произвольные |
| Циклы | Нет | Нет | Да |
| Поиск | O ( n ) | O(log n) | Зависит от алгоритма |
| Применение | Очереди, undo | ФС, индексы | Маршруты, связи |
---
Вывод
- Списки — простые и линейные, отлично подходят для очередей и стеков
- Деревья — иерархии и быстрый поиск
- Графы — универсальный инструмент для сетей и навигации
⚙ Операции: поиск, вставка и удаление в списках, деревьях и графах
Теперь добавим в практику: не просто структура, а как с ней работать.Ниже — реализации трёх базовых операций для списка, дерева и графа на 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
C:
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
C:
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, [])
C:
#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);
}
}Пример работы с графом:
C:
#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*: поиск кратчайшего пути
- Предыдущая статья цикла: Стек и очередь: фундаментальные структуры данных
