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

0

Специалисты в области производительности говорят, что озарения приходят, когда мыслят «не линейно». В этой главе обсуждается одна из наиболее нелинейных информационных структур в программировании — дерево. Древовидная структура представляет собой прорыв в организации данных, поскольку позволяет обрабатывать данные определенному набору алгоритмов намного быстрее, чем с применением линейных структур типа списка (list), вектора (vector) или последовательности (sequence). Древовидная структура обеспечивает естественную форму организации данных и, как следствие, получила широкое применение в файловых системах, графических пользовательских интерфейсах, базах данных, Web-сайтах и других системах.

Не всегда понятно, что имеют в виду специалисты в области производительности под «нелинейным» мышлением. Но, говоря, что древовидная структура «нелинейная», более подразумеваем организационные отношения, чем простые соотношения «до» и «после» между последовательно расположенными объектами. Отношения э древовидной структуре иерар- хичны, то есть объекты могут быть «выше» или «ниже» относительно друг друга. В принципе, терминология древовидной структуры данных основана на генеалогическом древе (family tree), в котором в качестве наиболее распространенных терминов описания взаимоотношений между объектами используются «parent» (родитель), «child» (ребенок), «ancestor» (предок) и «descendent» (потомок). Пример такого генеалогического древа приведен на рис. 6.1.

Рис. 6.1. Генеалогическое древо с отображением потомков Авраама, как указано в Книге Бытия, главы 25—36

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

По теме:

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