Модули

Здесь вы можете ознакомится со всеми реализованными структурами данных и алгоритмами.

datastructures.sorts module

Этот модуль содержит сортировки.

datastructures.sorts.bubble_sort(arr: list, **kwargs)

Сортировка пузырьком.

_images/bubble-sort.gif
Сложность:

O(N²)

Параметры:

  • arr – Список, который требуется отсортировать.

  • kwargs –

    Дополнительные параметры для настройки поведения сортировки. Возможные параметры:

    • reverse (bool): Если установлено в True, возвращает список в обратном порядке.

    • inplace (bool): Если установлено в True, сортирует список на месте (in-place).

Результат:

Отсортированный список.

datastructures.sorts.heap_sort(arr: list, **kwargs)

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

_images/heapsort.gif
Сложность:

O(N log N)

Параметры:

  • arr – Список, который требуется отсортировать.

  • kwargs –

    Дополнительные параметры для настройки поведения сортировки.

    Возможные параметры:

    • reverse (bool): Если установлено в True, возвращает список в обратном порядке.

    • inplace (bool): Если установлено в True, сортирует список на месте (in-place).

Результат:

Отсортированный список.

datastructures.sorts.insertion_sort(arr: list, **kwargs) → list

Сортировка вставкой.

_images/insertion.gif
Сложность:

O(N²)

Параметры:

  • arr – Список, который требуется отсортировать.

  • kwargs –

    Дополнительные параметры для настройки поведения сортировки. Возможные параметры:

    • reverse (bool): Если установлено в True, возвращает список в обратном порядке.

    • inplace (bool): Если установлено в True, сортирует список на месте (in-place).

Результат:

Отсортированный список.

datastructures.sorts.merge_sort(arr: list, **kwargs) → list

Сортировка слиянием.

_images/merge.gif
Сложность:

O(N log N)

Параметры:

  • arr – Список, который требуется отсортировать.

  • kwargs –

    Дополнительные параметры для настройки поведения сортировки. Возможные параметры:

    • reverse (bool): Если установлено в True, возвращает список в обратном порядке.

    • inplace (bool): Если установлено в True, сортирует список на месте (in-place).

Результат:

Отсортированный список.

datastructures.sorts.quicksort(arr, left=None, right=None, **kwargs)

Выполняет алгоритм быстрой сортировки на входном списке.

_images/quicksort.gif
Сложность:

O(N log N)

Параметры:

  • arr – Список для сортировки.

  • left – Начальный индекс подсписка для сортировки. По умолчанию 0.

  • right – Конечный индекс подсписка для сортировки. По умолчанию len(arr) - 1.

  • kwargs –

    Дополнительные параметры для поведения сортировки.

    • inplace (bool): Если True, сортирует список на месте. По умолчанию False.

    • reverse (bool): Если True, сортирует список в обратном порядке. По умолчанию False.

Результат:

Отсортированный список.

datastructures.sorts.selection_sort(arr: list, **kwargs) → list

Сортировка выборкой.

_images/selection.gif
Сложность:

O(N²)

Параметры:

  • arr – Список, который требуется отсортировать.

  • kwargs –

    Дополнительные параметры для настройки поведения сортировки. Возможные параметры:

    • reverse (bool): Если установлено в True, возвращает список в обратном порядке.

    • inplace (bool): Если установлено в True, сортирует список на месте (in-place).

Результат:

Отсортированный список.

datastructures.strings module

Этот модуль содержит алгоритмы, связанные с работой со строками.

Грубый поиск подстроки.

_images/brute-force-string-search.gif
Сложность:

O(N * M), где N - длина строки, а M - длина подстроки

Параметры:

  • text – Исходный текст.

  • substring – искомая подстрока.

Результат:

Индекс начала подстроки в строке (если не найдено, то -1).

datastructures.strings.rabin_karp(text: str, substring: str, base=256, prime=89) → int

Алгоритм Рабина-Карпа создан для поиска подстроки в строке за линейное время. Вместо того, чтобы сравнивать строки, мы сравниваем из хэши, что позволяет проверять совпадают ли строки за O(1).

_images/rabin-karp.gif
Сложность:

O(N + M), где N - длина строки, а M - длина подстроки

Параметры:

  • text – Исходный текст.

  • substring – искомая подстрока.

  • base – количество символов в алфавите строки. По умолчанию 256 (ASCII).

  • prime – простое число для генерации хэша. По умолчанию 89.

Результат:

Индекс начала подстроки в строке (если не найдено, то -1).

datastructures.linear module

Этот модуль содержит линейные структуры данных.

class datastructures.linear.Deque

Базовые классы: Queue

Двусторонняя очередь.

_images/deque.jpg
__init__()

Инициализатор. Очередь работает с помощью DoublyLinkedList, чтобы всё работало со сложностью алгоритма O(1), вместо O(n). Такое решение было принято в связи с тем, что очереди работают на сдвигах и с крайними элементами списка. Если вы хотите работать с очередью как просто со списком, обращайтесь к параметру data: там находится DoublyLinkedList, на котором всё работает.

dequeue()

Для работы как с обычной очередью: вынуть из очереди следующий (первый) элемент.

Сложность:

O(1)

Результат:

Значение элемента, которого мы вынимаем

enqueue(item)

Для работы как с обычной очередью: поставить в очередь предмет. (Сделать последним элементом item)

Сложность:

O(1)

Параметры:

item – Значение элемента очереди, который мы ставим

peek_back()

Узнать последний элемент очереди. Он же хвост, он же конечный элемент очереди.

Сложность:

O(1)

Результат:

Последний элемент очереди

peek_front()

Узнать первый элемент очереди. Он же голова, он же следующий элемент очереди.

Сложность:

O(1)

Результат:

Первый элемент очереди

pop()

Вынуть из очереди следующий (первый) элемент.

Сложность:

O(1)

Результат:

Значение элемента, которого мы вынимаем

pop_back()

Выбрасывает из очереди последний элемент по порядку.

Сложность:

O(1)

Результат:

значение выбрасываемого элемента

pop_front()

Выбрасывает из очереди первый элемент по порядку.

Сложность:

O(1)

Результат:

значение выбрасываемого элемента

push(item)

Поставить в очередь предмет. (Сделать последним элементом item)

Сложность:

O(1)

Параметры:

item – Значение элемента очереди, который мы ставим

push_back(item)

Поставить новый элемент в конец по порядку.

Сложность:

O(1)

Параметры:

item – значение нового элемента.

push_front(item)

Поставить новый элемент в начало по порядку.

Сложность:

O(1)

Параметры:

item – значение нового элемента.

class datastructures.linear.DoublyLinkedList

Базовые классы: SinglyLinkedList

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

_images/doubly-linked-list.png
__init__()

Инициализатор.

build(data_list: list)

Преобразует входящий список в LinkedList.

Сложность:

O(n)

Параметры:

data_list – обычный список

consists(data)

Содержит ли список узел.

Сложность:

O(n)

Параметры:

data – искомое значение

Результат:

True - если содержит, иначе False

delete_at(i: int)

Удаляет узел на i-ой позиции.

Сложность:

~O(i/2)

Параметры:

i – индекс узла

Результат:

данные удаляемого узла

delete_first()

Удаляет первый узел списка.

Сложность:

O(1)

Результат:

удаляемый узел списка

delete_last()

Удаляет последний узел списка.

Сложность:

O(1)

Результат:

удаляемый узел списка

get_at(i: int)

Получить данные i-го узла.

Сложность:

O(i/2)

Параметры:

i – индекс искомого узла

Результат:

данные искомого узла

insert_at(i: int, data)

Вставляет новый узел на i-ую позицию.

Сложность:

~O(i/2)

Параметры:

  • i – индекс позиции нового узла

  • data – данные нового узла

insert_first(data)

Вставляет узел на 0-ую позицию.

Сложность:

O(1)

Параметры:

data – Данные, которые будут вставлены в список

insert_last(data)

Вставляет узел на последнюю позицию.

Сложность:

O(1)

Параметры:

data – Данные, которые будут вставлены в список

search(data)

Поиск узла.

Сложность:

O(n)

Параметры:

data – искомое значение

Результат:

индекс узла, либо -1, если узел не найден

set_at(i: int, data)

Меняет данные на data в i-ом узле.

Сложность:

O(i/2)

Параметры:

  • i – индекс узла

  • data – устанавливаемые данные

class datastructures.linear.DoublyLinkedListNode(data)

Базовые классы: SinglyLinkedListNode

Этот класс представляет собой узел двойного связанного списка (DoublyLinkedList). Он занимает в два раза больше памяти, потому что имеет указатель как и на следующий, так и на предыдущий узел.

__init__(data)

Инициализация узла

Параметры:

data – данные, которые хранит узел

earlier_node(i: int)

Рекурсивная функция обхода списка от конца до начала.

