Занятие 9

Занятие 9: Связные списки и двоичные деревья

Цели работы

  1. Связные списки.
  2. Деревья.
  3. Двоичные деревья поиска.

Связный список

Связный список – это структура данных, которая состоит из ячеек (узлов), содержащих хранимую в списке информацию и ссылку на следующую ячейку.

Удобство связного списка заключается в постоянном времени операции вставки и удаления отдельного элемента (узла): асимптотика этих операций равна $O(1)$ (для структуры list длины n асимптотика данных операций равна $O(n)$).

Первый узел в связном списке называется головой списка.

Однонаправленным связным (односвязным) списоком называется список, каждый узел которого связан только со следующим узлом: хранит ссылку только на следующий узел.

В двунаправленных списках ссылки ячеек указывают на следующий и предыдущий узлы.

На языке Python односвязный список можно реализовать с помощью словаря:

L = {
        'head': None,
        'size': 0,
    }
  • head содержит головной узел списка L
  • size хранит текущий размер списка.

Также на основе словаря можно создать узел списка:

node = {
        'value': x,
        'next': None
    }
  • value содержит произвольного типа значение узла
  • next содержит ссылку на следующий узел списка или None, если данный узел является концевым.

У определенного выше пустого списка L голова является концом, а размер равен 0.

Задание 1 – Для определенных выше списка L и узла node создайте:

  • list_create() - конструктор списка, который создаёт и возвращает пустой список
  • list_add(L, value) - функция, добавляет узел со значением value в начало списка L
In [ ]:

Деревья

Дерево состоит из вершин (узлов), которые содержат данные (ключи) и соединяются ветвями. Ветви изображают в виде стрелок, ведущих от родительской вершины к дочерней.

Корневой называется вершина, не имеющая родителя.

У каждой вершины, за исключением корневой, есть одна родительская вершина. Дочерние вершины дочерних вершин называют потомками, а родительские вершины родительских вершин — предками.

Вершины, не имеющие потомков называются листьями.

Деревья предназначены, в первую очередь, для представления иерархических структур.

Двоичные деревья поиска

Дерево называется двоичным, если каждый его узел имеет не более двух прямых потомков: левый и правый.

Двоичное дерево называется деревом двоичного поиска (binary search tree), если для каждого узла x все ключи в левом поддереве, меньше чем ключ в x, а все ключи в правом поддереве больше, чем ключ в x. Это свойство упорядоченности отличает дерево двоичного поиска от любого другого типа двоичных деревьев.

Упорядоченность ключей позволяет реализовать в двоичном дереве поиска упорядоченный обход: посещение всех узлов в ветви левого прямого потомка до посещения корня, а затем – все узлы в ветви правого прямого потомка после посещения корня. Результатом является обход узлов в отсортированном порядке в соответствии с упорядоченностью ключей.

Реализовать структуру данных "двоичное дерево" можно на основе классов: нам их понадобится создадим его:

  • класс BinarySearchTree для представления двоичного дерева

Ниже приведено описание класса BinarySearchTree:

class BinarySearchTree:
    def __init__(self):
        self.data = None # Данные, хранящиеся в узле (ключ)
        self.parent = None # Ссылка на родительский узел
        self.left = None # Левый потомок. None, если ребенка нет
        self.right = None # Правый потомок. None, если ребенка нет

Данное определение класса очевидно бесполезно, так как отсутствуют методы (функции) класса для построения и отображения дерева.

Дополним его определив метод insert(data), который позволит добавить в дерево узел, хранящий данные data:

class BinarySearchTree:
    def __init__(self):
        self.data = None # Данные, хранящиеся в узле (ключ)
        self.parent = None # Ссылка на родительский узел
        self.left = None # Левый потомок. None, если ребенка нет
        self.right = None # Правый потомок. None, если ребенка нет

    def insert(self, data):
        if self.data is None:
            self.data = data
            return

        if data == self.data:
            return
        elif data < self.data:
            if self.left != None:
                self.left.insert(data)
            else:
                self.left = BinarySearchTree()
                self.left.data = data
                self.left.parent = self
                return
        else:
            if self.right != None:
                self.right.insert(data)
            else:
                self.right = BinarySearchTree()
                self.right.data = data
                self.right.parent = self
                return

Поясним код. Бинарное дерево достраивается спуском по дереву; на каждом шаге спуска выбирается соотвествующая левая или правая ветка (в зависимости от того, меньше или больше значение data нового узла значения data, хранящегося в текущем узле дерева), пока не найдется место для вставки новой вершины (т.е ссылка на нужную ветвь равна None). Новая вершина добавляется как лист дерева, т.е. указатели на дочерние вершины left и right равны None. Если элемент уже существует в дереве, добавлять его не надо. Описанные действия соответствуют, рассмотренному на лекции операции вставить. Например, код ниже создаёт на основе определённого выше класса двоичное дерево поиска bst и добавляет в него значение '10':

bst = BinarySearchTree()
bst.insert(10)

Задача 2: Создайте дерево с узлами, хранящими значения 10, 8, 11, 5, 3, 12, 9, 7 (напишите код в ячейке ниже). Воспользуйтесь online сервисом для визуализации состояния памяти в процессе создания дерева и в результате его создания. Проанализируйте результат.

In [ ]:

Задача 3: Реализуйте операцию отыскать в виде метода find(k), который по ключу k находит узел x и возвращает указатель на него или None в случае отсутвия узла с таким ключом. Для последовательности целых чисел '10, 8, 11, 5, 3, 12, 9, 7' постройте дерево поиска и, используя метод find(k) выведите на экран информацию о ключах родителя и потомков узлов с ключами 3, 5 и 10. Продемонстрируйте код и результат его выполнения. Напомним, что операция отыскать по ключу k возвращает указатель на объект в структуре данных с ключом k, либо сообщает, что такого объекта не существует.

In [ ]:

Задача 4 Для того, чтобы иметь возможность выводить дерево на экран реализуйте операцию Вывести в отсортированном порядке в виде метода print(). Подсказка: реализуйте, рассмотренный на лекции алгоритм обхода.

Выведите на экран дерево из Задачи 2.

In [ ]:

Задача 5: Измените код метода print() из задачи 4 таким образом, чтобы он учитывал информацию о родители узла и выводил на экран информацию не только об узле x, но и об его родители (ключ родителя в скобках после ключа узла). Например: 3 (7).

In [ ]:

Задача 6: Реализуйте операции Минимум и Максимум в виде методов min() и max(). Напомним, что операция Максимум возвращает указатель на объект в структуре данных с наибольшим значением. Операция Минимум определяется аналогично. С помощью созданных методов выведите на экран минимальный и максимальный ключи для дерева из задачи 2. Подсказка: реализуйте алгоритмы, рассмиотренные на лекции.

In [ ]:

Задача 7: Реализуйте операцию Предшественник в виде метода predecessor(data). Воспользовавшись результатами задач 2-6 постройте двоичное дерево поиска для входных данных '3, 1, 5, 2, 4' и выведите на экран значение ключа предшественника узлов с ключоми '3, 2, 4, 5'. Напомним, что Предшественник по указателю на объект возвращает указатель на объект со следующим наименьшим значением значением ключа. Если объект имеет наименьший ключ, то возвращает None.

In [ ]: