Лабораторная работа 5. Бинарное дерево поиска. Обходы бинарных деревьев

Вычислительная практика I, ММФ, БГУ

Лаврова О.А., декабрь 2017

Вспомогательные сведения

Большинство алгоритмов работы с деревьями основаны на обходах (tree traversing). Полный обход дерева -- это последовательная обработка всех узлов дерева по некоторому правилу. Результатом обхода дерева является линейное упорядочение узлов.

Основные обходы:

  • Прямой обход (префиксный, левый, preorder, CLR) -- осуществляется по правилу: корень-левое поддерево-правое поддерево.
  • Центрированный обход (инфиксный, симметричный, inorder, LCR) -- осуществляется по правилу: левое поддерево-корень-правое поддерево. Является наиболее популярным обходом. Реализует сортировку числовой последовательности по возрастанию для бинарного дерева поиска.
  • Обратный обход (постфиксный, правый, postorder, LRC) -- осуществляется по правилу: левое поддерево-правое поддерево-корень. Используется для удаления дерева.

Названия обходов происходят от расположения корня по отношению к поддеревьям.

Если в представлении дерева фиксированы только ребра, ведущие от родительского узла (реализация представления в ЛР4), то существует ТОЛЬКО три обхода дерева: прямой, центрированный и обратный.

Обходы реализуются рекурсией. Итеративная реализация требует использования стека для "откладывания" на потом обработки некоторых узлов.

Центрированный обход реализует сортировку числовой последовательности для бинарного дерева поиска. Эффективность сортировки: $O(n)$ операций для обхода дерева + $O(n \log{(n)})$ для вставки $n$ элементов в бинарное дерево поиска, где $O(\log{(n)})$ операций необходимо для вставки элемента в сбалансированное дерево.

Задание 1. Центрированный обход

Напишите функцию LCR(tree), которая реализует центрированный обход для бинарного дерева поиска tree. Реализуйте обход с помощью рекурсии. Результатом функции должен быть список чисел, отсортированный по возрастанию.

Постройте в одной графической области исходный список чисел и список, полученный после центрированного обхода.

Сравните эффективность по времени сортировки последовательности из $10^3$ элементов с помощью встроенного метода sort для списков и с помощью центрированного обхода.

Реализация

In [1]:
import matplotlib.pyplot as plt
%matplotlib inline
In [2]:
f = open("VP1LR4_data_rows.txt") # числа записаны в строки и разделены пробелами

source_data = [float(x) for row in f for x in row.split(' ')]  # использование вложенных генераторов списка 
                                                               # ВАЖНО: индексация для внешнего цикла расположена внутри 
                                                               # (аналогично Table в Mathematica)

f.close()

source_data
Out[2]:
[1.0, 2.0, 0.5, 12.0, 6.0, 7.8]
In [5]:
tree = create_tree(source_data) # функция create_tree создана в ЛР4 
print(tree)

[1.0, [0.5, None, None], [2.0, None, [12.0, [6.0, None, [7.8, None, None]], None]]]

Напишите функцию LCR самостоятельно

In [2]:
def LCR(tree):
    """ центрированный обход бинарного дерева поиска: левое поддерево-корень-правое поддерево 
    
        Args:
            tree: бинарное дерево поиска
                        
        Returns:
            список, содержащий узлы дерева после обхода
    """
    Your code should be here
In [7]:
sorted_data = LCR(tree)
sorted_data
Out[7]:
[0.5, 1.0, 2.0, 6.0, 7.8, 12.0]

Визуализация

In [8]:
plt.stem(source_data,'r-', label='Initial data')
plt.plot(sorted_data,'g.-',label='Sorted data')
plt.title('Sequences of numbers')
plt.legend()
Out[8]:
<matplotlib.legend.Legend at 0x836c438>

Тест на эффективность

In [9]:
import random as rnd
In [10]:
help(rnd.uniform)

Help on method uniform in module random:

uniform(a, b) method of random.Random instance
    Get a random number in the range [a, b) or [a, b] depending on rounding.
In [11]:
rnd.uniform(0,100)
Out[11]:
32.507207541812235
In [12]:
source_data = [rnd.uniform(0,100) for i in range(10**3)]
tree = create_tree(source_data)
sorted_data = LCR(tree)
In [13]:
plt.plot(source_data,'m.', label='Initial data')
plt.plot(sorted_data,'y.-',label='Sorted data')
plt.title('Sequences of numbers')
plt.legend()
Out[13]:
<matplotlib.legend.Legend at 0x84755f8>

Встроенный метод сортировки для списков

In [14]:
source_data_copy = source_data
source_data_copy.sort()
In [15]:
plt.plot(source_data_copy,'m.')
Out[15]:
[<matplotlib.lines.Line2D at 0x8527978>]

Оцените время, необходимое на сортировку с помощью функции LCR и метода sort. Используйте подход из ЛР2.

Задание 2. Минимальное и максимальное значения последовательности

Напишите функции min(tree) и max(tree), для нахождения минимального и максимального значений бинарного дерева поиска tree. Реализуйте функции с помощью рекурсии.

Задание 3*. Прямой и обратный обходы (необязательное задание)

  • Напишите функцию CLR(tree), которая реализует прямой обход для бинарного дерева поиска tree. Реализуйте обход с помощью рекурсии.
  • Напишите функцию LRС(tree), которая реализует обратный обход для бинарного дерева поиска tree. Реализуйте обход с помощью рекурсии.