Сложность:

O(i)

Параметры:

i – номер узла последовательности от конца

Результат:

i-ый узел последовательности от конца

later_node(i: int)

Рекурсивная функция обхода списка. От начала до конца.

Сложность:

O(i)

Параметры:

i – номер узла последовательности

Результат:

i-ый узел последовательности

class datastructures.linear.Queue

Базовые классы: object

First in - First out список (FIFO). Альтернативное название: очередь. Работает так же, как очередь в пивнушке.

_images/queue.png
__init__()

Инициализатор. Очередь работает с помощью DoublyLinkedList, чтобы всё работало со сложностью алгоритма O(1), вместо O(n). Такое решение было принято в связи с тем, что очереди работают на сдвигах и с крайними элементами списка. Если вы хотите работать с очередью как просто со списком, обращайтесь к параметру data: там находится DoublyLinkedList, на котором всё работает.

dequeue()

Вынуть из очереди следующий (первый) элемент.

Сложность:

O(1)

Результат:

Значение элемента, которого мы вынимаем

enqueue(item)

Поставить в очередь предмет. (Сделать последним элементом item)

Сложность:

O(1)

Параметры:

item – Значение элемента очереди, который мы ставим

peek_back()

Узнать последний элемент очереди. Он же хвост, он же конечный элемент очереди.

Сложность:

O(1)

Результат:

Последний элемент очереди

peek_front()

Узнать первый элемент очереди. Он же голова, он же следующий элемент очереди.

Сложность:

O(1)

Результат:

Первый элемент очереди

pop()

Вынуть из очереди следующий (первый) элемент.

Сложность:

O(1)

Результат:

Значение элемента, которого мы вынимаем

push(item)

Поставить в очередь предмет. (Сделать последним элементом item)

Сложность:

O(1)

Параметры:

item – Значение элемента очереди, который мы ставим

class datastructures.linear.SinglyLinkedList

Базовые классы: object

Список связан единичными узлами (SinglyLinkedListNode): они хранят указатели только на следующий узел.

_images/singly-linked-list.png
__init__()

Инициализатор.

build(data_list: list)

Преобразует входящий список в LinkedList.

Сложность:

O(n)

Параметры:

data_list – обычный список

consists(data)

Содержит ли список узел.

Сложность:

O(n)

Параметры:

data – искомое значение

Результат:

True - если содержит, иначе False

delete_at(i: int)

Удаляет узел на i-ой позиции.

Сложность:

O(i)

Параметры:

i – индекс узла

Результат:

данные удаляемого узла

delete_first()

Удаляет первый узел списка.

Сложность:

O(1)

Результат:

удаляемый узел списка

delete_last()

Удаляет последний узел.

Сложность:

O(n)

Результат:

данные удаляемого узла

get_at(i: int)

Получить данные i-го узла.

Сложность:

O(i)

Параметры:

i – индекс искомого узла

Результат:

данные искомого узла

insert_at(i: int, data)

Вставляет новый узел на i-ую позицию.

Сложность:

O(i)

Параметры:

  • i – индекс позиции нового узла

  • data – данные нового узла

insert_first(data)

Вставляет узел на 0-ую позицию.

Сложность:

O(1)

Параметры:

data – Данные, которые будут вставлены в список

insert_last(data)

Добавляет узел в конец списка.

Сложность:

O(n)

Параметры:

data – данные нового узла

search(data)

Поиск узла.

Сложность:

O(n)

Параметры:

data – искомое значение

Результат:

индекс узла, либо -1, если узел не найден

set_at(i: int, data)

Меняет данные на data в i-ом узле.

Сложность:

O(i)

Параметры:

  • i – индекс узла

  • data – устанавливаемые данные

class datastructures.linear.SinglyLinkedListNode(data)

Базовые классы: object

Этот класс представляет собой узел связанного списка (SinglyLinkedList).

__init__(data)

Инициализация узла

Параметры:

data – данные, которые хранит узел

later_node(i: int)

Рекурсивная функция обхода списка. От начала до конца.

Сложность:

O(i)

Параметры:

i – номер узла последовательности

Результат:

i-ый узел последовательности

class datastructures.linear.Stack

Базовые классы: object

Last in - First out список (LIFO). Альтернативное название: стак/стэк. Работает так же, как и стопка тарелок.

_images/stack.png
__init__()

Инициализатор. Стак работает с помощью SinglyLinkedList, чтобы всё работало со сложностью алгоритма O(1), вместо O(n). Такое решение было принято в связи с тем, что стаки работают на сдвигах и с крайними элементами списка. Если вы хотите работать со стаком как просто со списком, обращайтесь к параметру data: там находится SinglyLinkedList, на котором всё работает.

peek()

Узнать верхний элемент.

Сложность:

O(1)

Результат:

Значение верхнего элемента

peek_bottom()

Узнать нижний элемент.

Сложность:

O(n)

Результат:

Значение нижнего элемента

pop()

Удаляет верхний элемент.

Сложность:

O(1)

Результат:

Верхний элемент, который мы удаляем

push(item)

Положить наверх стопки новый элемент.

Сложность:

O(1)

Параметры:

item – Значение элемента, которого мы хотим положить наверх стопки

class datastructures.linear.StaticArray(n: int)

Базовые классы: object

Обычный нерасширяемый список

_images/static-array.png
__init__(n: int)

Инициализация статичного списка.

Параметры:

n – Длина списка

get_at(i: int)

Получить элемент.

Сложность:

O(1)

Параметры:

i – Индекс элемента

Результат:

Данные под i-ым индексом

search(item)

Поиск данных.

Сложность:

O(n)

Параметры:

item – Искомые данные

Результат:

Индекс искомых данных

set_at(i: int, item)

Установить значение элемента.

Сложность:

O(1)

Параметры:

  • i – Индекс элемента

  • item – Значение элемента

datastructures.heap module

Этот модуль содержит кучу и приоритетную очередь, которая, в свою очередь, работает на куче.

class datastructures.heap.MinHeap(arr=None)

Базовые классы: object

Куча минимума - это бинарное дерево, где ключ каждого узла всегда меньше или равен ключам его детей. Эта структура данных позволяет эффективно вставлять, удалять и находить минимальный элемент в куче.

_images/heap.png
__init__(arr=None)

Инициализировать новую кучу минимума.

Сложность:

O(N log N), где n - количество элементов в arr.

Параметры:

arr – Необязательный итерируемый объект, содержащий начальные элементы кучи.

add(item)

Добавляет элемент в кучу.

Сложность:

O(log n), где n - количество элементов в куче.

Параметры:

item – Элемент для добавления.

count(item)

Возвращает количество вхождений указанного элемента в кучу.

Сложность:

O(n), где n - количество элементов в куче.

Параметры:

item – Элемент для подсчета.

Результат:

Количество вхождений элемента в кучу.

get_item(index)

Возвращает элемент по указанному индексу.

Сложность:

O(1).

Параметры:

index – Индекс элемента для возврата.

Результат:

Элемент по указанному индексу.

static get_left_child_index(index)

Возвращает индекс левого потомка указанного узла.

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

Индекс левого потомка узла.

static get_parent_index(index)

Возвращает индекс родителя указанного узла.

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

Индекс родителя узла.

static get_right_child_index(index)

Возвращает индекс правого потомка указанного узла.

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

Индекс правого потомка узла.

has_left_child(index) → bool

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

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

True, если узел имеет левого потомка, иначе False.

has_parent(index) → bool

Проверяет, есть ли у указанного узла родитель.

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

True, если узел имеет родителя, иначе False.

has_right_child(index) → bool

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

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

True, если узел имеет правого потомка, иначе False.

heapify_down(index=None)

Перестраивает элементы в куче вниз от указанного узла.

Сложность:

O(log n), где n - количество элементов в куче.

Параметры:

index – Индекс узла для начала. Если не указан, используется корень кучи.

heapify_up(index=None)

Перестраивает элементы в куче вверх от указанного узла.

Сложность:

O(log n), где n - количество элементов в куче.

Параметры:

index – Индекс узла для начала. Если не указан, используется последний элемент кучи.

left_child(index)

Возвращает левого потомка указанного узла.

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

Левый потомок узла.

parent(index)

Возвращает родителя указанного узла.

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

Родитель узла.

peek()

Возвращает минимальный элемент в куче без его удаления.

Сложность:

O(1).

Результат:

Минимальный элемент в куче.

poll(index=None)

Удаляет и возвращает минимальный элемент из кучи.

Сложность:

O(log n), где n - количество элементов в куче.

Параметры:

index – Индекс элемента для удаления. Если не указан, удаляется минимальный элемент.

Результат:

Минимальный элемент в куче.

right_child(index)

Возвращает правого потомка указанного узла.

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

Правый потомок узла.

