Лабораторная работа №6: Сравнение реализаций построения бинарного дерева

Цель работы

Изучение производительности итеративного и рекурсивного подходов при построении древовидных структур данных.

Задание

1. Реализовать итеративную функцию построения бинарного дерева с использованием очереди.
2. Реализовать рекурсивную функцию построения бинарного дерева.
3. Провести бенчмаркинг обеих функций для высот $h \in [1, 10]$.
4. Построить график зависимости времени выполнения от высоты дерева и сделать выводы.

Реализация

Для вычисления значений узлов использовались функции:

• Левая ветка: $f(x) = x + \frac{x}{2}$

• Правая ветка: $f(x) = x^2$

from collections import deque
import timeit
import matplotlib.pyplot as plt
import sys

sys.setrecursionlimit(5000)  # увеличиваем глубину рекурсии


# Итеративная функция для построения бинарного дерева
def bin_tree_iterative(root, height, l_b = lambda root: root + root/2, r_b = lambda root: root**2) -> dict:
    """
    Функция осуществляет построение бинарного дерева итеративным способом
    :param root: значение корня дерева
    :param height: значение высоты дерева
    :param l_b: значение левой ветки дерева
    :param r_b: значение правой ветки дерева
    :return: dict: вложенный словарь со структурой бинарного дерева
    """
    """Словарь tree, который хранит всё дерево. Ключ — значение корня дерева, значение — список дочерних узлов"""
    tree = {str(root): []}
    """Очередь, которая хранит текущие значения для вычислений: (словарь текущего узла, значение узла)"""
    q = deque([(tree, root)])
    """Цикл по высоте дерева, каждый раз создает новый уровень"""
    for i in range(height):
        """Перебираем каждый узел текущей высоты"""
        for _ in range(len(q)):
            (nodes, value) = q.popleft()

            """Вычисляем значения веток с помощью функции l_b для левой и r_b для правой"""
            left_value = l_b(value)
            right_value = r_b(value)

            """Создаём левый и правый дочерние узлы как словарь. Ключ — значение узла"""
            left_node = {str(left_value): []}
            right_node = {str(right_value): []}

            """Добавляем к текущему узлу левый и правый дочерние узлы"""
            nodes[str(value)] = [left_node, right_node]
            """Вкладываем новые значения в очередь для вычислений на следующей высоте бинарного дерева"""
            q.append((left_node, left_value))
            q.append((right_node, right_value))
        """Переход к следующему уровню"""
    return tree


# Рекурсивная функция бинарного дерева
def bin_tree_recursive(root, height, l_b=lambda x: x + x/2, r_b=lambda x: x ** 2) -> dict:
    """
    Функция реализует составление бинарного дерева
    :param root: значение корня дерева
    :param height: вводимая конечная высота, глубина дерева
    :return: вложенный словарь значений бинарного дерева
    """
    if height == 0:
        """Если текущая высота достигает введенной конечной, то возвращаем словарь с пустыми значениями"""
        return {str(root): []}
    """Левая часть дерева составляется с помощью заданной функции l_b"""
    left_tree = bin_tree_recursive(l_b(root), height - 1)
    """Правая часть дерева составляется с помощью заданной функции r_b"""
    right_tree = bin_tree_recursive(r_b(root), height - 1)
    """Возвращаем соединенные левую и правую часть дерева"""
    return {str(root): [left_tree, right_tree]}



def benchmark(func, *args, repeat=3, **kwargs):
   """
    Измеряет время выполнения функции
    :param func: функция, время выполнения которой нужно измерить
    :param args: позиционные аргументы
    :param kwargs: именованные аргументы
    :param repeat: количество повторов измерения
    :return: минимальное время выполнения среди повторов (в секундах)
    """
    times = timeit.repeat(lambda: func(*args, **kwargs), number=1, repeat=repeat)
    return min(times)


def main():
    test_data = list(range(1, 10))  # Высота дерева 1..11

    res_iterative = []
    res_recursive = []

    for h in test_data:
        # Итеративная
        res_iterative.append(benchmark(bin_tree_iterative, 2, h))

        # Рекурсивная
        try:
            res_recursive.append(benchmark(bin_tree_recursive, 2, h))
        except RecursionError:
            res_recursive.append(float("inf"))

    # Построение графика
    plt.figure(figsize=(10, 5))
    plt.plot(test_data, res_iterative, label="Итеративная реализация", linewidth=2)
    plt.plot(test_data, res_recursive, label="Рекурсивная реализация", linewidth=2)
    plt.xlabel("Высота дерева (height)")
    plt.ylabel("Время исполнения (сек)")
    plt.title("Сравнение времени построения бинарного дерева итеративным и рекурсивным способом")
    plt.legend()
    plt.show()


if __name__ == "__main__":
    main()

Результаты тестирования

При замере времени выполнения для дерева высотой 4 ($root=8$) были получены следующие результаты:

Метод	Время выполнения (сек)
Итеративный	22.115267
Рекурсивный	16.648929

Анализ

• Так как итеративная функция bin_tree_iterative использует очередь deque, чтобы последовательно обрабатывать узлы каждого уровня дерева, и не зависит от глубины рекурсии, то:

• Нет ограничения по глубине дерева;

• Сохраняется производительность даже для больших деревьев;

• Время выполнения линейно растёт с количеством узлов, но сама функция почти стабильна для всех высот дерева.

• Рекурсивная функция bin_tree_recursive реализует построение дерева с помощью рекурсии. Для маленьких высот деревьев рекурсивный метод немного быстрее, но для большой высоты дерева может возникнуть RecursionError, а также с увеличением высоты растет и время выполнения.

Вывод

1. Итеративная функция по сравнению с рекурсивной более устойчива для больших деревьев (ее график растет более плавно с увеличением высоты дерева).

2. Для практических задач с глубокой структурой дерева лучше использовать итеративный подход.