Структуры данных и модели вычислений
Свойства левостороннего дерева
- Правая ветвь из любого узла дерева имеет минимальную длину среди всех ветвей, исходящих из этого узла.
- Длина правой ветви левостороннего дерева, имеющего узлов, ограничена величиной , .
Первое свойство непосредственно следует из определения левостороннего дерева. Для доказательства второго свойства рассмотрим левостороннее дерево , у которого длина правой ветви равна . Индукцией по числу докажем, что число узлов в таком дереве удовлетворяет неравенству . Действительно, при утверждение очевидно. При левое и правое поддеревья дерева будут левосторонними, а ранги их корней больше или равны . Следовательно, по предположению индукции число узлов в каждом из них больше или равно , а в дереве — больше или равно
Для реализации приоритетной очереди с помощью левосторонней кучи будем использовать узлы вида
содержащие следующую информацию:
- element — элемент приоритетной очереди или ссылка на него (используется прикладной программой);
- key — его ключ (вес);
- rank — ранг узла, которому приписан рассматриваемый элемент;
- left, right — указатели на левое и правое поддеревья;
- parent — указатель на родителя.
Куча представляется указателем на ее корень. Если — указатель на корень кучи, то через будем обозначать и саму кучу. Заметим, что указатель на родителя используется лишь в операциях УДАЛИТЬ и УМЕНЬШИТЬ_КЛЮЧ (см. ниже).
