Эта статья посвящена сразу двум темам — рекурсии и бинарному дереву. Как и всегда с помощью несложных определений и пояснений разберем, что это такое и чем может быть полезно.
Начнем с рекурсии
Рекурсия — это когда функция вызывает саму себя внутри своего тела. Это способ решения задач, которые можно разбить на более мелкие подзадачи того же типа.
Аналогия: представьте зеркало, поставленное напротив другого зеркала — вы видите бесконечное отражение. В программировании мы контролируем «глубину» этого отражения.
Один из самых простых примеров, чтобы понять рекурсию, — вычисление факториала (это произведение всех натуральных чисел от 1 до n, а факториал нуля равен единице).
В коде объявляем функцию factorial(n), принимающую один параметр n. По определению факториала 0! = 1, поэтому если n = 0 или n = 1, то функция factorial возвращает единицу и перестает себя вызывать дальше. Это и будет точкой останова в нашем случае, чтобы произведение не вычислялось до бесконечности. Если же n не попадает под блок с if, то идём к строке return n * factorial(n - 1). Функция также возвращает значение, но в этот раз оно равно произведению n на результат функции factorial для преыдудщего числа (в нашем случае для 4). Таким образом выполнится 6 шагов:
- factorial(5) → 5 * factorial(4)
- factorial(4) → 4 * factorial(3)
- factorial(3) → 3 * factorial(2)
- factorial(2) → 2 * factorial(1)
- factorial(1) → возвращает 1 (базовый случай)
- Возвращаемся назад: 2 × 1 = 2 (откат к шагу 4), 3 × 2 = 6 (шаг 3), 4 × 6 = 24 (шаг 2), 5 × 24 = 120 (шаг 1).
После достижения базового случая начинается обратный процесс: функции завершаются, подставляя результаты в выражения, где они были приостановлены.
Порядок вычислений следующий:
- сначала все вызовы «накапливаются» в стеке, пока не будет достигнут базовый случай;
- затем происходит «разматывание» стека: функции последовательно завершаются, возвращая результаты.
Теперь перейдем к "более практической" части — Бинарному дереву
Бинарное дерево — это иерархическая структура данных, в которой:
- каждый элемент называется узлом;
- у каждого узла может быть не более двух «потомков» (детей) — их называют левым и правым потомком;
- верхний узел (самый первый) называется корнем дерева;
- узлы без потомков называются листьями.
В нашем примере в узле хранятся числа, но это могут быть и любые другие типы данных. Кроме этого на изображении не просто бинарное дерево, а бинарное дерево поиска (BST) — особый вид бинарного дерева с жёстким правилом расположения элементов:
- все значения в левом поддереве узла меньше его значения;
- все значения в правом поддереве узла больше его значения.
Такое расположение позволяет быстро искать элементы — это главная цель BST.
Как это работает:
- Начинаем с корня.
- Сравниваем искомое значение с текущим узлом:
если искомое меньше — идём влево (все меньшие элементы точно там);
если искомое больше — идём вправо (все большие элементы точно там);
если равно — элемент найден. - Повторяем шаги для поддерева.
Именно такое дерево мы построим на Python.
Создаем новый узел:
Функция create_node принимает значение будущего узла и возвращает сам узел в виде словаря (я выбрал такую структуру данных вместо ООП, поскольку она более простая), где ключи это value, left и right. В left и right ставим "заглушки" в виде None. Это значит, что left и right существуют, но в них пусто. Это нужно для возможности продолжать вести дерево.
Следующая функция для вставки элемента — функция insert:
Она принимает два аргумента — root и value. root — это ссылка на корневой узел дерева (или поддерева) в текущий момент выполнения функции. По сути, это:
- либо словарь с ключами 'value', 'left', 'right' (узел дерева);
- либо None (пустое дерево).
Если дерево пустое (root = None), то создаем его запуском функции create_node. Если дерево уже есть, то идём к рекурсии, которую изучили в статье ранее. Происходит проверка: если значение потомка меньше значения родителя, спускаемся в левую ветку, если больше, то вправо. Говорим, что root['left'] = insert(root['left'], value). Похоже на пример с факториалом? Значение ключа left очередного словаря root становится равным результату выполнения снова же функции insert (функция insert в функции insert это и есть рекурсия). Она в свою очередь выполняет те же действия и останавливается тогда, когда root['left'] или root['right'] (это значение ключа словаря root) окажется пустым и мы можем его заполнить с помощью create_node. Это работает так: root['left'] = None, поэтому вызываем insert(None, value) и попадаем под первое условие функции.
Разберем наглядно, как добавить очередной элемент в дерево:
Результатом root['left'] = insert(root['left'], value) в данном случае будет являться новый словарь, то есть root['left'] = {'value': 5, 'left': None, 'right': None}.
Следующая функция реализовывает поиск элемента:
Логика аналогична функции insert, только результатом будет являться True или False в зависимости от того, был ли найден элемент.
Теперь напишем функцию для вывода всех элементов дерева в отсортированном порядке:
In‑order traversal (симметричный обход) следует строгому порядку посещения узлов:
- Левое поддерево — сначала рекурсивно обходим всё левое поддерево.
- Текущий узел — добавляем значение текущего узла в результат.
- Правое поддерево — затем рекурсивно обходим правое поддерево.
Порядок: Left → Root → Right.
- Рекурсия — основной механизм обхода: функция вызывает себя для поддеревьев.
- extend — добавляет все элементы из другого списка в текущий.
- append — добавляет один элемент в конец списка.
- Базовый случай — когда root is None, функция возвращает пустой список. Это останавливает рекурсию на листьях.
И теперь создаем свое дерево на основе созданных нами конструкций:
Знание бинарных деревьев полезно, потому что:
- они дают быстрый поиск, вставку и удаление данных;
- поддерживают естественную сортировку;
- служат основой для многих реальных приложений (сжатие, графика, ОС);
- помогают моделировать иерархии (файлы, DOM, родословные);
- развивают алгоритмическое мышление и нужны для собеседований в топовые IT‑компании.
Если у вас будут вопросы, с радостью на все отвечу в комментариях!