class datastructures.heap.PriorityQueue(arr=None)

Базовые классы: MinHeap

Приоритетная очередь, реализованная на основе мин-кучи. Узлы двигаются в очереди по приоритету.

__init__(arr=None)

Инициализировать новую кучу минимума.

Сложность:

O(N log N), где n - количество элементов в arr.

Параметры:

arr – Необязательный итерируемый объект, содержащий начальные элементы кучи.

add(item)

Добавляет элемент в кучу.

Сложность:

O(log n), где n - количество элементов в куче.

Параметры:

item – Элемент для добавления.

count(item)

Возвращает количество вхождений указанного элемента в кучу.

Сложность:

O(n), где n - количество элементов в куче.

Параметры:

item – Элемент для подсчета.

Результат:

Количество вхождений элемента в кучу.

dequeue()

Извлекает и возвращает элемент с наивысшим приоритетом из приоритетной очереди.

Сложность:

O(log n)

Результат:

Самый приоритетный узел.

enqueue(item, priority=0)

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

Сложность:

O(log n)

Параметры:

  • item – Элемент для добавления.

  • priority – Приоритет элемента. (По умолчанию 0 – самый высокий приоритет)

get_item(index)

Возвращает элемент по указанному индексу.

Сложность:

O(1).

Параметры:

index – Индекс элемента для возврата.

Результат:

Элемент по указанному индексу.

static get_left_child_index(index)

Возвращает индекс левого потомка указанного узла.

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

Индекс левого потомка узла.

static get_parent_index(index)

Возвращает индекс родителя указанного узла.

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

Индекс родителя узла.

static get_right_child_index(index)

Возвращает индекс правого потомка указанного узла.

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

Индекс правого потомка узла.

has_left_child(index) → bool

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

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

True, если узел имеет левого потомка, иначе False.

has_parent(index) → bool

Проверяет, есть ли у указанного узла родитель.

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

True, если узел имеет родителя, иначе False.

has_right_child(index) → bool

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

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

True, если узел имеет правого потомка, иначе False.

heapify_down(index=None)

Перестраивает элементы в куче вниз от указанного узла.

Сложность:

O(log n), где n - количество элементов в куче.

Параметры:

index – Индекс узла для начала. Если не указан, используется корень кучи.

heapify_up(index=None)

Перестраивает элементы в куче вверх от указанного узла.

Сложность:

O(log n), где n - количество элементов в куче.

Параметры:

index – Индекс узла для начала. Если не указан, используется последний элемент кучи.

left_child(index)

Возвращает левого потомка указанного узла.

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

Левый потомок узла.

parent(index)

Возвращает родителя указанного узла.

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

Родитель узла.

peek()

Возвращает минимальный элемент в куче без его удаления.

Сложность:

O(1).

Результат:

Минимальный элемент в куче.

poll(index=None)

Удаляет и возвращает минимальный элемент из кучи.

Сложность:

O(log n), где n - количество элементов в куче.

Параметры:

index – Индекс элемента для удаления. Если не указан, удаляется минимальный элемент.

Результат:

Минимальный элемент в куче.

right_child(index)

Возвращает правого потомка указанного узла.

Сложность:

O(1).

Параметры:

index – Индекс узла.

Результат:

Правый потомок узла.

class datastructures.heap.PriorityQueueNode(val, priority)

Базовые классы: object

Узел приоритетной очереди.

__init__(val, priority)

datastructures.trees.nodes module

Этот модуль содержит различные узлы бинарных деревьев. Эти узы используются в , но их также можно использовать отдельно. У узлов BinaryNode и BalancingNode нет своих деревьев, но их можно использовать отдельно. Остальные узлы использовать отдельно не рекомендуется.

class datastructures.trees.nodes.AVLNode(item)

Базовые классы: BalancingNode, SearchNode

Узел дерева AVL. AVL-дерево — это сбалансированное бинарное дерево поиска, в котором для каждого узла высота его левого и правого поддерева может отличаться не более чем на 1.

Наследует функциональность как от BSTNode (для операций поиска и вставки), так и от BalancingNode (для поддержания баланса дерева).

__init__(item)

Инициализатор.

Параметры:

item – Значение узла

property data

Данные, хранящиеся внутри узла.

inorder_traversal()

Рекурсивный обход дерева по порядку (in-order traversal), также центрированный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • preorder_traversal

  • postorder_traversal

Обход дерева по умолчанию (subtree_iter.).

Алгоритм обхода по порядку:

  1. Обойти левое поддерево (рекурсивно).

  2. Выбросить (оператор yield) корень.

  3. Обойти правое поддерево (рекурсивно).

_images/inorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева по порядку.

property left

Левый ребёнок элемента.

level_order_traversal()

Обход в ширину (BFS - Breadth First Search).

Алгоритм обхода в ширину:

  1. Выбросить (оператор yield) корень.

  2. Обойти следующий слой

_images/level-order-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

maintain()

Функция вызывается после удаления или вставки узла (уже прописано в коде). Она поддерживает дерево сбалансированным за счёт rebalance Также оно проходиться вверх по дереву с той же целью.

Сложность:

O(log n)

property parent

Родитель элемента.

postorder_traversal()

Рекурсивный обход дерева по порядку (postorder traversal), также обратный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • preorder_traversal

  • inorder_traversal

Алгоритм обратного обхода:

  1. Обойти левое поддерево (рекурсивно).

  2. Обойти правое поддерево (рекурсивно).

  3. Выбросить (оператор yield) корень.

_images/postorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

predecessor()

Найти предшественника этого узла (узел, который идёт предыдущий по порядку).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Предшественник этого узла

preorder_traversal()

Рекурсивный обход дерева по порядку (preorder traversal), также прямой. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • inorder_traversal

  • postorder_traversal

Алгоритм прямого обхода:

  1. Выбросить (оператор yield) корень.

  2. Обойти левое поддерево (рекурсивно).

  3. Обойти правое поддерево (рекурсивно).

_images/preorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

rebalance()

Сбалансировать дерево, если оно слишком накренено:

  • Если накренено вправо, повернуть налево

    • Перед этим сбалансировать правое поддерево (повернуть направо) при необходимости

  • Если накренено влево, повернуть направо

    • Перед этим сбалансировать левое поддерево (повернуть налево) при необходимости

Сложность:

O(1)

property right

Правый ребёнок элемента.

skew()

Найти скос дерева. Скос - это разница между высотами поддеревьев (в данном случае высота правого минус высота левого). Если эта разница больше нуля, то дерево накренено вправо. Если эта разница меньше нуля, то дерево накренено влево. Если эта разница равна нулю, то дерево полное (не накренено).

Сложность:

O(1)

Результат:

разница высот.

subtree_delete() → Node

Рекурсивная функция удаления узла дерева.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Удаляемый узел

subtree_find(item: int)

Найти узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение искомого узла

Результат:

искомый узел

subtree_find_next(item: int)

Найти следующий узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение, после которого идет значение искомого узла

Результат:

узел, значение которого идёт после входного значения

subtree_find_prev(item: int)

Найти предыдущий узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение, перед которым идет значение искомого узла

Результат:

узел, значение которого идёт перед входным значением

subtree_first()

Получить первый по порядку узел дерева (самый левый).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Первый узел дерева

subtree_insert(new_node: Node)

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

_images/bst_insert.gif
Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

new_node – новый узел, который мы добавляем

subtree_insert_after(node: Node)

Вставить узел (node) после текущего по порядку.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

node – Узел, который мы хотим вставить после текущего

subtree_insert_before(node: Node)

Вставить узел (node) перед текущим по порядку.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

node – Узел, который мы хотим вставить перед текущим

subtree_iter()

Рекурсивный обход дерева по порядку (in-order traversal), также центрированный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Алгоритм обхода по порядку:

  1. Обойти левое поддерево (рекурсивно).

  2. Выбросить (оператор yield) корень.

  3. Обойти правое поддерево (рекурсивно).

_images/inorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева по порядку.

subtree_last()

Получить последний по порядку узел дерева (самый правый).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Последний узел дерева

subtree_rotate_left()

Функция поворота дерева налево нужна для поддержки баланса дерева. Она уменьшает скос дерева, не меняя при этом порядок узлов при обходе дерева по порядку. Функция вызывается относительно корня поддерева, которое надо повернуть. Функция вызывается при каждом обновлении дерева, см. maintain.

Алгоритм:

  1. Обозначить временные переменные для хранения узлов: root_left_subtree, pivot_left_subtree, pivot_right_subtree

  2. Поменять местами корень (root) и опорную точку (pivot). Теперь pivot - корень

  3. Сделать левым ребенком pivot’a корень (root), а правым – pivot_right_subtree

  4. Сделать левым ребёнком root’a root_left_subtree, а правым – pivot_left_subtree

  5. Не забыть поставить указатели на своих родителей для pivot_right_subtree и root_left_subtree

  6. Обновить дерево относительно pivot’a и root’a

_images/left_rotation.gif
Сложность:

O(1)

subtree_rotate_right()

Функция поворота дерева направо нужна для поддержки баланса дерева. Она уменьшает скос дерева, не меняя при этом порядок узлов при обходе дерева по порядку. Функция вызывается относительно корня поддерева, которое надо повернуть. Функция вызывается при каждом обновлении дерева, см. maintain.

Алгоритм:

  1. Обозначить временные переменные для хранения узлов: root_right_subtree, pivot_left_subtree, pivot_right_subtree

  2. Поменять местами корень (root) и опорную точку (pivot). Теперь pivot - корень

  3. Сделать правым ребенком pivot’a корень (root), а левым – pivot_left_subtree

  4. Сделать правым ребёнком root’a root_right_subtree, а левым – pivot_right_subtree

  5. Не забыть поставить указатели на своих родителей для pivot_left_subtree и root_right_subtree

  6. Обновить дерево относительно pivot’a и root’a

_images/right_rotation.gif
Сложность:

O(1)

subtree_update()

Обновляет высоту узла. Высота самого высокого ребёнка + 1.

Сложность:

O(1)

successor()

Найти преемника этого узла (узел, который идёт следующий по порядку).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Преемник этого узла

class datastructures.trees.nodes.BalancingNode(item)

Базовые классы: BinaryNode

Узел балансирующего узла.

__init__(item)

Инициализатор.

Параметры:

item – Значение узла

property data

Данные, хранящиеся внутри узла.

inorder_traversal()

Рекурсивный обход дерева по порядку (in-order traversal), также центрированный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • preorder_traversal

  • postorder_traversal

Обход дерева по умолчанию (subtree_iter.).

Алгоритм обхода по порядку:

  1. Обойти левое поддерево (рекурсивно).

  2. Выбросить (оператор yield) корень.

  3. Обойти правое поддерево (рекурсивно).

_images/inorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева по порядку.

property left

Левый ребёнок элемента.

level_order_traversal()

Обход в ширину (BFS - Breadth First Search).

Алгоритм обхода в ширину:

  1. Выбросить (оператор yield) корень.

  2. Обойти следующий слой

_images/level-order-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

maintain()

Функция вызывается после удаления или вставки узла (уже прописано в коде). Она поддерживает дерево сбалансированным за счёт rebalance Также оно проходиться вверх по дереву с той же целью.

Сложность:

O(log n)

property parent

Родитель элемента.

postorder_traversal()

Рекурсивный обход дерева по порядку (postorder traversal), также обратный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • preorder_traversal

  • inorder_traversal

Алгоритм обратного обхода:

  1. Обойти левое поддерево (рекурсивно).

  2. Обойти правое поддерево (рекурсивно).

  3. Выбросить (оператор yield) корень.

_images/postorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

predecessor()

Найти предшественника этого узла (узел, который идёт предыдущий по порядку).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Предшественник этого узла

preorder_traversal()

Рекурсивный обход дерева по порядку (preorder traversal), также прямой. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • inorder_traversal

  • postorder_traversal

Алгоритм прямого обхода:

  1. Выбросить (оператор yield) корень.

  2. Обойти левое поддерево (рекурсивно).

  3. Обойти правое поддерево (рекурсивно).

_images/preorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

rebalance()

Сбалансировать дерево, если оно слишком накренено:

  • Если накренено вправо, повернуть налево

    • Перед этим сбалансировать правое поддерево (повернуть направо) при необходимости

  • Если накренено влево, повернуть направо

    • Перед этим сбалансировать левое поддерево (повернуть налево) при необходимости

Сложность:

O(1)

property right

Правый ребёнок элемента.

skew()

Найти скос дерева. Скос - это разница между высотами поддеревьев (в данном случае высота правого минус высота левого). Если эта разница больше нуля, то дерево накренено вправо. Если эта разница меньше нуля, то дерево накренено влево. Если эта разница равна нулю, то дерево полное (не накренено).

Сложность:

O(1)

Результат:

разница высот.

subtree_delete() → Node

Рекурсивная функция удаления узла дерева.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Удаляемый узел

subtree_first()

Получить первый по порядку узел дерева (самый левый).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Первый узел дерева

subtree_insert_after(node: Node)

Вставить узел (node) после текущего по порядку.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

node – Узел, который мы хотим вставить после текущего

subtree_insert_before(node: Node)

Вставить узел (node) перед текущим по порядку.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

node – Узел, который мы хотим вставить перед текущим

subtree_iter()

Рекурсивный обход дерева по порядку (in-order traversal), также центрированный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Алгоритм обхода по порядку:

  1. Обойти левое поддерево (рекурсивно).

  2. Выбросить (оператор yield) корень.

  3. Обойти правое поддерево (рекурсивно).

_images/inorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева по порядку.

subtree_last()

Получить последний по порядку узел дерева (самый правый).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Последний узел дерева

subtree_rotate_left()

Функция поворота дерева налево нужна для поддержки баланса дерева. Она уменьшает скос дерева, не меняя при этом порядок узлов при обходе дерева по порядку. Функция вызывается относительно корня поддерева, которое надо повернуть. Функция вызывается при каждом обновлении дерева, см. maintain.

Алгоритм:

  1. Обозначить временные переменные для хранения узлов: root_left_subtree, pivot_left_subtree, pivot_right_subtree

  2. Поменять местами корень (root) и опорную точку (pivot). Теперь pivot - корень

  3. Сделать левым ребенком pivot’a корень (root), а правым – pivot_right_subtree

  4. Сделать левым ребёнком root’a root_left_subtree, а правым – pivot_left_subtree

  5. Не забыть поставить указатели на своих родителей для pivot_right_subtree и root_left_subtree

  6. Обновить дерево относительно pivot’a и root’a

_images/left_rotation.gif
Сложность:

O(1)

subtree_rotate_right()

Функция поворота дерева направо нужна для поддержки баланса дерева. Она уменьшает скос дерева, не меняя при этом порядок узлов при обходе дерева по порядку. Функция вызывается относительно корня поддерева, которое надо повернуть. Функция вызывается при каждом обновлении дерева, см. maintain.

Алгоритм:

  1. Обозначить временные переменные для хранения узлов: root_right_subtree, pivot_left_subtree, pivot_right_subtree

  2. Поменять местами корень (root) и опорную точку (pivot). Теперь pivot - корень

  3. Сделать правым ребенком pivot’a корень (root), а левым – pivot_left_subtree

  4. Сделать правым ребёнком root’a root_right_subtree, а левым – pivot_right_subtree

  5. Не забыть поставить указатели на своих родителей для pivot_left_subtree и root_right_subtree

  6. Обновить дерево относительно pivot’a и root’a

_images/right_rotation.gif
Сложность:

O(1)

subtree_update()

Обновляет высоту узла. Высота самого высокого ребёнка + 1.

Сложность:

O(1)

successor()

Найти преемника этого узла (узел, который идёт следующий по порядку).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Преемник этого узла

class datastructures.trees.nodes.BinaryNode(item)

Базовые классы: Node

Узел бинарного дерева.

__init__(item)

Инициализатор.

Параметры:

item – Значение узла

property data

Данные, хранящиеся внутри узла.

inorder_traversal()

Рекурсивный обход дерева по порядку (in-order traversal), также центрированный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • preorder_traversal

  • postorder_traversal

Обход дерева по умолчанию (subtree_iter.).

Алгоритм обхода по порядку:

  1. Обойти левое поддерево (рекурсивно).

  2. Выбросить (оператор yield) корень.

  3. Обойти правое поддерево (рекурсивно).

_images/inorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева по порядку.

property left

Левый ребёнок элемента.

level_order_traversal()

Обход в ширину (BFS - Breadth First Search).

Алгоритм обхода в ширину:

  1. Выбросить (оператор yield) корень.

  2. Обойти следующий слой

_images/level-order-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

maintain()

Функция вызывается после удаления или вставки узла (уже прописано в коде). Заготовка.

property parent

Родитель элемента.

postorder_traversal()

Рекурсивный обход дерева по порядку (postorder traversal), также обратный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • preorder_traversal

  • inorder_traversal

Алгоритм обратного обхода:

  1. Обойти левое поддерево (рекурсивно).

  2. Обойти правое поддерево (рекурсивно).

  3. Выбросить (оператор yield) корень.

_images/postorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

predecessor()

Найти предшественника этого узла (узел, который идёт предыдущий по порядку).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Предшественник этого узла

preorder_traversal()

Рекурсивный обход дерева по порядку (preorder traversal), также прямой. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • inorder_traversal

  • postorder_traversal

