Структуры данных и модели вычислений


Левосторонние кучи


Левосторонняя куча — это представление приоритетной очереди с помощью так называемого левостороннего бинарного дерева. При реализации приоритетных очередей левосторонними кучами предусматривается возможность их объединения.

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

Рангом узла будем называть увеличенное на 1 расстояние (число ребер) от него до ближайшего неполного потомка.

Ранг узла также можно определить следующим образом. Расширить данное дерево до полного бинарного дерева, добавляя к каждому узлу, имеющему менее двух потомков, в том числе и к листьям исходного дерева, недостающее количество потомков. Затем приписать каждому из листьев полученного расширенного дерева ранг 0, а ранг каждого из остальных узлов определить как минимум из рангов его непосредственных потомков плюс 1. Очевидно, что ранги вершин исходного дерева совпадут с рангами соответствующих вершин расширенного дерева.

Левостороннее дерево — это бинарное дерево, для каждого узла которого ранг его левого непосредственного потомка в расширенном дереве не меньше ранга его правого потомка.

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

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

Пример левостороннего дерева (и его расширения) приведен на рис. 5.1. Ребра исходного дерева выделены жирными линиями, а ребра, добавленные при расширении, — пунктиром. Числа рядом с узлами — их ранги.


Рис. 5.1. 




Начало    Вперед