Дерево AVL и структура данных кучи в C++

Дерево AVL и кучи в C++Дерево AVL — это бинарное дерево, сбалансированное по высоте. Каждый узел связан со сбалансированным коэффициентом, который вычисляется как разница между высотой его левого поддерева и правого поддерева.

Дерево AVL названо в честь двух его изобретателей Абельсона-Велвети и Лэндиса в 1962 году, и опубликовано в их статье “Алгоритм организации информации”.

Дерево AVL

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

Пример дерева AVL показан ниже:

Пример дерева AVL

В приведенной выше схеме дерева можно заметить, что разница в высотах левого и правого поддеревьев равна 1. Это означает, что он сбалансированный по BST. Поскольку коэффициент балансировки равен 1, это означает, что левое поддерево на один уровень выше, чем правое поддерево.

Если коэффициент балансировки равен 0, то это означает, что левое и правое поддеревья находятся на одном уровне, т.е., они имеют одинаковую высоту. Если коэффициент балансировки равен -1, то левое поддерево будет на один уровень ниже правого поддерева.

Дерево AVL управляет высотой бинарного дерева поиска и предотвращает его перекос. Когда бинарное дерево становится искаженным, это наихудший случай (O (n)) для всех операций. Используя коэффициент баланса, дерево AVL накладывает ограничение на бинарное (двоичное) дерево и, таким образом, сохраняет все операции в O (log n).

Операции с деревом AVL

Ниже приведены операции, поддерживаемые деревом AVL:

1) Вставка

Операция вставки в дереве AVL на C++ такая же, как и в бинарном дереве поиска. Единственное отличие состоит в том, что для поддержания коэффициента баланса нам нужно повернуть дерево влево или вправо, чтобы оно не стало несбалансированным.

2) Удаление

Операция удаления выполняется также, как операция удаления в бинарном дереве поиска. И снова нам нужно перебалансировать дерево, выполнив несколько поворотов дерева AVL.

Читать также:  Квалификаторы типов и классов хранения в C++

Реализация дерева AVL

Ниже приведена программа на C++ для демонстрации дерева AVL и его операций:

Вывод данных:

Порядок обхода для дерева AVL является:
4 5 8 11 12 17 18
Обход по порядку после удаления узла 5:
4 8 11 12 17 18

Применения дерева AVL

  1. Дерево AVL в основном используются для типов наборов и словарей в памяти.
  2. Дерево AVL также широко используются в приложениях баз данных, в которых меньше вставок и удалений, но есть частые запросы на требуемые данные.
  3. Дерево AVL используется в приложениях, требующих улучшенного поиска, помимо приложений базы данных.

Структура данных кучи

Куча в C++ — это специальная древовидная структура данных, представляющая собой полное бинарное дерево.

Кучи могут быть двух типов:

  • Минимальная куча: в min-heap наименьшим элементом является корень дерева, и каждый узел больше или равен его родительскому элементу.
  • Максимальная куча: в max-heap самым большим элементом является корень дерева, и каждый узел меньше или равен его родительскому элементу.

Рассмотрим следующий массив элементов:

10 20 30 40 50 60 70

Минимальная куча для вышеуказанных данных представлена ниже:

Минимальная куча

Максимальная куча, использующая вышеуказанные данные, показана ниже:

Максимальная куча

Бинарная куча в C++

Бинарная куча — это обычная реализация структуры данных кучи.

Бинарная куча обладает следующими свойствами:

  • Полное бинарное дерево — это когда все уровни полностью заполнены, за исключением, возможно, последнего уровня, и на последнем уровне осталось как можно больше ключей.
  • Бинарная куча может быть минимальной или максимальной кучей.
  • Бинарная куча — это полное двоичное дерево, и поэтому ее лучше всего представить в виде массива.

Читать также:  Деревья в C++

Давайте рассмотрим представление массива бинарной кучи:

Бинарная куча

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

Массив для вышеупомянутой бинарной кучи (Heap Arr) показан ниже:

Массив для бинарной кучи

Как показано выше, HeapArr[0] является корнем бинарной кучи. Мы можем представить другие элементы в общих чертах следующим образом:

Если HeapArr[i] является i-м узлом в бинарной куче, то индексы других узлов из i-го узла равны:

  • HeapArr [(i-1)/2] => Возвращает родительский узел.
  • HeapArr [(2*i)+1] => Возвращает левый дочерний узел.
  • HeapArr [(2*i)+2] => Возвращает правый дочерний узел.

Бинарная куча удовлетворяет “свойству упорядочения”, которое бывает двух типов, как указано ниже:

  • Свойство минимальной кучи: минимальное значение находится в корне, а значение каждого узла больше или равно его родительскому.
  • Свойство максимальной кучи: максимальное значение находится в корне, а значение каждого узла меньше или равно его родительскому.

Операции с бинарной кучей

Ниже приведены основные операции, которые выполняются с минимальной кучей. В случае максимальной кучи операции меняются соответственно.

1) Insert() – вставляет новый ключ в конец дерева. В зависимости от значения вставленного ключа нам, возможно, придется настроить кучу, не нарушая свойство кучи.

2) Delete() – удаляет ключ. Обратите внимание, что временная сложность операций вставки и удаления кучи равна O (log n).

3) DecreaseKey() – уменьшает значение ключа. Возможно, нам потребуется поддерживать свойство кучи, когда выполняется эта операция. Временная сложность операции DecreaseKey кучи также равна O (log n).

4) extractMin() – удаляет минимальный элемент из минимальной кучи. Он должен поддерживать свойство кучи после удаления минимального элемента. Таким образом, его временная сложность равна O (log n).

5) getMin() – возвращает корневой элемент минимальной кучи. Это самая простая операция, и временная сложность для этой операции равна O (1).

Читать также:  Карты в STL

Реализация структуры данных кучи

Ниже приведена реализация на C++ для демонстрации базовой функциональности min-heap:

Вывод данных:

Куча после вставки: 2 4 6 8 10 12
Корень кучи: 2
Куча после deletekey(2): 2 4 12 8 10
Минимальный элемент в куче: 2
Новый корень кучи после DecreaseKey: 1

Применение кучи

  • Кучная сортировка: алгоритм сортировки кучи эффективно реализуется с использованием бинарной кучи.
  • Очереди приоритетов: бинарная куча поддерживает все операции, необходимые для успешной реализации очередей приоритетов за O (log n) время.
  • Алгоритмы графов: некоторые алгоритмы, связанные с графами, используют приоритетную очередь, а приоритетная очередь, в свою очередь, использует бинарную кучу.
  • Сложность алгоритма быстрой сортировки в наихудшем случае может быть преодолена с помощью сортировки кучи.

Итог

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

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

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

Кучи могут быть представлены в виде массивов с 0-м элементом в качестве корня дерева. Структуры данных кучи в основном используются для реализации сортировки кучи и очередей приоритетов.

В следующей статье мы с вами поговорим о реализации графов в C++.

С Уважением, МониторБанк

Добавить комментарий