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

         

Толстые деревья


Основные определения

Определяем толстое дерево ранга

следующим образом:

  • Толстое дерево ранга ноль состоит из единственного узла.
  • Толстое дерево ранга , для , состоит из трех деревьев

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

Ранг узла в толстом дереве определяется как ранг толстого поддерева с корнем в узле .

На рис. 9.1 приведены примеры толстых деревьев.


Рис. 9.1. 

Свойства толстых деревьев:

  1. В толстом дереве ранга ровно узлов.
  2. Для любого натурального числа существует лес из толстых деревьев, в котором ровно узлов. Такой лес можно построить, включив в него столько деревьев ранга , каково значение -го разряда представления числа в троичной системе счисления. Заметим, что для построения такого леса можно использовать и избыточные троичные представления.
  3. Толстый лес из узлов содержит деревьев.

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



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