Методы организации данных

Методы хранения данных в памяти ЭВМ обычно предполагают раздельное хранение значений каждой составной единицы информации [4, 8, 9]. Отдельное значение СЕИ, находящееся в памяти ЭВМ, называется записью.Запись состоит из значений атрибутов, включенных в структуру СЕИ. Множество записей образует массив, или файл. Термин «массив» обычно используется при рассмотрении данных в оперативной памяти ЭВМ, а «файл» – для данных, хранимых на внешних запоминающих устройствах. Как правило, файл содержит записи, принадлежащие одной и той же СЕИ, хотя в общем случае это необязательно.

Под организацией значений данных понимают относительно устойчивый порядок расположения записей данных в памяти ЭВМ и способ обеспечения взаимосвязи между записями [8, с. 141].

Организация значений данных (далее называемая просто организацией данных) может быть линейной и нелинейной. При линейной организации каждая запись, кроме первой и последней, связана с одной предыдущей и одной последу­ющей. У записей, соответствующих нелинейной организации данных, количество предыдущих и последующих записей может быть произвольным.

Линейные методы организации данных различаются только способами указания предыдущей и последующей записи по отношению к текущей. Это приводит к тому, что алгоритмы, эффективные для одних методов организации данных, становятся неприемлемыми для других. Среди линейных методов выделяются последовательная и цепная организации данных.

При последовательной организации данных [8, с. 142] записи располагаются в памяти строго одна за другой, без промежутков, в том порядке, в котором они обрабатываются. Последовательная организация данных обычно соответствует понятию «массив» («файл»).

Записи, составляющие массив, с точки зрения способа указания их длины делятся на записи фиксированной, переменной и неопределенной длины. Записи фиксированной (постоянной) длины имеют одинаковую, заранее известную длину. Если длины записей неодинаковы, то они указываются в самой записи. Такие записи называют записями переменной длины. Вместо явного указания длины записи можно отмечать окончание записи специальным символом-разделителем, который не должен встречаться среди информационных символов значения записи. Записи, заканчивающиеся разделителем, именуются записями неопределенной длины.

Адреса промежуточных записей фиксированной длины в массиве задаются формулой

A (i) = А (1) + (I – 1) L,

где A (i) – начальный адрес i -й записи; А (1) – начальный адрес первой записи; L – длина одной записи.

Для массива записей переменной и неопределенной длины подобной простой формулы не существует. Они занимают меньший объем памяти, но их обработка ведется медленнее, поскольку обнаружение следующей записи затруднено.

В структуре записей последовательного массива обычно выделяется один или несколько ключевых атрибутов, по значениям которых происходит доступ к остальным значениям атрибутов той или иной записи. Состав ключевых атрибутов необязательно соответствует понятию первичного ключа.

Будем считать, что последовательный массив состоит из записей фиксированной длины, а среди атрибутов записи будем выделять только один ключевой атрибут. Наличие в записях других (неключевых) атрибутов специально не оговаривается. Иллюстрацией такого последовательного массива служит табл. 4.

Таблица 4

p (1)	p (2)	…	p (i)	…	p (M)
			i		M

Ключевые атрибуты в записях обозначаются через p (i), где i – номер записи. Общее число записей в массиве обозначается через М.

Записи массива могут быть упорядоченными или неупорядоченными по значениям ключевого атрибута (ключа), имя которого одинаково во всех записях. Ключевой атрибут обычно является атрибутом-признаком. Часто требуется поддерживать упорядоченность записей по нескольким именам ключевых признаков. В этом случае среди признаков устанавливается старшинство. Условия упорядоченности записей в массиве (и вообще в линейной организации данных) выглядят следующим образом:

р (i) ≤ р (i + 1) – упорядоченность по возрастанию;

p (i) ≥ p (i + l) – упорядоченность по убыванию.

Наиболее важными и часто применяемыми алгоритмами обработки данных выступают формирование данных, их поиск и корректировка, а также последовательная обработка. Они могут быть реализованы с использованием достаточно большого количества методов организации данных. Здесь мы рассмотрим выбор наилучшего метода организации данных.

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

Упорядоченные данные эффективны для быстрого поиска информации. Выводимые на печать выходные документы, которые получены на основе отсортированных данных, удобны для дальнейшего использования. Многие алгоритмы задач управления вообще рассчитаны на использование только упорядоченных данных. Отсортированные данные позволяют организовать быструю обработку нескольких массивов. Далее будем считать все массивы упорядоченными по возрастанию значений одного атрибута, когда для ключа i -й записи p (i) справедливо условие p (i) ≤ p (i + l).

Для каждого метода организации данных требуется анализировать следующие величины [8, 9]:

– время формирования данных, т. е. время создания в памяти ЭВМ так или иначе упорядоченного представления данных (упорядочение способно ускорить выполнение алгоритмов поиска данных);

– время поиска данных. Известно, что условия поиска (выборки) на практике могут быть достаточно разнообразными. Обычно анализируется простейший и наиболее распространенный случай (поиск по совпадению) – найти записи, у которых значение ключевого атрибута равно заранее известной величине q;

– время корректировки данных. Из всех возможных вариантов корректировки учитывается включение или исключение одной записи;

– объем дополнительной памяти, расходуемой под служебную информацию (например, адреса связи).

Время выполнения алгоритма обычно прямо пропорционально числу требуемых сравнений ключевых атрибутов и искомых величин, и поэтому лучше анализировать не время, а количество операций сравнения значений.

Необходим еще ряд допущений, обеспечивающих равномерное распределение вероятностей для всех случайных величин, описывающих работу алгоритма:

– распределение значений ключевых атрибутов в массиве из М записей – равномерное;

– значение q при поиске по совпадению выбрано случайно: это означает, что поиск с одинаковой вероятностью 1/ М может закончиться на любой записи массива;

– положение включаемой (исключаемой) записи при корректировке определяется теми же вероятностями, что и при поиске.

Минимальное число сравнений при упорядочении последовательного файла можно узнать, не рассматривая ни одного конкретного алгоритма с помощью рассуждений, характерных для теории информации. Процедура упорядочения состоит из серии сравнений ключевых атрибутов и тех или иных перераспределений записей по результатам сравнения. Массив, характеризующийся наибольшей неопределенностью своего состояния, будем называть случайным. Все его М! состояний равновозможны (М! = 1 ∙ 2∙ … ∙ М).

Таким образом, минимальное число сравнений, необходимое для упорядочения массива из М записей, определяется как

С = log M!,

что соответствует минимально возможному числу вопросов о состоянии массива с возможными ответами типа «да – нет» (принято считать log по основанию 2).

После преобразований по формуле Стирлинга получаем:

С = М (log М – 1,43).

В анализе алгоритмов принято учитывать в подобных формулах лишь те слагаемые, которые ощутимо влияют на общую сумму (разность).

Соответствующее преобразование выглядит как С ~ М log M (С пропорционально М log M). Значением коэффициента пропорциональности в этом кон-тексте мы интересоваться не будем. Разумеется, справедлива эта запись для времени сортировки Т ~ М log M.

Поиском [8, 9] называется процедура выделения из некоторого множества записей определенного подмножества, записи которого удовлетворяют заранее поставленному условию. Условие поиска часто именуют запросом на поиск.

Простейшим условием поиска служит поиск по совпадению,т. е. равенство значения ключевого атрибута i -й записи p (i) и некоторого заранее заданного значения q. Алгоритмы всех разновидностей поиска можно получить из алгоритмов поиска по совпадению, которые рассматриваются в дальнейшем.

Базовым методом доступа к массиву является ступенчатый поиск.Он предполагает упорядоченность обрабатываемых записей по возрастанию или по убыванию. Для определенности будем считать, что массив отсортирован по возрастанию значений ключевого атрибута p (i).

Простейшим вариантом ступенчатого поиска (его можно назвать одноступенчатым) является последовательный поиск. Искомое значение q сравнивается с ключом первой записи. Если значения не совпадают – с ключом второй записи, и так до тех пор, пока q не станет больше ключа очередной записи. Алгоритм последовательного поиска на языке Паскаль показан А.И. Мишениным [8].

Число сравнений в цикле может быть выражено как С = ∑ I r (i), где суммирование по i ведется в пределах от 1 до М.

Поиск с одинаковой вероятностью r (i) = l / M может окончиться на любой записи, поэтому

С = (1/ М) · ∑i = (М + 1) / 2, или С ~ М.

Далее рассмотрим двухступенчатый поиск в массиве, состоящем из М записей. Для заданного М выбирается константа d_l, называемая шагом поиска.Если необходимо отыскать запись со значением ключевого атрибута, равным q, производятся следующие действия.

Значение q последовательно сравнивается с рядом величин р (1), p (l + d_l), p (l + 2 d_l),..., p (l + kd_l) до тех пор, пока будет впервые достигнуто неравенство p (l + md_l) ≥ q. Здесь заканчивается первая ступень поиска. На второй ступени q последовательно сравнивается со всеми ключами, которые имеют номер l + md_l и больше, до тех пор, пока в процессе сравнений не будет достигнут ключ, больший, чем q. Извлеченные при этом записи с ключом q образуют результат поиска.

Эффективность поиска измеряется количеством произведенных сравнений. Для двухступенчатого поиска среднее число сравнений составит примерно

C = M /(2 d_l) + d₁ / 2.

Параметр d_l – выбираемый, и,естественно, выбрать его нужно так, чтобы минимизировалось С. Будем считать d_l непрерывной переменной и вычислим производную

C' = – M / (2 d_l ²) + l / 2.

Из условия С' = 0 получаем d_l = SQR (M). Вторая производная С" в точке х = d₁ положительна, следовательно, достигнуто минимальное значение С.

При n -ступенчатом поиске заранее выбираются константы n и S. На первом этапе ключевые атрибуты для сравнения с искомым ключом q выбираются из массива по закону арифметической прогрессии начиная с р (1) и шагом d _l = M / S (округление в меньшую сторону). Когда будет впервые достигнут ключ p (k) > q, выбирается шаг d ₂ = d _l / S и организуются сравнения с этим шагом начиная с p (k – d _l). Описанные действия повторяются n раз, причем шаг на последней ступени поиска d_n = l.

Минимальное число сравнений достигается при S = M и, кроме того, существует оптимальное n = ln (M).

Ступенчатый поиск имеет важный частный вариант – бинарный поиск, прикотором S = 2.

Для бинарного поиска вводятся левая граница интервала поиска А и правая граница В. Первоначально интервал охватывает весь массив, т. е. А = 0, В = М + 1. Вычисляется середина интервала i по формуле i = (A + B) / 2 с округлением в меньшую сторону. Ключ i -й записи p (i) сравнивается с искомым значением q. Если p (i) = q, то поиск заканчивается. В случае p (i) > q записи с номерами i + 1, i + 2,..., М заведомо не содержат ключа q, и надо сократить интервал поиска, приняв B = i. Аналогично при p (i) < q надо взять A = i. Далее середина интервала вычисляется заново, и все действия повторяются. Если будет достигнут нулевой интервал, то требуемой записи в массиве нет.

Алгоритм бинарного поиска представлен А.И. Мишениным на языке «Паскаль» в практикуме «Теория экономических информационных систем» [9].

Достаточно легко оценить максимальное число сравнений C_m при поиске данных бинарным методом. Сокращение интервала поиска на каждом шаге в худшем случае приведет к интервалу нулевой длины, что соответствует отсутствию в массиве искомого значения ключевого атрибута. После первого сравнения интервал поиска составит М /2 записей, после второго – М /4 и т. д. Когда интервал поиска впервые станет меньше 1, применяемая схема округления результата деления даст нулевой интервал и поиск закончится. Это соответствует неравенству

