Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19
Download 1.98 Mb.
|
Lekcii AiSD 2015
|
Б-деревья
Б-деревья (Ъайера—МакКрейта) являются сdалансирован- нышп деревьями, у которых число ветвей, исходящих из узлов, может быть два и doлee. Узел, корневой для двух ветвей, содер- жит единственный ключ, а узел, корневой для нескольких ветвей, содержит составной ключ несколько ключей, число которых на 1 меньше числа ветвей. Упрощенная архитектура Б—дерева пока— зана на рисунке 10.18: Рис. 10.18 — Б-дерево В зависимости от области применения таких деревьев, по- лезные данные могут храниться только в их терминальных узлах (в этом случае узлы верхних уровней обеспечивают быстрый доступ по ключам к терминальным узлам), или во всех узлах, как в обычных деревьях. Существуют способы преобразования двоичного дерева в Б- дерево и наоборот. 141 Модификацией Б-дерева является Б+дерево Б-дерево, у которого терминальные узлы соединены в связный список (см. рисунок 10.19). Именно по такому принципу хранятся данные в базах данных по технологии Microsoft SQL Server. Возможны и другие модификации Б-дерева, например Б++ дерево — Б+ дерево, у которого связный список формируется не только на самом нижнем уровне, но и на уровень выше. В тех случаях, когда максимальное число ветвей, исходящих из узла, ограничено, получаются, например, 2-3-деревья и 2-3-4- деревья. Рис. 10.19 — Б+ дерево Кроме рассмотренных сбалансированных деревьев сущест- вует также расширяемое дерево Тарьяна (splay-tree), являющее двоичным деревом поиска и обеспечивающее балансировку без каких-либо дополнительных признаков. Балансировка выполня- ется в том числе с использованием операций поворотов, анало- гичных показанной на рисунке 10.15. При необходимости обычное двоичное дерево поиска мож- но принудительно балансировать, например, алгоритмом, анало- гичным нисходящему обходу дерева. Но при этом не только не гарантируется эффективность алгоритма, но и существует воз- можность получить алгоритм с худшим временем работы, на- пример, P(N ). Подобные алгоритмы относятся к категории «на- пвпых», т.е. наиболее очевидных, но не всегда эффективных. То же самое справедливо для операции поиска ближайшего общего предка. 142 Многоключевые деревья Б-деревья могут считаться частным случаем многоключевых деревьев (с переменным числом ключей). Ещё один такой част- ный случай — Декартово дерево. Это древовидная структура данных, в каждом узле которой содержится два ключа, по одному ключу она является двоичной пирамидой, а по второму ключу двоичным деревом поиска. Более простая ситуация двухключевое дерево, которое яв- ляется двоичным деревом поиска либо только по одному из клю- чей, либо по сумме ключей (именно в этом случае возможно по- вторение сумм ключей). Такое дерево может использоваться для описания рёбер графа. При этом также возможно повторение ключей в дереве, в зависимости от структуры графа. Операции с такими двухключевыми деревьями ничем не от- личаются от операций с обычными двоичными деревьями. Вопросы н задания для самоконтроля ных?
Что представляют собой древовидные структуры дан- Какие существуют виды деревьев? Что представляет собой двоичное дерево? В чем заключается особенность дерева как структуры данных? Опишите организацию связей в дереве. Перечислите основные области применения деревьев. Какие операции осуществляются над деревьями? В чем преимущества использования деревьев? Чем отличаются двоичные деревья от списков? Изобразите структуру элемента двоичного дерева. Процедуры какого характера наиболее эффективны при работе с деревьями? Чем отличаются: сбалансированное, несбалансиро- ванное и вырожденное двоичные деревья. Проиллюстрируйте ри- сунками. Что означают термины «сбалансированное дерево» и «идеально сбалансированное дерево»? 143
Чем вырожденное дерево отличается от односвязного списка? Перечислите основные способы прохождения двоич- ного дерева. Предложите процедуру обхода дерева в ширину с ис- пользованием стека вместо очереди. Почему рекурсивные функции наиболее эффективны при работе с деревьями? В чем заключается вставка узла в дерево? Предложите нерекурсивную процедуру добавления узла в дерево без использования поиска. В чем заключается удаление узла из дерева? Проиллюстрируйте процесс удаления узла. Как дей- ствует алгоритм в каждом из трех возможных случаев? Что такое высота дерева? Как сохранить сбалансированность дерева при встав- ке и удалении узлов? Чем отличается красно-чёрное дерево от АВЛ-дерева? Каковы основные особенности красно-чёрного и АВЛ-дерева? На каких структурах данных могут строится деревья? Используя приведённые в этом разделе функции, на- пишите программу построения и просмотра двоичного дерева поиска. Используя правильный порядок ввода данных, постройте с помощью этой программы 1-2-братское дерево. В каком порядке должны вводиться данные, чтобы получилось сбалансированное дерево? 144 11. Элементы теории графов Download 1.98 Mb. Do'stlaringiz bilan baham: 
|