Алгоритм прямого обхода:

  1. Выбросить (оператор yield) корень.

  2. Обойти левое поддерево (рекурсивно).

  3. Обойти правое поддерево (рекурсивно).

_images/preorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

property right

Правый ребёнок элемента.

subtree_delete() → Node

Рекурсивная функция удаления узла дерева.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Удаляемый узел

subtree_first()

Получить первый по порядку узел дерева (самый левый).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Первый узел дерева

subtree_insert_after(node: Node)

Вставить узел (node) после текущего по порядку.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

node – Узел, который мы хотим вставить после текущего

subtree_insert_before(node: Node)

Вставить узел (node) перед текущим по порядку.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

node – Узел, который мы хотим вставить перед текущим

subtree_iter()

Рекурсивный обход дерева по порядку (in-order traversal), также центрированный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Алгоритм обхода по порядку:

  1. Обойти левое поддерево (рекурсивно).

  2. Выбросить (оператор yield) корень.

  3. Обойти правое поддерево (рекурсивно).

_images/inorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева по порядку.

subtree_last()

Получить последний по порядку узел дерева (самый правый).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Последний узел дерева

successor()

Найти преемника этого узла (узел, который идёт следующий по порядку).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Преемник этого узла

class datastructures.trees.nodes.HuffmanNode(char, freq)

Базовые классы: object

Узел дерева Хаффмана.

__init__(char, freq)

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

class datastructures.trees.nodes.Node

Базовые классы: ABC

Абстрактный класс, который описывает основные свойства узлов дерева.

__init__()
abstract property data

Данные, хранящиеся внутри узла.

abstract property left

Левый ребёнок элемента.

abstract maintain()

Обработка дерева после определённых действий (при необходимости).

abstract property parent

Родитель элемента.

abstract property right

Правый ребёнок элемента.

class datastructures.trees.nodes.RedBlackNode(item: int, color=True)

Базовые классы: SearchNode

Узел красно-чёрного дерева.

BLACK = False
RED = True
__init__(item: int, color=True)

Инициализатор.

Параметры:

item – Значение узла

property data

Данные, хранящиеся внутри узла.

property grandparent

Найти прародителя.

inorder_traversal()

Рекурсивный обход дерева по порядку (in-order traversal), также центрированный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • preorder_traversal

  • postorder_traversal

Обход дерева по умолчанию (subtree_iter.).

Алгоритм обхода по порядку:

  1. Обойти левое поддерево (рекурсивно).

  2. Выбросить (оператор yield) корень.

  3. Обойти правое поддерево (рекурсивно).

_images/inorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева по порядку.

property left

Левый ребёнок элемента.

level_order_traversal()

Обход в ширину (BFS - Breadth First Search).

Алгоритм обхода в ширину:

  1. Выбросить (оператор yield) корень.

  2. Обойти следующий слой

_images/level-order-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

maintain()

Функция вызывается после удаления или вставки узла (уже прописано в коде). Заготовка.

property parent

Родитель элемента.

postorder_traversal()

Рекурсивный обход дерева по порядку (postorder traversal), также обратный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • preorder_traversal

  • inorder_traversal

Алгоритм обратного обхода:

  1. Обойти левое поддерево (рекурсивно).

  2. Обойти правое поддерево (рекурсивно).

  3. Выбросить (оператор yield) корень.

_images/postorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

predecessor()

Найти предшественника этого узла (узел, который идёт предыдущий по порядку).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Предшественник этого узла

preorder_traversal()

Рекурсивный обход дерева по порядку (preorder traversal), также прямой. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • inorder_traversal

  • postorder_traversal

Алгоритм прямого обхода:

  1. Выбросить (оператор yield) корень.

  2. Обойти левое поддерево (рекурсивно).

  3. Обойти правое поддерево (рекурсивно).

_images/preorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

property right

Правый ребёнок элемента.

property sibling

Найти брата.

subtree_delete() → Node

Рекурсивная функция удаления узла дерева.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Удаляемый узел

subtree_find(item: int)

Найти узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение искомого узла

Результат:

искомый узел

subtree_find_next(item: int)

Найти следующий узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение, после которого идет значение искомого узла

Результат:

узел, значение которого идёт после входного значения

subtree_find_prev(item: int)

Найти предыдущий узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение, перед которым идет значение искомого узла

Результат:

узел, значение которого идёт перед входным значением

subtree_first()

Получить первый по порядку узел дерева (самый левый).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Первый узел дерева

subtree_insert(new_node: Node)

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

_images/bst_insert.gif
Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

new_node – новый узел, который мы добавляем

subtree_insert_after(node: Node)

Вставить узел (node) после текущего по порядку.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

node – Узел, который мы хотим вставить после текущего

subtree_insert_before(node: Node)

Вставить узел (node) перед текущим по порядку.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

node – Узел, который мы хотим вставить перед текущим

subtree_iter()

Рекурсивный обход дерева по порядку (in-order traversal), также центрированный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Алгоритм обхода по порядку:

  1. Обойти левое поддерево (рекурсивно).

  2. Выбросить (оператор yield) корень.

  3. Обойти правое поддерево (рекурсивно).

_images/inorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева по порядку.

subtree_last()

Получить последний по порядку узел дерева (самый правый).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Последний узел дерева

successor()

Найти преемника этого узла (узел, который идёт следующий по порядку).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Преемник этого узла

property uncle

Найти дядю.

class datastructures.trees.nodes.SearchNode(item)

Базовые классы: BinaryNode

Узел бинарного дерева поиска.

__init__(item)

Инициализатор.

Параметры:

item – Значение узла

property data

Данные, хранящиеся внутри узла.

inorder_traversal()

Рекурсивный обход дерева по порядку (in-order traversal), также центрированный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • preorder_traversal

  • postorder_traversal

Обход дерева по умолчанию (subtree_iter.).

Алгоритм обхода по порядку:

  1. Обойти левое поддерево (рекурсивно).

  2. Выбросить (оператор yield) корень.

  3. Обойти правое поддерево (рекурсивно).

_images/inorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева по порядку.

property left

Левый ребёнок элемента.

level_order_traversal()

Обход в ширину (BFS - Breadth First Search).

Алгоритм обхода в ширину:

  1. Выбросить (оператор yield) корень.

  2. Обойти следующий слой

_images/level-order-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

maintain()

Функция вызывается после удаления или вставки узла (уже прописано в коде). Заготовка.

property parent

Родитель элемента.

postorder_traversal()

Рекурсивный обход дерева по порядку (postorder traversal), также обратный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • preorder_traversal

  • inorder_traversal

Алгоритм обратного обхода:

  1. Обойти левое поддерево (рекурсивно).

  2. Обойти правое поддерево (рекурсивно).

  3. Выбросить (оператор yield) корень.

_images/postorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

predecessor()

Найти предшественника этого узла (узел, который идёт предыдущий по порядку).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Предшественник этого узла

preorder_traversal()

Рекурсивный обход дерева по порядку (preorder traversal), также прямой. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • inorder_traversal

  • postorder_traversal

Алгоритм прямого обхода:

  1. Выбросить (оператор yield) корень.

  2. Обойти левое поддерево (рекурсивно).

  3. Обойти правое поддерево (рекурсивно).

_images/preorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

property right

Правый ребёнок элемента.

subtree_delete() → Node

Рекурсивная функция удаления узла дерева.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Удаляемый узел

subtree_find(item: int)

Найти узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение искомого узла

Результат:

искомый узел

subtree_find_next(item: int)

Найти следующий узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение, после которого идет значение искомого узла

Результат:

узел, значение которого идёт после входного значения

subtree_find_prev(item: int)

Найти предыдущий узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение, перед которым идет значение искомого узла

Результат:

узел, значение которого идёт перед входным значением

subtree_first()

Получить первый по порядку узел дерева (самый левый).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Первый узел дерева

subtree_insert(new_node: Node)

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

_images/bst_insert.gif
Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

new_node – новый узел, который мы добавляем

subtree_insert_after(node: Node)

Вставить узел (node) после текущего по порядку.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

node – Узел, который мы хотим вставить после текущего

subtree_insert_before(node: Node)

Вставить узел (node) перед текущим по порядку.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

node – Узел, который мы хотим вставить перед текущим

subtree_iter()

Рекурсивный обход дерева по порядку (in-order traversal), также центрированный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Алгоритм обхода по порядку:

  1. Обойти левое поддерево (рекурсивно).

  2. Выбросить (оператор yield) корень.

  3. Обойти правое поддерево (рекурсивно).

_images/inorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева по порядку.

subtree_last()

Получить последний по порядку узел дерева (самый правый).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Последний узел дерева

successor()

Найти преемника этого узла (узел, который идёт следующий по порядку).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Преемник этого узла

class datastructures.trees.nodes.SegmentNode(item)

Базовые классы: BalancingNode