М / (2 ^Сm) ≤ 1,

откуда C_m ~ log M.

Среднее число сравнений при бинарном поиске составляет C = log M – 1. Для обоснования представим все возможные разветвления алгоритма бинарного поиска в виде дерева. Число уровней дерева соответствует С_m. Одна половина возможных сравнений расположена на последнем уровне, другая – на первых (log M – l).

Определение лучшего метода поиска (из рассмотренных выше последовательного, двухступенчатого и бинарного) опирается на следующие рассуждения. Во всех трех случаях время поиска является функцией от числа записей М. Конкретные выражения составляют:

– для последовательного поиска:

Т ₁ ~ М, или Т ₁ = k ₁* М;

– для двухступенчатого поиска:

T ₂ ~ SQR (M), или T ₂ = k ₂ (SQR (M));

– для бинарного поиска:

Т ₃~ log M, или T ₃ = k ₃ * log M.

Коэффициенты пропорциональности в каждом случае неизвестны (они определяются в зависимости от быстродействия ЭВМ и применяемого языка программирования). Однако очевидно, что функция логарифма растет с увеличением М медленнее, чем две другие функции (для Т ₁ и Т ₂).

Таким образом, даже при неизвестных коэффициентах k _l, k ₂, k ₃ можно утверждать, что при достаточно большом числе записей М бинарный метод поиска выполняется, безусловно, быстрее двух остальных. Значения k _l, k ₂, k ₃ влияют на граничную величину М, выше которой преимущество бинарного поиска безусловно.

Корректировка массива (последовательного) может касаться одной его записи или группы записей [8, 9]. Отдельная запись может включаться в массив и исключаться из него. Кроме того, в записи могут быть изменены значения отдельных атрибутов (как правило, неключевых). В любом случае непосредственно перед корректировкой выполняется поиск местонахождения корректируемой записи.

Включение новой записи (например, со значением ключевого атрибута w) в последовательный упорядоченный массив не должно нарушать его упорядоченность. Поэтому сначала необходимо найти положение новой записи относительно имеющихся в массиве записей, т. е. выполнить поиск ключа новой записи w. Если значения w в массиве нет, то поиск остановится там, где должна находиться запись с ключом w при сохранении общей упорядоченности массива. Новая запись не может сразу занять место, где остановился поиск, необходимо выполнить пересылку записей, чтобы освободить его. Пересылка начинается с последней записи (она после пересылки занимает следующую позицию по направлению к концу массива), затем предпоследняя запись пересылается на место последней и т. д. В результате освобождается место для новой записи.

Итак, время включения записи складывается из времени поиска и времени пересылки. В среднем пересылка затрагивает примерно половину записей массива. Время пересылки одной записи пропорционально ее длине:

T_k = log M + M L,

где L – длина одной записи массива.

В формуле для Т_k второе слагаемое по величине всегда значительно превышает первое, поэтому можно считать верным следующее выражение:

T_k ~ M L.

При исключении записи из массива также необходимо сначала найти в массиве ключ удаляемой записи, а затем выполнить пересылки записей в направлении к началу массива для уничтожения исключаемой записи в памяти. Очевидно, что время исключения записи описывается той же формулой, что и время ее включения.

Можно прийти к выводу, что включение (исключение) записей по отдельности представляет собой очень длительную процедуру. Поэтому в ряде случаев удобно накапливать корректирующие записи в специальном массиве изменений, а не вносить их по мере появления.

Массив записей, подвергающихся изменениям, называется основным.Изменения, которые необходимо внести в основной массив, накапливаются в специальном упорядоченном массиве изменений, рассчитанном на 1 ≤ m ≤ М записей. Обычно m составляет несколько процентов от М. При необходимости обработки основного массива он объединяется с массивом изменений, для чего выполняются следующие операции (алгоритм слияния):

