Разница — в заключительных действиях. Есть и смешанный режим — поиск со вставкой, предусматривающий либо использование найденного элемента, либо включение в БДУ нового с равным аргументу поиска значением ключа. Вспомните принцип построения трассы поиска. Сложность акта включения в БДУ . Та же картина — с исключением. Включение в БДУ — тема задания . Исключение из БДУ, простое для листа, усложняется, если надо удалить не. Решением проблемы является исключение узла . В самом деле, узел У в правом поддереве не может быть ближайшим . В левом поддереве — лишь та особенность, что возможна цепь узлов с равными значениями ключа, ближайшими к . Общая стратегия исключения может быть различна и зависит от типа узлов БДУ. Включение в первоначально пустое БДУ п ключей, а затем исключение . Корнем с пустыми ссылками . Способ, когда поиск отделен от использования, хотя бы исключения узла, как видим, имеет издержки. Запишите блок удаления исМ узла с заданным значением ключа, выделив, как самые простые, случаи исключения листа и узла с одним сыном. Универсальный блок поиска в БДУ В БДУ мы имели дело с поиском по совпадению, рассмотрим и Другие случаи . Поиск по интервалу обозначим значением . Излагаемый алгоритм поиска надо изучать с карандашом в руках, прослеживая его работу на примере конкретного БДУ для конкретных аргументов поиска. Проходя трассу поиска, начинающуюся от корня, прежде всего будем проверять в узле ключ на совпадение с аргументом поиска, означающее успешный конец поиска для случаев . Это последний из узлов, от которых трасса поиска идет влево. Ссылки на такие узлы помещаем в стек г. В отсутствие ключа, равного аргументу, трасса завершается в листе, и в этот момент ссылка на вышеупомянутый узел находится в верхушке стека. Эта ссылка пересылается в рр. Рассмотрим следующее БДУ. Верхушка стека будет содержать ссылку на узел . В каждом случае имеем ссылку на ближайшее к аргументу . Даже если рр ф . Это может быть один и тот же узел, т. искомое множество записей пусто и обработки нет. Тогда значение рр устанавливается в . Это как бы поиск по интервалу с равными границами. Ни одного шага вправо не будет . Как и в п. Аналогично перестроим блоки включения и исключения. Например, при поиске и обработке всех записей о студентах . В функциях пользователя значения полей можно преобразовывать, например, чтобы вести поиск по абсолютной величине. Аргументы поиска могут быть представлены глобальными переменными и выражениями. Применение функций пользователя замедляет поиск. ФОсуществите указанные изменения в блоке . Применение подравненных БДУ БДУ как динамическая структура весьма привлекательно, особенно, если узлы. худший случай подобен простому перебору по времени поиска. Чтобы исключить такие БДУ, Адельсон. Для понимания его сути рассмотрите одно из . Перестройке подвергается часть трассы включения узла. Например, она потребуется после включения в наше ПД числа М, которое меньше всех чисел ПД, ибо высота левых поддеревьев для всех узлов трассы окажется на . Теперь включим в ПД еще меньшее число ММ — вновь потребуется перестройка. Положение в БД У узла — отца узла А не изменяется, но сын . Для отыскания узла А каждый узел снабжается оценкой . Показано, что узел А — всегда последний на трассе включения узел, для которого . В среднем перестройка возникает в . Всегда после включения требуется коррекция оценок . Убедитесь в этом на примерах. Асимптотическая ВС построения ПД из п узлов равна . Получена динамическая структура с небольшим различием средней и экстремальной оценки ВС и приемлемой ЕС. Хорошие идеи губит плохая реализация. Хотя выше показаны лишь . Если М больше одного только числа Ъ перестройка также несложна. До сих пор мы исходили из того, что равные ключи могут быть только справа. Заметим, что не нарушая этот принцип, гарантировать . Линейный порядок при обходе БДУ слева не нарушается, но немного усложняется поиск по совпадению . Поэтому для работы с подравненным БДУ блок . Обдумайте проблемы сохранения подравненного БДУ в случае исключения узлов. ВЫВОДЫ В данной главе рассмотрены различные концептуальные схемы, позволяющие рядовому пользователю надежно и быстро выполнять обработку данных в практически значимых случаях. Нужно лишь строго придерживаться нехитрых правил оформления блоков, подчиненных главному . Новые идеи, алгоритмы составят интерес и для продвинутого читателя. Выбирались алгоритмы, обеспечивающие компактность универсальных блоков. Читатель может найти в литературе и другие концепции выполнения поиска, специальных сортировок, например, в . Сложные средства, например хеширование, в данное издание не вошли. Поэтому если любой известный нам способ упорядочения в памяти применить . Сортировку данных на магнитных лентах и дисках называют внешней. Усложнение ее процессов, их неоднородность и многообразие факторов, влияющих на производительность, обусловили появление большого числа алгоритмов, часть из которых уже потеряла актуальность. Особенность данной главы — рассмотрение так называемой . Она использует по возможности меньшее дисковое пространство . Ее появление вызвано необходимостью сокращения размера . Здесь мы рассмотрим простые по своей идее алгоритмы, которые однако могут составить серьезную конкуренцию, особенно алгоритмы из пп. Как и в случае внутренней сортировки, рассматривается альтернатива. Известны внешние сортировки слиянием и распределением. Здесь предлагается еще один вариант . Составляющие сложности сортировки на диске Исследовать, а тем более конструировать внешнюю сортировку невозможно, не представляя, мало. Диски имеют запоминающие магнитные поверхности и вращаются с большой постоянной скоростью под головками чтения. Головка обслуживает одну поверхность — сторону . Совокупность этих треков назовем, следуя традиции, текущим цилиндром. Головки крепятся на штанге, подобной . После перемещения блока головок . Цилиндры нумеруются в порядке их прохождения блоком головок при движении штанги в одну сторону.