Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

CMИCKdX.

30. 
    На каких структурах данных могут строится списки?
    
31. 
    Предложите алгоритм удаления из связного списка ка- ждого чётного звена.
    
32. 
    Предложите методы использования двусвязного коль- цевого списка для работы с деком.
    

110

10. 
    Древовидные структуры данных
    

Существует несколько определений того, что такое дерево как структура данных. Например, дерево — это лес, состоящий из одного связного компонента [16] (т.е. из одного дерева) (рекур- сивное определение). Или (с точки зрения теории графов), дере- во — это граф без циклов (Directed Acyclic Graph, DAG) \6] . Рас- смотрим деревья с точки зрения структур данных, которые долж- ны использоваться в программах и храниться в памяти.

Деревья или, в более широком смысле, древовидные структуры данных, представляют собой динамические связные структуры, отличающиеся от списков тем, что система связей не носит линейного характера, а образует ветвп, подобно природ- ному дереву (откуда и произошло название этой структуры дан- ных).
Эти структуры данных в общем случае можно разделить на две группы, которые отличаются друг от друга способом по- строения и (как следствие) реализацией процедур обработки — собственно деревья п пирамиды ( нлп «кучи»). Но у обеих этих групп сохраняется общий древовидный характер и часто их объе- диняют под общим коротким названием « Ьереsья». Отличие nu- рамид от деревьев (н значения термина «кучп») будет рассмотре- но позже.
Часто предполагается, что дерево — это ориентированная (направленная) структура данных, и при реализации связей, ана- логичной спискам, направление (т.е. ориентация) задаётся авто- матически. Кроме того, некоторые алгоритмы обработки деревь- ев предполагают, что дерево является ориентированным (что не всегда удобно), в то время как в других алгоритмах считается, что дерево — неориентированная структура (с точки зрения фи- тического уровня двунаправленная, т.к. для обеспечения воз- можности перемещения по ветвям дерева во всех направлениях
и вверх, и вниз, — физические связи должны быть направлены в обе стороны).

1. 
   Классификация
   

Существует очень большое количество видов древовидных структур данных, которые можно классифицировать по не- скольким различным признакам. Одно такое разделение уже бы- ло приведено — деревья и пирамиды.

Из других признаков классификации следует указать (в пер- вую очередь) чпсла ветвей, отходящих от каждого узла дерева. Деревья могут быть:
— двоичны ми (или бинарны ми) — имеющими не более двух ветвей (примеров таких деревьев очень много, они будут приве- дены позже);

• 
  с числом ветвей больше 2 — часто такие деревья называют мультивариантны ми (многопутевы ми, сильноветвящнмися) или К-деревьями (т.е. К-мерными). Примерами могут быть Б- деревья (различные деревья Байера-МакКрейта с вариантами, на- пример, 2-3-деревья, 2-3-4-деревья) и т.п. Видов К-деревьев очень много (свыше 40 различных древовидных структур для представления многомерной информации: R-Tree, R+-Tree, Hilben R-Tree, hB-Tree, hBII-Tree, BV-Tree, BD-Tree, GBD-Tree, G-Tree, SKD-Tree, kd-Tree, kd2B-Tree, BSP-Tree, LSD-Tree, P- Tree, TR-Tree, Cell-Tree, Quadtree, Grid File, Z-Hashing, SS-Tree).
  

Важным признаком является состояние сбалансированно-
сша дерева и способы его достижения. Деревья могут быть:

• 
  сбалансированными;
  

идеально сбалансированными (отличие этих двух первых состояний будет рассмотрено ниже);
вырожденными;

• 
  отличающимися более или менее сильно от сбалансиро-
  

ВІІННЫХ И ОТ ВЫ]ЗОЖQ ННЫХ.
Автоматическая балансировка дерева выполняется, напри- мер, для АВИ-деревьев, красно-чёрных деревьев (все эти деревья являются двоичны ми), Б-деревьев и некоторых других видов де- ревьев.
Ещё один возможный признак классификации примене- ние деревьев (хотя не всегда из названия дерева следует, что оно применяется именно с этой целью). В качестве примера можно указать деревья поиска или сортировки, но из названия «дерево

112