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

         

Свойства левостороннего дерева


  1. Правая ветвь из любого узла дерева имеет минимальную длину среди всех ветвей, исходящих из этого узла.
  2. Длина правой ветви левостороннего дерева, имеющего узлов, ограничена величиной , .

Первое свойство непосредственно следует из определения левостороннего дерева. Для доказательства второго свойства рассмотрим левостороннее дерево , у которого длина правой ветви равна . Индукцией по числу докажем, что число узлов в таком дереве удовлетворяет неравенству . Действительно, при утверждение очевидно. При левое и правое поддеревья дерева будут левосторонними, а ранги их корней больше или равны . Следовательно, по предположению индукции число узлов в каждом из них больше или равно , а в дереве — больше или равно

Для реализации приоритетной очереди с помощью левосторонней кучи будем использовать узлы вида

содержащие следующую информацию:

  • element — элемент приоритетной очереди или ссылка на него (используется прикладной программой);
  • key — его ключ (вес);
  • rank — ранг узла, которому приписан рассматриваемый элемент;
  • left, right — указатели на левое и правое поддеревья;
  • parent — указатель на родителя.

Куча представляется указателем на ее корень. Если — указатель на корень кучи, то через будем обозначать и саму кучу. Заметим, что указатель на родителя используется лишь в операциях УДАЛИТЬ и УМЕНЬШИТЬ_КЛЮЧ (см. ниже).



Содержание  Назад  Вперед