– ключ очередной записи основного массива сравнивается с ключом очередной записи массива изменений, и запись с меньшим значением ключа добавляется в новый массив (результат слияния);

– когда все записи одного из массивов будут перезаписаны полностью, оставшиеся записи другого массива добавляются в результирующий массив и алгоритм заканчивается.

Решение целого ряда задач обработки данных требует применения таких методов организации данных, которые позволили бы связать физически разнесенные в памяти данные в логическую последовательность, определяющую порядок их обработки. Простейшим методом преодоления этой проблемы является списковая (цепная) организация данных [4, 8, 9].

Спискомназывается множество записей, занимающих произвольные участки памяти, последовательность обработки которых задается с помощью адресов связи. Адресом связинекоторой записи называется атрибут, в котором хранится начальный адрес или номер записи, обрабатываемой после этой записи. Обычная последовательность обработки записей в списке определяется возрастанием значений ключа в записях.

В списке выделяется собственная информация (записи с содержательными сведениями) и ассоциативная информация, т. е. все адреса связи.

Описание записей списка на языке программирования (например, «Паскале») может быть произведено двумя способами [8, с. 154].

1. Определение адресов связи как начальных адресов записей:

type ref = ^ node;

node = record

key: integer; {ключевой атрибут записи}

other: string [30]; {остальные атрибуты}

next: ref {адрес связи}

end.

2. Определение адресов связи как номеров записей:

const М = 12;

type

node = record

key: integer; {ключевой атрибут записи}

other: string [30]; {остальные атрибуты}

next: integer {адрес связи}

end;

var t: array [l..M] of node.

Второй вариант является более практичным, особенно если требуется хранить список на внешнем запоминающем устройстве.

Возможны два способа организации списка – совместное размещение собственной и ассоциативной информации, при котором запись и ее адрес связи образуют одно целое, и раздельное, когда приняты списковая организация адресов связи и последовательное хранение собственной информации [4, 8, 9].

При списковой организации данных необходим специальный атрибут, называемый указателем списка, который содержит начальный адрес или номер первой в порядке обработки списка его записи. Кроме того, адрес связи последней записи списка должен содержать специальное значение, называемое концом списка и показывающее, что последующих записей у данной записи нет. Обычно конец списка отмечается нулем.

При формировании упорядоченного списка записей возможны два варианта:

– вновь поступающие записи вставлять так, чтобы не нарушать упорядоченность по ключу;

– создать сначала неупорядоченный список, а затем отсортировать его.

Учитывая, что для сортировки можно использовать метод слияния, второй вариант следует признать более целесообразным.

В итоге время формирования упорядоченного списка пропорционально величине M log M (T ~ M log M).

Для поиска в упорядоченном списке можно использовать те же методы, что и в последовательном массиве, однако эффективность этих методов иная, поскольку адреса связи создают возможность быстрого доступа только к следующей записи списка.

Для поиска данных в однонаправленном списке применяется единственный метод – последовательный поиск. Ключевой атрибут первой записи (ее адрес извлекается из указателя списка) сравнивается с искомым значением q, затем такое же сравнение выполняется для ключа второй записи, которая извлекается по адресу связи первой записи, и т. д. Время поиска, естественно, пропорционально числу записей: Т ~ М.

Неэффективность бинарного поиска для списковой организации данных объясняется тем обстоятельством, что для достижения середины интервала требуется последовательное движение в соответствии с адресами связи, и суммарное количество переходов от записи к записи достаточно велико. Число таких переходов при доступе к серединам интервалов представляется величиной М /2 + М /4 + М /8 +..., что практически составляет М.

Для ускорения доступа к списку могут быть рекомендованы такие варианты использования адресов связи, как двунаправленный и кольцевой списки:

– двунаправленный список образован двумя цепочками адресов связи – от первой записи к последней и от последней записи к первой;

– в кольцевом списке последний адрес связи указывает на первую запись.

