Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[130]

ключи различны.

а.Будем хранить в каждой вершине х 2-3-4 дерева поле height[x], хранящее высоту поддерева с корнем в х. Показать, что эту ин- хранить формацию можно поддерживать, не ухудшая асимптотику вре- хранящее мени поиска, добавления и удаления.- это

б.Реализовать операцию объединения деревьев Т и Г", раз- неплохо! делённых ключом к. Время работы должно быть 0(\h - h"\),

где Ы, h" - высоты деревьев.

в.Пусть р - путь в 2-3-4 дереве Г от корня к заданному ключу к. Рассмотрим два множества ключей из Г: меньшие к (множество s) и большие к (множество s"). Показать, что s разбивается на деревья Tq,T[, .. ,Tm, разделенные ключами к[, к2, , кт (для всех у £ Г/ 1 и z £ Т выполнено у < Ц < z при г = 1, 2,..., т. Как связаны высоты деревьев T t и Т? На какие части путь р делит s"?

г.Реализовать операцию разделения. Для этого следует объединить ключи из s в 2-3-4 дерево Т и ключи из s" в дерево Г". Для дерева с п ключами время работы этой операции должно быть О (log га). (Указание: при сложении стоимостей операций объединения происходит сокращение.)

Замечания

Сбалансированные деревья и Б-деревьев обсуждаются в Кнут [123], Ахо, Хопкрофт и Ульман [4] и Седжвик [175]. Подробный обзор Б-деревьев дан в Комер [48]. Гибас и Седжвик [93] рассмотрели взаимосвязи между разными видами сбалансированных деревьев, включая красно-чёрные и 2-3-4 деревья.

В 1970 году Хопкрофт (J. Е. Hopcroft) предложил понятие 2-3 деревьев, которые явились предшественниками Б-деревьев и 2-34 деревьев. В этих деревьях каждая внутренняя вершина имеет 2 или 3 детей. Б-деревья были определены Байером и МакКрейтом в 1972 году [18]. В их работе не объяснён выбор названия.


Биномиальные кучи

В этой главе и в главе 21 рассматриваются структуры данных, известные как сливаемые кучи (mergeable heaps). Такая структура хранит несколько множеств (куч), элементы которых называют вершинами. Каждая вершина содержит поле key (ключ), в котором хранится некоторое число; кроме того, в вершине может храниться некоторая информация, сопровождающая это число. Сливаемые кучи позволяют выполнять следующие пять операций: Маке-Неар() создаёт и возвращает новую кучу, не содержащую элементов;

lNSERT(ii, х) добавляет элемент (вершину) х в кучу Н (поле key элемента х должно быть заполнено заранее);

Minimum (if) возвращает указатель на элемент кучи Н с минимальным ключом;

Extract-Min (ii) изымает элемент с минимальным ключом из кучи if и возвращает указатель на изъятый элемент;

Union (Hi, Н2) объединяет кучи Н\ и ii2, то есть создаёт и возвращает новую кучу, содержащую все элементы куч Н\ и Н2. Сами кучи iii и Я2 ПРИ этом исчезают. Структуры данных, описываемые в этой и следующей главах, поддерживают ещё две операции:

decrease-key(ii, х, к) уменьшает ключ вершины х кучи Н, присваивая ему новое значение к (предполагается, что новое значение не превосходит старого);

delete(ii, х) удаляет элемент (вершину) х из кучи Н.

Как видно из таблицы 20.1, если мы не нуждаемся в операции Union, то (двоичные) кучи, с помощью которых мы сортировали массив в главе 7, весьма эффективны. Для них все операции, кроме операции Union, выполняются за время O(lgra) в худшем случае (а некоторые из операций - ещё быстрее). Но для выполнения операции Union нам приходится приписывать один массив к другому и затем выполнять процедуру Heapify, что требует времени О(га).

В этой главе мы расскажем о «биномиальных кучах» (второй столбец таблицы). Обратите внимание, что объединение двух би-


Процедура

Двоичные кучи (в худшем случае)

Биномиальные кучи Фибоначчиевы кучи (в худшем случае)(в среднем)

EXTRACT-MlN

Delete

Decrease-Key

Union

Minimum

Make-Heap

Insert

0(1) ©(lgrx)

0(1)

0(lgn)

0(n) 0(lgn) 0(lgn)

Рис. 20.1 Время выполнения различных операций для трёх видов сливаемых куч (п - общее число элементов в кучах на момент операции).

номиальных куч, содержащих в сумме га элементов, требует всего лишь О (lgra) операций.

В главе 21 мы рассматриваем «фибоначчиевы кучи», которые ещё более эффективны (третий столбец). Отметим, впрочем, что это улучшение достигается лишь для учётной стоимости операций при амортизационном анализе.

В наших процедурах мы не занимаемся выделением и освобождением памяти для элементов куч.

Все три вида куч, указанных в таблице, не позволяют эффективно реализовать поиск элемента с данным ключом (Search). Поэтому процедуры Decrease-Key и Delete получают в качестве параметра не ключ вершины, а указатель на неё (во многих случаях это требование не создаёт проблем).

В разделе 20.1 определяются биномиальные деревья и кучи. Там же описывается представление биномиальных куч в программе. В разделе 20.2 показано, как реализовать все перечисленные операции за указанное в таблице 20.1 время.

Биномиальная куча состоит из нескольких биномиальных деревьев.

20.1.1. Биномиальные деревья

Биномиальные деревьями (binomial trees) называются упорядоченные (в смысле раздела 5.2.2) деревья Во, В\, В2, , определяемые индуктивно.

Дерево Во состоит из единственной вершины (рис. 20.2а). Дерево Bk склеено из двух экземпляров дерева Bk-i. корень одного из них объявлен самым левым потомком корня другого. На рис. 20.26 показаны биномиальные деревья В0-В4.

20.1. Биномиальные деревья и биномиальные кучи



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]