Степень дерева равна максимальной степени составляющих его узлов. Дерево, представленное на следующей диаграмме, имеет степень 2
Поддерево (Subtree)
Поддерево — это часть дерева с выбранным узлом в качестве корневого‚ а все его дочерние элементы — это узлы дерева. На диаграмме поддерево от узла E состоит из узла E в качестве корневого и узлов G и H в качестве дочерних
Концевой узел (Leaf node)
Узел в дереве без дочерних элементов называется концевым. Например, на рис. 2.8 D, G, H и F — это четыре концевых узла
Внутренний узел (Internal node)
Любой узел, который не является ни корневым, ни концевым‚ называется внутренним. У внутреннего узла имеются по крайней мере один родительский и один дочерний узлы
Терминология
Рассмотрим некоторые термины, связанные с древовидной структурой данных (табл. 2.7).
Таблица 2.7
Корневой узел (Root node)
Узел без родителя называется корневым узлом. Например, на следующей диаграмме (рис. 2.8) корневым узлом служит A. В алгоритмах корневой узел, как правило, содержит наиболее важное значение во всей древовидной структуре
Уровень узла (Level of a node)
Расстояние от корневого узла называется уровнем узла. На следующей диаграмме уровень узлов D, E и F равен двум
Узлы-братья (Siblings nodes)
Два узла в дереве называются братьями, если они расположены на одном уровне. Например, если мы взглянем на диаграмму‚ то увидим‚ что узлы B и C являются братьями
Дочерний и родительский узлы (Child and parent node)
Узел F является дочерним по отношению к узлу C, если они напрямую связаны и уровень узла C меньше уровня узла F. И наоборот, узел C является родительским для узла F. Узлы C и F на следующей диаграмме демонстрируют отношения родительского и дочернего узлов
Степень узла (Degree of a node)
Степень узла — это количество его дочерних элементов. Например, на рис. 2.8 узел B имеет степень 2
Стек
Стек — это линейная структура данных для хранения одномерного списка. Элементы в стеке могут обрабатываться по принципу LIFO (Last-In, First-Out: «последним пришел — первым ушел») либо по принципу FILO (First-In, Last-Out: «первым пришел — последним ушел». Порядок добавления и удаления элементов определяет характер стека. Новые элементы могут добавляться и удаляться только с одного конца списка.
Ниже приведены операции со стеками:
• isEmpty. Возвращает true, если стек пуст;
• push. Добавляет новый элемент;
• pop. Возвращает элемент, добавленный последним, и удаляет его.
На рис. 2.4 показано, как операции push() и pop() можно использовать для добавления и удаления данных из стека.
Вектор
Вектор — это одномерная структура для хранения данных‚ одна из самых популярных в Python. В Python имеются два способа создания векторов.
• Использование списка Python. Самый простой способ создания вектора — применить список Python следующим образом:
>>> myVector = [22,33,44,55]
>>> print(myVector)
[22 33 44 55]
>>> print(type(myVector))
Этот код создает список из четырех элементов.
• Использование массива numpy. Еще один популярный способ создания вектора — применение массивов NumPy, как показано ниже:
>>> myVector = np.array([22,33,44,55])
>>> print(myVector)
[22 33 44 55]
>>> print(type(myVector))
Обратите внимание, что мы создали MyVector, используя np.array.
В Python структуры данных — это контейнеры, позволяющие эффективно управлять данными, организовывать их и осуществлять поиск. Они организованы в коллекции — группы элементов данных, которые требуется хранить и обрабатывать совместно. В Python существуют пять различных структур данных для хранения коллекций:
• Список (List). Упорядоченная изменяемая последовательность элементов.
• Кортеж (Tuple). Упорядоченная неизменяемая последовательность элементов.
• Множество (Set). Неупорядоченная последовательность элементов.
• Словарь (Dictionary). Неупорядоченная последовательность пар «ключ — значение».
• DataFrame. Двумерная структура для хранения двумерных данных.
Давайте рассмотрим их более подробно.
Возможность четко определить признаки, которые прямо или косвенно повлияли на конкретное решение, называется объяснимостью алгоритма.
Логарифмическая временная сложность (O(logn))
Считается, что алгоритм выполняется за логарифмическое время, если время выполнения алгоритма пропорционально логарифму размера входных данных. С каждой итерацией размер входных данных уменьшается в несколько раз. Примером логарифмической временной сложности является бинарный поиск.
Другим примером квадратичной временной сложности является алгоритм сортировки пузырьком
Квадратичная временная сложность (O(n2))
Считается, что алгоритм выполняется за квадратичное время, если время выполнения алгоритма пропорционально квадрату размера входных данных. Например, простая функция, которая суммирует двумерный массив
Независимо от размера стека добавление или удаление элемента займет одно и то же время.
• Доступ к элементу хеш-таблицы.
• Блочная (иначе называемая корзинная или карманная) сортировка (Bucket sort).