Цепным каталогом называется сплошной участок памяти (или несколько таких участков), в котором одновременно размещаются списки обрабатываемых записей и свободных позиций памяти. Адрес связи, отмечающий первую обрабатываемую запись, называется указателем списка.Адрес связи, показывающий первую свободную позицию памяти, именуется указателем свободной памяти.Адрес связи последней записи (или последней позиции свободной памяти) в списке называется концом списка,и здесь отмечается нулевым значением.

Рассмотрим пример цепного каталога, в котором адреса связи представлены номерами соответствующих записей [8, с. 157]. Описание каталога на языке «Паскаль» имеет вид

const M = 9;

type

node = record

key: integer; {ключевой атрибут записи}

next: integer {адрес связи}

end;

var t: array [l..M] of node.

Включение и исключение записей в цепном каталоге предполагает поиск местоположения включаемой (исключаемой) записи и замену значений адресов связи для установления новой последовательности записей основного списка и списка свободной памяти.

Используется нижеприведенный алгоритм вставки записи с ключом F в цепной каталог.

1. Найти в каталоге запись с ключом непосредственно меньше, чем F (предшествующую запись).

2. Поместить запись с ключом F в первую позицию свободной памяти.

3. Заменить указатель свободной памяти (УСП) на адрес связи новой записи, его – на адрес связи предшествующей записи, а последний – на первоначальное значение УСП.

Распространен такой алгоритм удаления записи с ключом W из каталога.

1. Найти в каталоге запись с ключом непосредственно меньше, чем W (предшествующую запись).

2. Заменить УСП на адрес связи предшествующей записи, его – на адрес связи исключаемой записи, а последний – на первоначальное значение УСП.

Оценка времени корректировки складывается из времени реализации поиска и времени на замену значений адресов связи. В последнем случае число пересылок адресов связи всегда одинаково и не зависит от числа записей в цепном каталоге, поэтому затраты времени на поиск при корректировке являются доминирующими и время корректировки пропорционально числу записей (Т ~ М).

Древовидной организацией данных (деревом) называется множество записей, расположенных по уровням следующим образом [4, 8, 9]:

– на 1-м уровне размещена только одна запись (корень дерева);

– к любой записи i -гo уровня ведет адрес связи только от одной записи уровня i – 1.

В данном толковании понятия «дерево» и «уровень» вводятся одновременно. Если записи получат номера уровней, соответствующие определению, то они получат и древовидную организацию.

Количество уровней в дереве называется рангом.Записи дерева, которые адресуются от общей записи (i – l)-гo уровня, образуют группу.Максимальное число элементов в группе называется порядком дерева.Деревья обычно формируются двунаправленными, адрес связи от записи уровня i + 1 к записи i -гo уровня называется обратным. При размещении дерева в памяти ЭВМ каждая запись может занимать произвольное место.

Набор адресов связи, принадлежащих одной записи, называют звеном связи. Если порядок дерева равен р, то звено связи состоит из р + 1 адресов (один адрес обратный, определяющий связь с записью непосредственно более высокого уровня). Корень дерева адресуется из специального указателя дерева. Незанятые адреса связи содержат признак конца списка.

Рассмотрим деревья порядка 2 (бинарные). Они интересны тем, что составляющие их записи могут быть упорядочены. Для этого один из атрибутов записи должен быть объявлен ключевым.

Чтобы дать определение упорядоченности бинарных деревьев, требуется ввести ряд новых понятий. В качестве примера рассмотрим бинарное дерево на рис. 15, где внутри показаны значения ключевого атрибута [8, с. 162].

Запись А – корень дерева. Записи, у которых заполнены два адреса связи, называются полными, с одним заполненным адресом – неполными, с двумя незаполненными адресами – концевыми.На рис. 15 записи А, В, Е, F – полные, С – неполная, D, G, H, I, J, – концевые. Адреса связи делятся на левые и правые. Так, адрес от Е к Н – левый, от F к I – правый. Каждая запись имеет левую и правую ветви. Правую (левую) ветвь записи образует поддерево, адресованное из этой записи через правый (левый) адрес связи. У записи С правая ветвь состоит из записей F, I, J, левая ветвь пустая