Индексируемый узел имеет параметр размера. Размер – это сумма размеров детей + 1. Это нужно для индексации узлов.

__init__(item)

Инициализатор.

Параметры:

item – Значение узла

property data

Данные, хранящиеся внутри узла.

inorder_traversal()

Рекурсивный обход дерева по порядку (in-order traversal), также центрированный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • preorder_traversal

  • postorder_traversal

Обход дерева по умолчанию (subtree_iter.).

Алгоритм обхода по порядку:

  1. Обойти левое поддерево (рекурсивно).

  2. Выбросить (оператор yield) корень.

  3. Обойти правое поддерево (рекурсивно).

_images/inorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева по порядку.

property left

Левый ребёнок элемента.

level_order_traversal()

Обход в ширину (BFS - Breadth First Search).

Алгоритм обхода в ширину:

  1. Выбросить (оператор yield) корень.

  2. Обойти следующий слой

_images/level-order-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

maintain()

Функция вызывается после удаления или вставки узла (уже прописано в коде). Она поддерживает дерево сбалансированным за счёт rebalance Также оно проходиться вверх по дереву с той же целью.

Сложность:

O(log n)

property parent

Родитель элемента.

postorder_traversal()

Рекурсивный обход дерева по порядку (postorder traversal), также обратный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • preorder_traversal

  • inorder_traversal

Алгоритм обратного обхода:

  1. Обойти левое поддерево (рекурсивно).

  2. Обойти правое поддерево (рекурсивно).

  3. Выбросить (оператор yield) корень.

_images/postorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

predecessor()

Найти предшественника этого узла (узел, который идёт предыдущий по порядку).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Предшественник этого узла

preorder_traversal()

Рекурсивный обход дерева по порядку (preorder traversal), также прямой. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Смотри также:

  • inorder_traversal

  • postorder_traversal

Алгоритм прямого обхода:

  1. Выбросить (оператор yield) корень.

  2. Обойти левое поддерево (рекурсивно).

  3. Обойти правое поддерево (рекурсивно).

_images/preorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева.

rebalance()

Сбалансировать дерево, если оно слишком накренено:

  • Если накренено вправо, повернуть налево

    • Перед этим сбалансировать правое поддерево (повернуть направо) при необходимости

  • Если накренено влево, повернуть направо

    • Перед этим сбалансировать левое поддерево (повернуть налево) при необходимости

Сложность:

O(1)

property right

Правый ребёнок элемента.

skew()

Найти скос дерева. Скос - это разница между высотами поддеревьев (в данном случае высота правого минус высота левого). Если эта разница больше нуля, то дерево накренено вправо. Если эта разница меньше нуля, то дерево накренено влево. Если эта разница равна нулю, то дерево полное (не накренено).

Сложность:

O(1)

Результат:

разница высот.

subtree_at(i)

Найти i-ый узел. Поиск происходит через размеры узлов:

  • Если размер левого ребёнка больше индекса, найти i-ый узел в левом поддереве.

  • Если размер левого ребёнка меньше индекса, найти узел в правом поддереве с индексом: индекс - размер левого ребёнка - 1.

  • Если размер левого ребенка равен индексу, вернуть текущий узел.

Сложность:

O(log n)

Параметры:

i – индекс искомого узла

Результат:

искомый узел

subtree_delete() → Node

Рекурсивная функция удаления узла дерева.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Удаляемый узел

subtree_first()

Получить первый по порядку узел дерева (самый левый).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Первый узел дерева

subtree_insert_after(node: Node)

Вставить узел (node) после текущего по порядку.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

node – Узел, который мы хотим вставить после текущего

subtree_insert_before(node: Node)

Вставить узел (node) перед текущим по порядку.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

node – Узел, который мы хотим вставить перед текущим

subtree_iter()

Рекурсивный обход дерева по порядку (in-order traversal), также центрированный. Является одним из трёх обходов в глубину (DFS - Depth First Search).

Алгоритм обхода по порядку:

  1. Обойти левое поддерево (рекурсивно).

  2. Выбросить (оператор yield) корень.

  3. Обойти правое поддерево (рекурсивно).

_images/inorder-traversal.gif
Сложность:

O(n)

Результат:

Итерационный объект, состоящий из узлов бинарного дерева по порядку.

subtree_last()

Получить последний по порядку узел дерева (самый правый).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Последний узел дерева

subtree_rotate_left()

Функция поворота дерева налево нужна для поддержки баланса дерева. Она уменьшает скос дерева, не меняя при этом порядок узлов при обходе дерева по порядку. Функция вызывается относительно корня поддерева, которое надо повернуть. Функция вызывается при каждом обновлении дерева, см. maintain.

Алгоритм:

  1. Обозначить временные переменные для хранения узлов: root_left_subtree, pivot_left_subtree, pivot_right_subtree

  2. Поменять местами корень (root) и опорную точку (pivot). Теперь pivot - корень

  3. Сделать левым ребенком pivot’a корень (root), а правым – pivot_right_subtree

  4. Сделать левым ребёнком root’a root_left_subtree, а правым – pivot_left_subtree

  5. Не забыть поставить указатели на своих родителей для pivot_right_subtree и root_left_subtree

  6. Обновить дерево относительно pivot’a и root’a

_images/left_rotation.gif
Сложность:

O(1)

subtree_rotate_right()

Функция поворота дерева направо нужна для поддержки баланса дерева. Она уменьшает скос дерева, не меняя при этом порядок узлов при обходе дерева по порядку. Функция вызывается относительно корня поддерева, которое надо повернуть. Функция вызывается при каждом обновлении дерева, см. maintain.

Алгоритм:

  1. Обозначить временные переменные для хранения узлов: root_right_subtree, pivot_left_subtree, pivot_right_subtree

  2. Поменять местами корень (root) и опорную точку (pivot). Теперь pivot - корень

  3. Сделать правым ребенком pivot’a корень (root), а левым – pivot_left_subtree

  4. Сделать правым ребёнком root’a root_right_subtree, а левым – pivot_right_subtree

  5. Не забыть поставить указатели на своих родителей для pivot_left_subtree и root_right_subtree

  6. Обновить дерево относительно pivot’a и root’a

_images/right_rotation.gif
Сложность:

O(1)

subtree_update()

Обновляет размер узла (это сумма размеров детей + 1).

Сложность:

O(1)

successor()

Найти преемника этого узла (узел, который идёт следующий по порядку).

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

Преемник этого узла

class datastructures.trees.nodes.TrieNode

Базовые классы: object

Узел префиксного дерева.

__init__()

Инициализирует узел TrieNode пустым словарём дочерних узлов и флагом is_word, установленным в False.

get_words(prefix='')

Генерирует все слова в поддереве, корнем которого является этот узел TrieNode с указанным префиксом.

Параметры:

prefix – Префикс для добавления к словам.

Результат:

Генератор, выдающий слова с указанным префиксом.

class datastructures.trees.nodes.TwoThreeTreeNode(keys=None, children=None)

Базовые классы: object

Узел 2-3 дерева.

__init__(keys=None, children=None)

Инициализатор принимает списки значений и детей.

is_full() → bool

Проверяет узел на полноту (3 элемента).

is_leaf()

Проверяет, является ли узел листом.

datastructures.trees.nodes.height(node) → int

Возвращает высоту входящего узла. Сложность алгоритма является O(1) вместо O(h), потому что каждый узел хранит в себе значение его высоты. При каждом изменении дерева это значение обновляется при необходимости.

Сложность:

O(1)

Параметры:

node – узел, высоту которого надо узнать

Результат:

высота узла и, если узла нет, -1

datastructures.trees.trees module

Этот модуль содержит реализации различных бинарных и не только деревьев.

class datastructures.trees.trees.AVLTree(tree_node_type=<class 'datastructures.trees.nodes.AVLNode'>)

Базовые классы: SearchTree

AVL дерево - бинарное балансирующее дерево поиска. Балансировка осуществляется засчёт поворотов дерева.

__init__(tree_node_type=<class 'datastructures.trees.nodes.AVLNode'>)

Инициализатор дерева с типом узлов BSTNode.

build(arr: list)

Строит дерево бинарного поиска из входящего списка.

Сложность:

O(nlog n)

Параметры:

arr – входящий список значений узлов

delete(item: int)

Удалить узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение удаляемого узла

Результат:

значение удаляемого узла

find(item: int)

Найти элемент.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – искомое значение

Результат:

значение искомого элемента, если элемент не найден возвращает None

find_max()

Максимальный элемент - последний, поэтому вызываем subtree_last

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

значение максимального узла

find_min()

Минимальный элемент - первый, поэтому вызываем subtree_first

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

значение минимального узла

find_next(item: int)

Найти элемент, идущий после данного.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение элемента, после которого идёт искомый

Результат:

значение искомого элемента, если элемент не найден возвращает None

