Какой граф называется деревом?

Граф: определение дерева

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

Определение дерева

Дерево — это связный неориентированный граф, который не содержит циклов.

По другому: граф называется деревом, если он удовлетворяет следующим условиям:

1. Связность — между любыми двумя вершинами существует путь
2. Отсутствие циклов — нет ни одного замкнутого маршрута вершин
3. N вершин, N-1 рёбер — если в дереве N вершин, то ровно N-1 рёбер

Эквивалентные определения

Граф является деревом тогда и только тогда когда:

• Это минимальный связный граф (если удалить любое ребро, граф становится несвязным)
• Это максимальный ациклический граф (если добавить ещё одно ребро, появится цикл)
• Между любыми двумя вершинами существует ровно один простой путь
• N вершин и N-1 рёбер, и граф связен

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

Дерево с N вершинами имеет:
- Ровно N-1 рёбер
- Ровно одну компоненту связности
- Ноль циклов
- Может быть направленным (ориентированное дерево) или неориентированным

Примеры деревьев

1. Бинарное дерево поиска (Binary Search Tree)

        5
       / \\
      3   7
     / \ / \\
    1 4 6  8

Это дерево:
- 8 вершин
- 7 рёбер (8-1)
- Нет циклов
- Связно

2. Структура файлов в ОС

root/
├── home/
│   ├── user/
│   │   ├── Documents/
│   │   └── Downloads/
│   └── admin/
└── var/
    ├── log/
    └── tmp/

Это дерево:
- Корень (root)
- Иерархическая структура
- Нет циклов

3. Организационная структура

Генеральный директор
├── VP Sales
│   ├── Regional Manager 1
│   └── Regional Manager 2
├── VP Engineering
│   ├── Engineering Lead
│   │   ├── Developer 1
│   │   └── Developer 2
│   └── QA Lead
└── VP Finance

Ориентированное дерево (Rooted Tree)

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

       A (root)
      / \\
     B   C
    / \   \\
   D  E   F

Свойства:
- Только один корень
- Каждый узел (кроме корня) имеет ровно одного родителя
- Нет циклов

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

Типы деревьев

1. Бинарное дерево

Каждый узел имеет не более 2 потомков:

public class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

2. Дерево поиска (BST)

Левый потомок < узел < правый потомок:

        5
       / \\
      3   7
     / \\ / \\
    1 4 6  8

3. Сбалансированное дерево (AVL, Red-Black)

Высота левого и правого поддеревьев различается не более чем на 1:

4. N-ary дерево

Каждый узел может иметь произвольное количество потомков:

public class NaryTreeNode {
    int value;
    List<NaryTreeNode> children;
}

5. Trie (префиксное дерево)

Для хранения строк и поиска по префиксам:

       root
      /  | \\
     a  b  c
     |     |
     p    at
     |    |
     p   s

Обход деревьев

В глубину (DFS)

public void dfs(TreeNode node) {
    if (node == null) return;
    
    // Pre-order: обработка перед рекурсией
    System.out.println(node.value);
    dfs(node.left);
    dfs(node.right);
}

В ширину (BFS)

public void bfs(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.value);
        
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
}

Где используются деревья

1. Файловые системы — иерархия папок
2. Индексы БД — B-trees, B+ trees
3. Синтаксис парсеры — Abstract Syntax Tree (AST)
4. DOM браузера — структура HTML элементов
5. Организационные структуры — иерархия должностей
6. Поиск и сортировка — Binary Search Trees
7. Приоритетные очереди — Heaps
8. Автодополнение — Trie структуры

Важное свойство для интервью

Если вам задали про граф с N вершинами и вы знаете что там N-1 рёбер и он связен — это гарантированно дерево. И обратно — если это дерево, то ровно N-1 рёбер.

// Проверка что граф — дерево
public boolean isTree(int numNodes, List<int[]> edges) {
    // Дерево имеет ровно numNodes - 1 рёбер
    if (edges.size() != numNodes - 1) return false;
    
    // Проверяем связность (через BFS/DFS)
    // Все вершины должны быть достижимы из вершины 0
    return isConnected(numNodes, edges);
}

Ключевое определение для запоминания: дерево — это связный граф без циклов с N вершинами и N-1 рёбрами.