.

Рис. 15

В упорядоченном бинарном дереве значение ключевого атрибута каждой записи должно быть больше, чем значение ключа у любой записи на ее левой ветви, и не меньше, чем ключ любой записи на ее правой ветви. Это определение позволяет также различать левые и правые адреса (ветви).

Упорядоченное бинарное дерево формируется из неупорядоченного массива записей по специальному алгоритму. Этот алгоритм создает дерево из первой записи массива, затем – дерево из первых двух записей, из первых трех записей и так до исчерпания всех записей массива.

Приведем алгоритм построения упорядоченного бинарного дерева [8, с. 162].

1.Первая запись массива с ключом р (1) становится корнем дерева.

2.Значение ключа второй записи р (2) сравнивается с р (1), находящимся в корне дерева. Если р (2) < р (1), то вторая запись помещается на левой от корня ветви, в противном случае – на правой. Сейчас получено упорядоченное дерево из первых двух записей, далее на каждом шаге создается упорядоченное дерево из первых i записей.

3. Выбор места i -й записи массива производится следующим образом. Ключ p (i) сравнивается с корневым значением, выполняется переход по левому адресу (если p (l) > p (i)), а при p (l) ≤ p (i) – по правому адресу. Ключ достигнутой записи также сравнивается с p (i), и снова организуется переход по левому или правому адресу, и т. д. Когда будет достигнут незаполненный адрес связи, он должен адресовать запись с ключом p (i). Указанные действия повторяются до исчерпания всех записей исходного массива.

Например, упорядоченное дерево на рис. 15 получается из массива записей с ключевыми атрибутами 23, 10, 18, 27, 15, 32, 8, 30, 32, 21.

В процессе поиска данных по совпадению в упорядоченном бинарном дереве просматривается некоторый путь по дереву, начинающийся всегда от его корня. Искомое значение ключа q сравнивается со значением корня р (1). Если p (l) > q, просмотр дерева продолжается по левой ветви корня, если p (l) ≤ q – по правой. Для произвольной записи дерева с ключом p (i) результаты сравнения означают:

– p (i) = q: запись, удовлетворяющая условию поиска, найдена, и поиск продолжается по правой ветви p (i);

– p (i) > q: производится переход к записи, расположенной на левой ветви p (i);

– p (i) < q: осуществляется переход к записи, расположенной на правой ветви р (i).

Поиск заканчивается, когда у какой-либо записи отсутствует адрес связи, необходимый для дальнейшего продолжения поиска.

Для определения среднего числа сравнений при поиске записи в упорядоченном бинарном дереве рассмотрим ситуацию, когда требуемая запись не найдена, что равноценно вставке записи с искомым значением в дерево. Ненайденный ключ может с одинаковой вероятностью попасть в один из М + 1 интервалов, образованных ключами, находящимися в дереве. Неудачный поиск закончится всегда на нулевом адресе связи.

Если обозначить через Е (М) сумму длин всех ветвей дерева с учетом выхода на нулевые адреса связи, то среднее число сравнений при поиске в упорядоченном бинарном дереве составит

(М) = Е (М) / (М + 1).

Дерево с М – 1 вершиной отличается от дерева с М вершинами, полученного из него, отсутствием одной концевой записи или (применительно к величине Е) двумя нулевыми адресами связи. Поэтому Е (М) – Е (М – 1) = 2. Вычислим разность

.

Математическое ожидание средней длины пути при поиске равно сумме математических ожиданий dL от 1 до М. Приближенно заменяя суммирование интегрированием [8], получаем:

= 2 ln (М + 1).

При замене натурального логарифма на двоичный (ln 2 = 0,7) получаем оценку числа сравнений при поиске в упорядоченном бинарном дереве:

С = 1,4 log M, или С ~ log M.

При формировании упорядоченного бинарного дерева в среднем производится

