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

0

Описанная выше связная структура может применяться как для бинарных деревьев, так и для обычных деревьев. Поскольку при этом не оговаривается количество дочерних элементов узла v обычного дерева, то для их хранения вместо переменных экземпляров применим контейнер (к примеру, список или вектор). Схема такой структуры приводится на рис. 6.22.

В табл. 6.3 сведены показатели производительности реализации дерева с помощью связной структуры. Анализ предлагается произвести в упражнении, но заметим, что использование контейнера для хранения дочерних элементов каждого узла v позволяет реализовать метод children(v) простым вызовом метода elementsQ из этого контейнера.

Рис. 6.22. Связная структура для дерева: (а) объект, ассоциируемый с узлом;

(Ь) часть структуры данных, ассоциируемая с узлом и его дочерними элементами

 

Операции

Время

size, isEmpty

0(1)

positions, elements

0(1)

swapElements, replaceElement

0(1)

root, parent

0(1)

children(v)

0(1)

islnjernal, is^xternal, isRoot

0(1)

Таблица 6.3. Время выполнения методов дерева с количеством узлов п, реализованного связной структурой. С помощью cv указывается количество дочерних элементов узла v. Используется 0(п) места

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

По теме:

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