find_prev(item: int)

Найти элемент, идущий перед данным.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение элемента, перед которым идёт искомый

Результат:

значение искомого элемента, если элемент не найден возвращает None

insert(item: int) → bool

Вставить узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение нового узла

Результат:

True, если узел был добавлен, иначе False

class datastructures.trees.trees.HuffmanTree(tree_node_type=<class 'datastructures.trees.nodes.HuffmanNode'>)

Базовые классы: _BinaryTree

Дерево Хаффмана - это структура, на которой держится алгоритм сжатия Хаффмана. Алгоритм заключается в том, что мы кодируем элементы строки по-своему: элементы, которые встречаются чаще, кодируются короче.

_images/huffman_tree.png
__init__(tree_node_type=<class 'datastructures.trees.nodes.HuffmanNode'>)

Инициализатор.

Параметры:

tree_node_type – Тип узлов дерева. По умолчанию BinaryTreeNode

build(frequency_map=None)

Построение дерева Хаффмана из словаря частот символов.

Параметры:

frequency_map – Словарь, где ключи — символы, а значения — их частоты.

decode(encoded_text)

Декодирование строки, используя дерево Хаффмана.

Параметры:

encoded_text – Закодированная строка.

Результат:

Декодированная строка.

encode(text)

Кодирование текста с использованием дерева Хаффмана.

Параметры:

text – Текст, который нужно закодировать.

Результат:

Закодированная строка.

generate_codes()

Генерация кодов Хаффмана для каждого символа на основе дерева.

Результат:

Словарь, где ключ — символ, значение — его код Хаффмана.

static get_frequency_map(s: str) → dict

Статический метод для образования словаря частот.

Параметры:

s – строка, для которой нужен словарь частот

Результат:

Словарь, где ключи — символы, а значения — их частоты

class datastructures.trees.trees.RedBlackTree

Базовые классы: SearchTree

Красно-черное дерево - это самобалансирующееся дерево бинарного поиска. Оно поддерживает балансировку за счет следующих правил:

  1. Каждый узел либо красный, либо черный.

  2. Корень всегда черный.

  3. Все листья (NULL узлы) черные.

  4. Оба ребенка каждого красного узла черные.

  5. Любой путь от узла до листьев имеет одинаковое количество черных узлов.

_images/redblack.png
__init__()

Инициализатор.

build(arr: list)

Строит дерево бинарного поиска из входящего списка.

Сложность:

O(nlog n)

Параметры:

arr – входящий список значений узлов

delete(item: int)

Удалить узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение удаляемого узла

Результат:

значение удаляемого узла

find(item: int)

Найти элемент.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – искомое значение

Результат:

значение искомого элемента, если элемент не найден возвращает None

find_max()

Максимальный элемент - последний, поэтому вызываем subtree_last

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

значение максимального узла

find_min()

Минимальный элемент - первый, поэтому вызываем subtree_first

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

значение минимального узла

find_next(item: int)

Найти элемент, идущий после данного.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение элемента, после которого идёт искомый

Результат:

значение искомого элемента, если элемент не найден возвращает None

find_prev(item: int)

Найти элемент, идущий перед данным.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение элемента, перед которым идёт искомый

Результат:

значение искомого элемента, если элемент не найден возвращает None

insert(item: int) → bool

Вставить узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение нового узла

Результат:

True, если узел был добавлен, иначе False

class datastructures.trees.trees.SearchTree(tree_node_type=<class 'datastructures.trees.nodes.SearchNode'>)

Базовые классы: _BinaryTree

Это то же самое бинарное дерево, но значения узлов будут возрастать в порядке обхода. Повторяющиеся элементы пропадают. По другому это дерево можно назвать бинарное дерево-множество или дерево бинарного поиска.

_images/bst.png

Если обойти это дерево по порядку (subtree_iter), то на выходе мы получим узлы в порядке возрастания: 2 4 6 8 9 10 11 12 14 16 18

_images/BST_complexity.png
__init__(tree_node_type=<class 'datastructures.trees.nodes.SearchNode'>)

Инициализатор дерева с типом узлов BSTNode.

build(arr: list)

Строит дерево бинарного поиска из входящего списка.

Сложность:

O(nlog n)

Параметры:

arr – входящий список значений узлов

delete(item: int)

Удалить узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение удаляемого узла

Результат:

значение удаляемого узла

find(item: int)

Найти элемент.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – искомое значение

Результат:

значение искомого элемента, если элемент не найден возвращает None

find_max()

Максимальный элемент - последний, поэтому вызываем subtree_last

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

значение максимального узла

find_min()

Минимальный элемент - первый, поэтому вызываем subtree_first

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Результат:

значение минимального узла

find_next(item: int)

Найти элемент, идущий после данного.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение элемента, после которого идёт искомый

Результат:

значение искомого элемента, если элемент не найден возвращает None

find_prev(item: int)

Найти элемент, идущий перед данным.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение элемента, перед которым идёт искомый

Результат:

значение искомого элемента, если элемент не найден возвращает None

insert(item: int) → bool

Вставить узел.

Сложность:

O(log n), (если дерево не сбалансировано - O(h))

Параметры:

item – значение нового узла

Результат:

True, если узел был добавлен, иначе False

class datastructures.trees.trees.SegmentTree(tree_node_type=<class 'datastructures.trees.nodes.SegmentNode'>)

Базовые классы: _BinaryTree

Бинарное дерево, к элементам которого можно обращаться по индексу (Sequence Binary Tree). Индексация идет по порядку обхода дерева.

__init__(tree_node_type=<class 'datastructures.trees.nodes.SegmentNode'>)

Инициализатор.

Параметры:

tree_node_type – Тип узлов дерева. По умолчанию BinaryTreeNode

build(iterable: list)

Построить дерево из входящего списка. Но алгоритм не просто поочерёдно вставлять элементы, а корнем каждого поддерева является центр среза входящего списка, что способствует балансу дерева.

Сложность:

O(n)

Параметры:

iterable – входящий список

delete_at(i)

Удаляет i-ый элемент.

Сложность:

O(log n)

Параметры:

i – индекс удаляемого узла

Результат:

значение удаляемого узла

delete_first()

Удаляет первый узел.

Сложность:

O(log n)

Результат:

значение удаляемого узла

delete_last()

Удаляет последний узел.

Сложность:

O(log n)

Результат:

значение удаляемого узла

get_at(i)

Получить i-ый узел.

Сложность:

O(log n)

Параметры:

i – индекс узла

Результат:

значение искомого узла

insert_at(i, data)

Вставить новый узел на i-ую позицию.

Сложность:

O(log n)

Параметры:

  • i – индекс нового узла

  • data – значение нового узла

insert_first(data)

Вставляет новый узел в начало дерева (0 позиция).

Сложность:

O(log n)

Параметры:

data – значение нового узла

insert_last(data)

Вставляет новый узел в конец дерева (len(self) позиция).

Сложность:

O(log n)

Параметры:

data – значение нового узла

set_at(i, data)

Установить значение i-го узла.

Сложность:

O(log n)

Параметры:

  • i – индекс узла

  • data – новое значение узла

class datastructures.trees.trees.Trie

Базовые классы: object

Trie (также известно как префиксное дерево) - это древовидная структура данных, которая хранит динамический набор или ассоциативный массив. Ключ обычно является строкой, а связанное значение часто является None.

__init__()

Инициализирует пустое дерево Trie.

get_words_with_prefix(prefix='')

Получает все слова в дереве Trie с указанным префиксом.

Параметры:

prefix – Префикс для проверки.

Результат:

Список слов с указанным префиксом.

Исключение:

TypeError – Если префикс не является строкой.

insert(*words)

Вставляет слова (строки) в дерево Trie.

Параметры:

words – Переменная длина аргумента списка слов для вставки.

Исключение:

TypeError – Если слово не является строкой.

search(word)

Ищет слово в дереве Trie.

Параметры:

word – Слово для поиска.

Результат:

True, если слово найдено, иначе False.

Исключение:

TypeError – Если слово не является строкой.

class datastructures.trees.trees.TwoThreeTree

Базовые классы: object

Дерево 2-3 - это B-дерево порядка 3.

Свойства дерева 2-3:

  • Узлы с двумя дочерними элементами называются 2-узлами. 2-узлы имеют одно значение данных и два дочерних узла.

  • Узлы с тремя детьми называются 3-узлами. 3-узлы имеют два значения данных и три дочерних узла.

  • Данные хранятся в отсортированном порядке.

  • Это сбалансированное дерево.

  • Все листовые узлы находятся на одном уровне.

  • Каждый узел может быть либо листом, либо 2-узловым, либо 3-узловым.

  • Вставка всегда выполняется в лист.

_images/2-3.jpg
__init__()

Инициализатор.

insert(key)

Вставка ключа в дерево 2-3.

Если дерево пустое, создается новый корневой узел. Если в результате вставки происходит разделение узла, то корень обновляется.

Сложность:

O(log n)

Параметры:

key – Ключ, который нужно вставить.

search(key, node=None) → bool

Поиск ключа в дереве.

Выполняет рекурсивный поиск ключа в узлах дерева. Если ключ найден, возвращает True, иначе - False.

Сложность:

O(logN)

Параметры:

  • key – Ключ, который нужно найти.

  • node – Узел, с которого начинается поиск (по умолчанию корневой узел).

Результат:

True, если ключ найден, иначе False.

datastructures.graphs module

Этот модуль содержит графы и алгоритмы, связанные с ними.

class datastructures.graphs.ListAdjacency(size: int, directed: bool = True)

Базовые классы: _GraphParent

Реализация графа через список смежности.

__init__(size: int, directed: bool = True)

Инициализатор. Создает пустой граф.

Параметры:

  • size – количество узлов / размер графа

  • directed – направленный / ненаправленный граф

a_star(from_node: int, to_node: int, heuristic: callable | None = None) -> (<class 'int'>, <class 'list'>)

Алгоритм A*. Находит самый короткий путь между двумя узлами. Этот алгоритм является усовершенствованным алгоритмом Дейкстры. Он не рассматривает все возможные пути.

_images/a_star.gif
Сложность:

O((V + E) log V), где V - количество вершин, а E - количество рёбер в худшем случае

Параметры:

  • from_node – индекс первого узла (откуда проложить маршрут)

  • to_node – индекс второго узла (куда проложить маршрут)

  • heuristic – функция эвристики для оценки стоимости пути (h(n))

Результат:

tuple (int, list) - Первый элемент – это минимальная длина маршрута - Второй элемент – это кратчайший маршрут: последовательность индексов, которые нужно посетить

add_edge(v1: int, v2: int, weight: int = 1, repeat: bool = True)

Добавить грань.

Параметры:

  • v1 – номер 1го узла

  • v2 – номер 2го узла

  • repeat – служебная переменная для избегания бесконечной рекурсии, используется для ненаправленных графов

  • weight – вес грани (его значение)

bellman_ford(from_node: int, to_node: int) -> (<class 'int'>, <class 'list'>)

Алгоритм Беллмана-Форда. Находит самый короткий путь между двумя узлами.

Не поддерживает убывающие циклы. Поддерживает отрицательные веса.

Сложность:

O(V * E), где V - количество вершин, а E - количество рёбер

Параметры:

  • from_node – индекс первого узла (откуда проложить маршрут)

  • to_node – индекс второго узла (куда проложить маршрут)

Результат:

tuple (int, list) - Первый элемент – это минимальная длина маршрута - Второй элемент – это кратчайший маршрут: последовательность индексов, которые нужно посетить

breadth_first_traversal(from_node: int)

Обход графа в ширину. (BFT – Breadth First Traversal).

_images/graph-bfs.gif
Сложность:

O(V + E), где V – количество вершин и E – количество рёбер

Параметры:

from_node – номер узла, от которого идёт проходка

Результат:

итерационный объект с номерами узлов

depth_first_traversal(from_node: int)

Обход графа в глубину. (DFT – Depth First Traversal).

_images/graph-dfs.gif
Сложность:

O(V + E), где V – количество вершин и E – количество рёбер

Параметры:

from_node – номер узла, от которого идёт проходка

Результат:

итерационный объект с номерами узлов

dijkstra(from_node: int, to_node: int) -> (<class 'int'>, <class 'list'>)

Алгоритм Дейкстры. Находит самый короткий путь между двумя узлами.

Не поддерживает отрицательные веса.

Сложность:

O((V + E) log V), где V - количество вершин

Параметры:

  • from_node – индекс первого узла (откуда проложить маршрут)

  • to_node – индекс второго узла (куда проложить маршрут)

Результат:

tuple (int, list) - Первый элемент – это минимальная длина маршрута - Второй элемент – это кратчайший маршрут: последовательность индексов, которые нужно посетить

print_adjacency()

Вывести в консоль список смежности.

remove_edge(v1: int, v2: int, repeat: bool = True) → int

Убрать грань.

Параметры:

  • v1 – номер 1го узла

  • v2 – номер 2го узла

  • repeat – служебная переменная для избегания бесконечной рекурсии, используется для ненаправленных графов

Результат:

вес удалённой грани

traversal(from_node: int, storage_type: type)

Проходка по графу.

Сложность:

O(V + E), где V – количество вершин и E – количество рёбер

Параметры:

  • from_node – номер узла, от которого идёт проходка

  • storage_type – структура, для управления узлами: очередь – если в ширину, стэк – если в глубину

Результат:

итерационный объект с номерами узлов

class datastructures.graphs.MatrixAdjacency(size: int, directed: bool = True)

Базовые классы: _GraphParent

Реализация графа через матрицу смежности.

__init__(size: int, directed: bool = True)

Инициализатор. Создает пустой граф.

Параметры:

  • size – количество узлов / размер графа

  • directed – направленный / ненаправленный граф

a_star(from_node: int, to_node: int, heuristic: callable | None = None) -> (<class 'int'>, <class 'list'>)

Алгоритм A*. Находит самый короткий путь между двумя узлами. Этот алгоритм является усовершенствованным алгоритмом Дейкстры. Он не рассматривает все возможные пути.

_images/a_star.gif
Сложность:

O((V + E) log V), где V - количество вершин, а E - количество рёбер в худшем случае

Параметры:

  • from_node – индекс первого узла (откуда проложить маршрут)

  • to_node – индекс второго узла (куда проложить маршрут)

  • heuristic – функция эвристики для оценки стоимости пути (h(n))

Результат:

tuple (int, list) - Первый элемент – это минимальная длина маршрута - Второй элемент – это кратчайший маршрут: последовательность индексов, которые нужно посетить

add_edge(v1: int, v2: int, weight: int = 1, repeat: bool = True) → None

Добавить грань.

Параметры:

  • v1 – номер 1го узла

  • v2 – номер 2го узла

  • repeat – служебная переменная для избегания бесконечной рекурсии, используется для ненаправленных графов

  • weight – вес грани (его значение)

bellman_ford(from_node: int, to_node: int) -> (<class 'int'>, <class 'list'>)

Алгоритм Беллмана-Форда. Находит самый короткий путь между двумя узлами.

Не поддерживает убывающие циклы. Поддерживает отрицательные веса.

Сложность:

O(V * E), где V - количество вершин, а E - количество рёбер

Параметры:

  • from_node – индекс первого узла (откуда проложить маршрут)

  • to_node – индекс второго узла (куда проложить маршрут)

Результат:

tuple (int, list) - Первый элемент – это минимальная длина маршрута - Второй элемент – это кратчайший маршрут: последовательность индексов, которые нужно посетить

breadth_first_traversal(from_node: int)

Обход графа в ширину. (BFT – Breadth First Traversal).

_images/graph-bfs.gif
Сложность:

O(V + E), где V – количество вершин и E – количество рёбер

Параметры:

from_node – номер узла, от которого идёт проходка

Результат:

итерационный объект с номерами узлов

depth_first_traversal(from_node: int)

Обход графа в глубину. (DFT – Depth First Traversal).

_images/graph-dfs.gif
Сложность:

O(V + E), где V – количество вершин и E – количество рёбер

Параметры:

from_node – номер узла, от которого идёт проходка

Результат:

итерационный объект с номерами узлов

dijkstra(from_node: int, to_node: int) -> (<class 'int'>, <class 'list'>)

Алгоритм Дейкстры. Находит самый короткий путь между двумя узлами.

Не поддерживает отрицательные веса.

Сложность:

O((V + E) log V), где V - количество вершин

Параметры:

  • from_node – индекс первого узла (откуда проложить маршрут)

  • to_node – индекс второго узла (куда проложить маршрут)

Результат:

tuple (int, list) - Первый элемент – это минимальная длина маршрута - Второй элемент – это кратчайший маршрут: последовательность индексов, которые нужно посетить

print_adjacency()

Вывести матрицу в консоль.

remove_edge(v1: int, v2: int, repeat: bool = True) → int

Убрать грань.

Параметры:

  • v1 – номер 1го узла

  • v2 – номер 2го узла

  • repeat – служебная переменная для избегания бесконечной рекурсии, используется для ненаправленных графов

Результат:

вес удалённой грани

traversal(from_node: int, storage_type: type)

Проходка по графу.

Сложность:

O(V + E), где V – количество вершин и E – количество рёбер

Параметры:

  • from_node – номер узла, от которого идёт проходка

  • storage_type – структура, для управления узлами: очередь – если в ширину, стэк – если в глубину

Результат:

итерационный объект с номерами узлов