к узлу, являющемуся исходным для
Можно двигаться к узлу, являющемуся исходным для узла Ун, разделив k пополам и отбросив дробную часть. Адрес соответствующего узлу элемента памяти определяется по адресной функции.
Рассмотрим еще один способ реализации, который применим только для двоичных деревьев. Если для представления двоичного дерева используется вектор памяти от элемента i до элемента j включительно, то корень дерева размещается в элементе памяти с адресом
где
Рис. 3.2. Пример реализации структуры типа регулярного двоичного дерева с помощью линейного списка
Корень дерева размещается в середину вектора. В элементах памяти от г-то до (m-l)-ro включительно размещается левое поддерево. В элементах памяти от (m+1)-го до j-го включительно размещается правое поддерево. Аналогично процесс повторяется для размещения каждого поддерева. Приведенный способ позволяет реализовать двоичное сбалансированное дерево.
Существует ряд других способов представления древовидных структур [4, 13, 17]. С помощью приемов, основанных на свойствах целых чисел, можно с помощью последовательного распределения организовать в памяти некоторые сетевые структуры. Однако для представления сложных сетевых структур требуются более гибкие методы построения в памяти ЭВМ, которые невозможно получить с помощью последовательного распределения памяти. В этом случае используется связанное распределение памяти.
