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

Сортирующее дерево

Сортирующее дерево

Классическая структура данных, используемая для создания очереди по приоритету, известна под названием сортирующего дерева (или "кучи"). Сортирующее дерево (heap), на которое еще ссылаются как на частично упорядоченное полное двоичное дерево, - это двоичное дерево с определенными специальными свойствами и несколькими специальными операциями. (Не путайте эту "кучу" с "кучей", используемой в среде Delphi, -областью памяти, в которой выполняется все распределение памяти.)

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

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

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

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

Оглавление книги