Куча

Имеется список целых чисел 5, 1, 7, 3, 9, 2, 8. Построим два дерева, в которых каждому узлу соответствует одно из значений этого списка, причем первое дерево будет организованно нисходящей иерархией, а второе - восходящей (рис. 5.11).

Рис. 5.11. Кучи

Два получившихся дерева полностью удовлетворяют свойству кучи: если N является узлом-предком относительно М, а М соответственно узлом-потомком узла N, то для max-кучи всегда выполняется неравенство N > М₉ а для min-кучи N <М.

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

Данные, представленные такой структурой, удобны в обработке; некоторые операции с ними весьма нересурсоемки, например, удаление минимального (для min-кучи) или максимального (для max-кучи) элемента, добавление нового элемента и др.

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

АВЛ-дерево

АВЛ-дерево - структура данных, изобретенная в 1968 году двумя советскими математиками: Адельсон-Вельским Георгием Максимовичем и Ландисом Евгением Михайловичем. Прежде чем дать конструктивное определение АВЛ-дереву, сделаем это для сбалансированного двоичного дерева поиска. Сбалансированным называется такое двоичное дерево поиска, в котором высота каждого из поддеревьев, имеющих общий корень, отличается не более чем на некоторую константу к, и при этом выполняются условия, характерные для двоичного дерева поиска.

АВЛ-дерево - сбалансированное двоичное дерево поиска с к = 1. Для его узлов определен коэффициент сбалансированности (balance factor). Balance factor - это разность высот правого и левого поддеревьев, принимающая одно значение из множества {—1, 0, 1}. На рис. 5.12 изображено АВЛ-дерево, каждому узлу которого поставлен в соответствие его реальный коэффициент сбалансированности.

Положим В, - коэффициент сбалансированности узла 7} (/ - номер узла, отсчитываемый сверху вниз от корневого узла по уровням слева направо). Balance factor узла Г, рассчитывается следующим образом. Пусть функция /?() с параметрами 7) и L возвращает высоту левого поддерева L узла 7/, а с 7/ и R- правого. Тогда В, = h(T_h К) - h(T_h L). Например, Т?₄ = -1, так как /г(Г₄, К) - h(T₄, L) = 0 - 1 = -1.

Сбалансированное дерево эффективно в обработке, что следует из следующих рассуждений. Максимальное количество шагов, которое может потребоваться для обнаружения нужного узла, равно количеству уровней самого бинарного дерева поиска. А так как поддеревья сбалансированного дерева, «растущие» из произвольного корня, практически симметричны, то и его листья расположены на сравнительно невысоком уровне, т. е. высота дерева сводится к оптимальному минимуму. Поэтому критерий баланса положительно сказывается на общей производительности. Но в процессе обработки АВЛ-дерева балансировка может нарушиться, тогда потребуется осуществить операцию балансировки. Помимо нее над АВЛ-деревом определены операции вставки и удаления элемента. Именно выполнение последних может привести к дисбалансу дерева.

Рис. 5.12. АВЛ-дерево

Доказано, что высота АВЛ-дерева, имеющего N узлов, примерно равна log2 N. Имея в виду это, а также то, что время выполнения операций добавления и удаления напрямую зависит от операции поиска, получим временную сложность трех операций для худшего и среднего случая - 0(log АО-

Балансировка

Если после выполнения операции добавления или удаления коэффициент сбалансированности какого-либо узла АВЛ-дерева становится равен 2, т. е. | h(T_h R) - h(T_h L) = 2, то необходимо выполнить операцию балансировки. Она осуществляется путем вращения (поворота) узлов - изменения связей в поддереве. Вращения не меняют свойств бинарного дерева поиска и выполняются за константное время. Всего различают четыре их типа:

• 1) малое правое вращение;
• 2) большое правое вращение;
• 3) малое левое вращение;
• 4) большое левое вращение.

Оба типа больших вращений являются комбинацией малых вращений (право-левым или лево-правым вращением).

Возможны два случая нарушения сбалансированности. Первый из них исправляется 1-ми 3-м типом, а второй - 2-м и 4-м.

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

Рис. 5.13. Поддерево. Случай 1

Здесь х и у- узлы, а А, В, С- поддеревья. После добавления к поддереву А узла v баланс нарушится и потребуется балансировка. Она осуществляется правым поворотом (тип 1) узла^р (см. рис 5.14).

Рис. 5.14. Малый правый поворот

Малое левое вращение выполняется симметрично малому правому.

Второй случай дисбаланса исправляется большим правым или большим левым вращением. Пусть имеется сбалансированное поддерево (рис. 5.15).

Большое левое вращение показано на рис. 5.16.

Рис. 5.15. Поддерево. Случай 2

Рис. 5.16. Большой левый поворот

Большое правое вращение выполняется симметрично большому левому.

Добавление узлов

Операция вставки нового узла в АВЛ-дерево выполняется рекурсивно. По ключу данного узла производится поиск места вставки: спускаясь вниз по дереву, алгоритм сравнивает ключ добавляемого узла со встречающимися ключами, далее происходит вставка нового элемента; по возвращении из рекурсии выполняется проверка всех показателей сбалансированности узлов и, в случае необходимости, осуществляется балансировка. Для осуществления балансировки следует знать, с каким из рассмотренных выше случаев дисбаланса имеем дело. Допустим, мы добавили узел х в левое поддерево, для которого выполнялось h(T_h R) < h(T_h L), т. е. высота левого поддерева изначально превышала высоту правого. Если левое поддерево этого узла выше правого, то потребуется большое вращение, иначе - малое.

Удаление узлов

Удаление узла, так же, как и его вставку, удобно задать рекурсивно. Пусть х - удаляемый узел, тогда если х - лист (терминальный узел), то алгоритм удаления сводится к простому исключению узла х и подъему к корню с переопределением balance factor ов узлов.

Если же х не является листом, то он либо имеет правое поддерево, либо не имеет его.

Во втором случае из свойства АВЛ-дерева следует, что левое поддерево имеет высоту 1, и здесь алгоритм удаления сводится к тем же действиям, что и при терминальном узле.

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

Операция удаления реализуется определенно сложнее, чем операция добавления. Да и последствия ее выполнения могут потребовать поворота в каждом узле. Но какова вероятность возникновения ситуации, при которой появится потребность в поворотах? Этим вопросом задается Никлаус Вирт в своей книге «Алгоритмы и структуры» и отвечает на него: «Удивительный результат эмпирических проверок показал, что в то время как один поворот вызывается приблизительно каждыми двумя включениями, тем не менее при удалении мы имеем дело с одним поворотом на целых пять удалений».

Задания

• 1. Разработать программу, реализующую стек и операции работы с ним: добавление элемента, удаление элемента, чтение элемента.
• 2. Разработать программу, реализующую очередь и операции работы с ней: добавление элемента, удаление элемента, чтение элемента.
• 3. Разработать программу, реализующую дек и операции работы с ним: добавление элемента в конец и в начало, удаление элемента из конца и из начала, чтение элемента, находящегося в конце и в начале дека.
• 4. Реализовать программно двоичное дерево поиска.
• 5. Реализовать программно АВЛ-дерево.