Фундаментальные алгоритмы и структуры данных в Delphi

Бакнелл Джулиан М.

Рисунок 9.1. Сортирующее дерево

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

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

Сортирующее дерево обладает еще одним атрибутом: двоичное дерево должно быть полным. Двоичное дерево называется полным, когда все его уровни, за исключением, быть может, последнего, заполнены. В последнем уровне все узлы размещаются максимально сдвинутыми влево. Полное дерево является максимально сбалансированным. Полное двоичное дерево показано на рис. 9.1.

Так как же эта структура может помочь в наших поисках идеальной структуры очереди по приоритету? Что ж, операции вставки и удаления при использовании сортирующего дерева являются операциями типа O(log(n)), но они выполняются значительно быстрее, чем эти же операции в дереве двоичного поиска, независимо от того, является ли оно сбалансированным. Это тот случай, когда О-нотация оказывается неприемлемой - она не позволяет количественно определить, какая из двух операций с одним и тем же значением О большого действительно выполняется быстрее.

Вставка в сортирующее дерево

Рассмотрим алгоритмы вставки и удаления. Вначале ознакомимся со вставкой. Чтобы вставить элемент в сортирующее дерево, мы добавляем его в конец этого дерева, в единственную позицию, которая соответствует требованию полноты (на рис. 5 этой позицией была бы позиция правого дочернего узла пятого узла).

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

Если этот новый дочерний узел больше своего родительского узла, мы меняем его местами с родительским узлом. В своей новой позиции новый узел может быть все же больше своего нового родительского узла, и поэтому их нужно снова поменять местами. Мы продолжаем такое перемещение по сортирующему дереву до тех пор, пока не будет достигнута точка, в которой новый узел не больше родительского узла или пока не достигнем корневого узла дерева. Выполнение упомянутого алгоритма обеспечивает, чтобы все узлы были больше обоих своих дочерних узлов, и, таким образом, свойство пирамидальности восстанавливается. Этот алгоритм называется алгоритмом пузырькового подъема (bubble up), поскольку новый узел подобно пузырьку воздуха "всплывает" вверх, пока не попадает в требуемую позицию (либо в позиции корневого узла, либо под узлом, который больше него).

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

Удаление из сортирующего дерева

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

дерева -что было бы полным нарушением атрибута полноты сортирующего дерева. Вместо этого мы заменяем корневой узел последним узлом сортирующего дерева и уменьшаем его размер, тем самым обеспечивая сохранение полноты. Но при этом снова возможно нарушение свойства пирамидальности. Весьма вероятно, что новый корневой узел будет меньше одного или обоих своих дочерних узлов. Поэтому нужно снова исправить сортирующее дерево, чтобы восстановить его свойство пирамидальности. Для этого мы находим больший из двух дочерних узлов и меняем его местами с данным узлом. Как и ранее, эта позиция может нарушать свойство пирамидальности, поэтому мы проверяем, является данный узел меньше одного (или обоих) дочерних узлов и повторяем процесс. Со временем выяснится, что узел погрузился (или "просочился") на уровень, где он больше обоих своих дочерних узлов или является листом, не имеющим дочерних узлов. В любом случае свойство пирамидальное™ восстанавливается. Этот алгоритм называется алгоритмом просачивания вниз (trickle down).

Если реализовать кучу, используя реальное двоичное дерево, подобное описанному в главе 8, выяснится, что при этом расходуется довольно большой объем памяти. Для каждого узла необходимо поддерживать по три указателя: по одному для каждого дочернего узла, чтобы можно было реализовать алгоритм просачивания в нижние уровни дерева, и один для родительского узла, чтобы можно было реализовать алгоритм пузырькового подъема. При каждом обмене узлов местами придется обновлять бесчисленное количество указателей для множества узлов. Обычно в этом случае применяют прием, когда узлы остаются на своих местах, а вместо этого меняют местами элементы внутри узлов.

Однако существует более простой способ. Полное двоичное дерево легко представить массивом. Снова взгляните на рис. 9.1. Выполните просмотр дерева, используя обход по уровням. Обратите внимание, что в полном дереве обход по уровням не затрагивает никаких пробелов, в которых имеется позиция для узла, но какой-либо узел отсутствует (естественно, до тех пор, пока не будут посещены все узлы и не будет достигнут конец дерева). Узлы легко отобразить элементами массива, чтобы последовательное посещение элементов массива было эквивалентно посещению узлов посредством обхода по уровням. При этом элемент 1 массива был бы корневым узлом сортирующего дерева, элемент 2 - левым дочерним узлом корневого узла, элемент 3 - правым дочерним узлом корневого узла и т.д. Фактически, именно так пронумерованы узлы на рис. 9.1.

Теперь обратите внимание на нумерацию дочерних узлов каждого узла. Дочерними узлами корневого узла 1 являются, соответственно, узлы 2 и 3. Дочерними узлами узла 4 являются узлы 8 и 9, а узла 6 - узлы 12 и 13. Заметили ли вы какую-нибудь закономерность? Дочерними узлами узла n являются узлы 2n и 2n + 1, а родительским узлом узла n является узел nil. Теперь уже не обязательно, чтобы узел содержал указатели на родительский и дочерние узлы. Вместо этого можно воспользоваться простым арифметическим отношением. Таким образом, мы изобрели метод реализации сортирующего дерева при помощи массива, и решив более простую задачу, можно было бы снова отдать предпочтение структуре TList.

Проблема заключается в следующем: рассмотренная нами реализация сортирующего дерева в виде массива требует, чтобы отсчет элементов массива начинался единицы, а не с нуля, как имеет место в структуре TList. Этого достаточно легко добиться. Достаточно изменить арифметическую формулу вычисления индекса родительского и дочерних узлов. Дочерние узлы узла n должны располагаться в позициях In + 1 и In + 2, а родительский узел этого узла - в позиции (n -1)11.

Реализация очереди по приоритету при помощи сортирующего дерева