С = l,4 M · log M

сравнений пар ключевых атрибутов, где М – число записей, для которых строится дерево. Это соответствует затратам на поиск местоположения очередной записи в упорядоченном бинарном дереве из двух, трех и более (до М) записей.

Включение новой записи при корректировке упорядоченного бинарного дерева означает выполнение одного шага алгоритма формирования дерева с включаемой записью на входе.

Сложность исключения зависит от того, какая запись исключается – концевая, неполная или полная. Первые два случая аналогичны корректировке при списковой организации данных. Адрес связи на исключаемую концевую запись заменяется признаком конца строки, адрес связи на исключаемую неполную запись – ее собственным адресом связи.

При исключении полной записи решается задача о подстановке на ее место другой записи, такой, что ее ключ не нарушает общей упорядоченности бинарного дерева – подобные записи называются соседними. Соседняя слева запись – это запись с ключом, который непосредственно меньше ключа данной записи, а ключ соседней справа записи равен или непосредственно больше, чем ключ данной записи.

Способ нахождения соседней справа записи очень прост. Если исключаемая запись имеет ключ q, то от нее происходит переход по правой ветви дерева и производится поиск от достигнутой записи значения q. Запись, на которой остановится поиск, будет соседней. Она пересылается на место исключаемой записи, а сама соседняя запись исключается. Это уже простая задача, так как соседняя запись не может быть полной.

При поиске соседней слева записи надо выполнить переход по левой ветви от данной записи (с ключом q), а дальнейшие действия будут такими же, как и для поиска соседней справа записи.

В табл. 5 собраны все оценки методов организации данных, что позволяет сделать ряд выводов.

Таблица 5

Критерий оценки	Метод организации данных	Лучший метод
Последовательный массив	Цепной каталог	Бинарное дерево
Время формирования	~ М log M	~ М log M	~ М log M	Цепной каталог, бинарное дерево
Время поиска	~ log M	~ M	~ log M	Последовательный массив, бинарное дерево
Время корректировки	~ M	~ M	~ log M	бинарное дерево
Объем дополнительной памяти		~ M	~ M	последовательный массив

По времени формирования данных цепной каталог и бинарное дерево имеют определенные преимущества перед последовательным массивом, несмотря на то что процессы формирования описываются одинаковыми формулами. Это объясняется необходимостью пересылки записей в процессе сортировки последовательного массива, тогда как в цепном каталоге и бинарном дереве при формировании пересылаются адреса связи, а не целые записи.

По времени поиска последовательный массив и бинарное дерево предпочтительнее цепного каталога. Минимальное время корректировки характерно для бинарного дерева, а минимальный объем дополнительной памяти – для последовательного массива.

Мы приходим к окончательному выводу, что абсолютно безупречного метода организации данных не существует. Однако минимальное время обычно считается более важным критерием, чем минимальная дополнительная память, поэтому лучшим методом организации данных в оперативной памяти ЭВМ необходимо признать упорядоченное бинарное дерево.

Отметим, что для последовательной и цепной организации данных разработаны методы ускорения поиска, представленные в работах А.И. Мишенина и С.П. Салмина [8, 9].

Контрольные вопросы и задания

1. Перечислите основные понятия организации данных. Что вы понимаете под организацией значений данных?

2. Расскажите о разновидностях организации данных.

3. Назовите критерии эффективности алгоритмов.

4. Как осуществляется поиск в последовательном массиве?

5. Опишите порядок корректировки последовательного массива.

6. Перечислите особенности цепной (списковой) организации данных.

7. Охарактеризуйте цепной каталог.

8. Какова специфика древовидной организации данных?

9. Выполните задания 3.1–3.19 по теме «Последовательная организация данных» из практикума [9, с. 390–143].

10. Выполните задания 3.20–3.37 по теме «Цепная организация данных» из практикума [9, с. 147–153].

11. Выполните задания 3.38–3.62 по теме «Древовидная организация данных» из практикума [9, с. 156–159].