Главная » Java, Структуры данных и алгоритмы » Представление обычных деревьев с помощью бинарных деревьев

0

Альтернативным способом представления обычного дерева Г является трансформация последнего в бинарное дерево Т’ (рис. 6.23). Допустим, что Т упорядочено или имеет произвольный порядок. Трансформация выполняется следующим образом:

•          для каждого узла и дерера Г существует составной узел и’ дерева Т\ ассоциируемого с и;

•          если и — простой узел дерева Т, не имеющий прямых потомков, то дочерние элементы узла и’ в дереве Т’ будут простыми узлами;

•          если и — составной узел дерева Т, у которого v является первым дочерним элементом, тогда и’ будет левым дочерним элементом и’ в дереве 7";

•          если узел v имеет прямого потомка, то w’ будет правым дочерним элементом и’ в дереве Т’.

Рис. 6.23. Представление *’Дбрева! с поря61цью бййарного Дерева: (а) дерево Г;

(Ь) бинарное дерево Г’, ассоциируемое с Т. Пунктиром соединены узлы дерева Т\ ассоциируемые с узлам и-братья ми дерева Т

Заметим, что простые узлы дерева Т’ не ассоциируются с узлами дерева Т, а являются заглушками (следовательно, могут быть null).

Поддерживать соответствия между Т’ и Т и выражать операции в Т в терминах соответствующих операций Т’ не сложно. Интуитивно можно рассчитывать на соответствие условий конверсии Тв Т’, при которой каждая связка узлов-братьев {vi, V2, v^} в дереве Тс родительским элементом v замещается цепочкой правых дочерних элементов, корнем которых является vi, который затем становится левым дочерним элементом v.

В табл. 6.4 сведены данные о производительности реализации дерева с помощью бинарного дерева. Анализ дан для решения в упражнении 3-6.20.

Операция

Время

size, isEmpty

0(1)

positions, elements

0(1)

swapElements, replaceElement

0(1)

root

0(1)

parent(v)

0(1)

children(v)

0(1)

islnternal, isExternal, isRoot

0(1)

Таблица 6.4. Время выполнения методов дерева, представленного с помощью бинарного дерева, которое, в свою очередь, реализовано с помощью связной структуры. Количество узлов равно л, при этом cv означает количество дочерних элементов узла v, a sv — количество потомков v. Методы hasNext() и nextObject() итераторов, возвращаемых методами elements(), positions()n children(v), требуют 0(1) времени. Занимаемое место есть 0(п)

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии