Деревья: структура данных, которая везде

🎯 Зачем это нужно?

🔍 Google поиск - индексирует миллиарды страниц через B-деревья (поиск за доли секунды!) 🧠 Рекомендации Netflix - решающие деревья анализируют твои предпочтения
📱 Файловая система - папки и файлы организованы как дерево 🎮 ИИ в играх - minimax деревья просчитывают ходы на 10+ шагов вперед 💰 Банковские базы данных - B+ деревья обрабатывают миллионы транзакций

📚 История вопроса

В 1970 году Рудольф Байер из IBM изобрёл B-деревья, чтобы эффективно хранить данные на медленных дисках. Идея была гениальна: вместо линейного поиска (как в списке контактов) использовать “умную” иерархию.

Интересный факт: термин “дерево” в информатике появился потому, что структура действительно напоминает перевернутое дерево - корень вверху, ветви расходятся вниз! 🌳

💡 Интуиция

Представь генеалогическое дерево твоей семьи:

• Корень = самый старший предок
• Узлы = члены семьи
• Ребра = родственные связи
• Листья = те, у кого нет детей (пока что 😉)

[МЕДИА: image_01] Описание: Семейное дерево с корнем наверху, показывающее иерархическую структуру с родителями и детьми Промпт: “family tree diagram with root at top, hierarchical structure showing parent-child relationships, modern clean design, educational illustration, nodes connected by lines, suitable for computer science audience”

Или посмотри на структуру компании:

• CEO (корень) → директоры → менеджеры → сотрудники (листья)

Главная идея: один родитель, много детей. Никаких циклов - иначе начальник был бы подчинённым самого себя! 😅

📐 Формальное определение

Дерево - это связный ациклический граф с n узлами и (n-1) рёбрами.

Свойства:

• Связность: между любыми двумя узлами есть путь
• Ацикличность: нет замкнутых маршрутов
• Иерархия: есть единственный корень
• Уникальный путь: между любыми узлами ровно один путь

Терминология:

• Корень (root) - узел без родителя
• Лист (leaf) - узел без детей
• Высота - максимальная длина пути от корня до листа
• Степень узла - количество детей
• Поддерево - часть дерева, начинающаяся с некоторого узла

🔍 Основные виды деревьев

1️⃣ Бинарное дерево (Binary Tree)

Правило: у каждого узла максимум 2 ребёнка

    A
   / \
  B   C
 / \   \
D   E   F

Применение: выражения в компиляторах, поиск, сортировка

2️⃣ Дерево поиска (BST - Binary Search Tree)

Правило: левый ребёнок < родитель < правый ребёнок

[МЕДИА: image_02] Описание: Бинарное дерево поиска с числами, показывающее правило упорядочивания Промпт: “binary search tree diagram with numbers, showing left child < parent < right child rule, clean mathematical illustration, nodes with values, arrows indicating relationships”

# Поиск в BST - O(log n) вместо O(n)!
def search(root, target):
    if not root or root.val == target:
        return root
    if target < root.val:
        return search(root.left, target)  # идём влево
    return search(root.right, target)    # идём вправо

3️⃣ B-дерево (B-Tree)

Фишка: много ключей в одном узле (2-1000!)

Почему круто:

• Меньше обращений к диску - узел = блок данных
• Сбалансированность автоматически поддерживается
• Используется везде: MySQL, PostgreSQL, файловые системы

4️⃣ Решающее дерево (Decision Tree)

Суть: каждый узел = вопрос, каждый лист = решение

Покупать ли iPhone?
├─ Есть ли 100k? 
│  ├─ Да → Покупай! 🎉
│  └─ Нет → Посмотри на Android
└─ Фанат Apple?
   ├─ Да → Накопи денег
   └─ Нет → Xiaomi за 20k

🎮 Практика

Базовый уровень 🟢

Задача 1: В социальной сети 1000 пользователей. Если организовать их в BST по ID, сколько максимум сравнений нужно для поиска?

Задача 2: Почему в B-дереве узлы содержат много ключей, а не один?

Задача 3: Нарисуй BST для последовательности: [5, 3, 7, 1, 9, 4, 6]

Продвинутый уровень 🟡

Задача 4: База данных банка использует B-дерево степени 100. В узле помещается 200 счетов. Сколько узлов нужно посетить для поиска среди 10⁸ счетов?

Задача 5: Реализуй функцию подсчета высоты бинарного дерева:

def height(root):
    # твой код
    pass

Задача 6: Google использует B-деревья для хранения индекса. Почему не BST?

Челлендж 🔴

Задача 7: Netflix создаёт решающее дерево для рекомендаций. Есть признаки: возраст (18-65), жанр (комедия/драма/боевик), время просмотра (утро/день/вечер). Построй дерево для классификации на 8 групп пользователей.

Задача 8: Докажи, что в дереве с n узлами ровно (n-1) рёбер.

⚠️ Частые ошибки

❌ Ошибка: “Дерево - это граф с циклами” ✅ Правильно: Дерево всегда ациклично 💡 Почему: Цикл создал бы альтернативные пути между узлами

❌ Ошибка: “В дереве может быть несколько корней”
✅ Правильно: Корень всегда один (по определению) 💡 Почему: Иначе это лес из деревьев, а не дерево

❌ Ошибка: “BST всегда быстрее массива” ✅ Правильно: Только если дерево сбалансировано 💡 Почему: Вырожденное BST превращается в список O(n)

🎓 Главное запомнить

✅ Суть: Иерархическая структура без циклов с единственным корнем ✅ Формула: n узлов = (n-1) рёбер
✅ Применение: Поиск, иерархии, принятие решений, файловые системы

🔗 Связь с другими темами

Откуда пришли: Графы (урок 255) → убрали циклы = получили деревья Куда ведёт: Алгоритмы обхода, балансировка, хеш-таблицы, машинное обучение

В ML: Random Forest = много решающих деревьев, градиентный бустинг (XGBoost, LightGBM)